将表达式转换为具有扭曲的连接正态形式 [英] Converting an expression to conjunctive normal form with a twist

问题描述

我有一个库，我必须与哪些行为基本上作为数据源接口。检索数据时，我可以将特殊的过滤器表达式传递给该库，稍后将其转换为SQL WHERE部分。这些表达式非常有限。他们必须是联合正常的形式。喜欢：

 （A或B或C）和（D或E或F）和... 
  

这当然不是很适合编程。所以我想制作一个可以解析任意表达式并将它们转换为正常形式的包装器。喜欢：

 （A和（B或C）和D）或E 
  

将被翻译成如下：

  A或E）和（B或C或E）和（D或E）
  

我可以解析使用 Irony 库的树形表达式。现在我需要规范化，但是我不知道如何...哦，这里也是这样：

• 最后的表达式可能不包含 NOT 运算符。然而，我可以通过用逆运算符替换运算符来反转单个项。所以，这是可以的：
  
  （不是A或不B）AND（不是C或不D）
  
  但这不是：
  
  
  不（A或B）而不是（C或D）
  
  


• 我想使表达式尽可能简单，因为它将被转换为几乎相同的SQL WHERE语句，因此复杂的语句很可能会降低执行速度。

解决方案

我会在树上使用两个迭代，虽然可能在一个。

第一次迭代：通过遍历树并使用De Morgan定律来摆脱您的NOT节点（维基百科链接），并在适用的情况下删除双重否定。

第二次迭代（NOT现在只是在叶节点）
通过树：

 案例AND NODE：
罚款，检查孩子
案例OR NODE：
如果有一个孩子既不是Leaf也不是NOT节点
应用分配规则。 
从当前节点的父节点开始
 else 
罚款，检查孩子
  

之后，您应该完成。

I've got a library that I have to interface with which acts basically as a data source. When retrieving data, I can pass special "filter expressions" to that library, which later get translated to SQL WHERE part. These expressions are pretty limited. They must be in conjunctive normal form. Like:

(A or B or C) and (D or E or F) and ...

This of course isn't very comfortable for programming. So I want to make a little wrapper which can parse arbitrary expressions and translate them to this normal form. Like:

(A and (B or C) and D) or E

would get translated to something like:

(A or E) and (B or C or E) and (D or E)

I can parse an expression to a tree with the Irony library. Now I need to normalize it, but I don't know how... Oh, also, here's the twist:

• The final expression may not contain the NOT operator. However, I can inverse the individual terms by replacing the operators with the inverse operators. So, this is OK:
  
  (not A or not B) AND (not C or not D)
  
  but this is not:
  
  not (A or B) and not (C or D)
  
  
• I would like to make the expression as simple as possible, because it will be translated to a practically identical SQL WHERE statement, so a complex statement would most likely slow down execution speed.

解决方案

I'd use two iterations over the tree, although it's probably possible in one.

First iteration: get rid of your NOT Nodes by walking through the tree and using De Morgan's law (wikipedia link) and remove double negation wherever applicable.

Second iteration (the NOT are now only directly before a leaf node) Go through your tree:

Case "AND NODE":
    fine, inspect the children
Case "OR NODE":
    if there is a child which is neither a Leaf nor a NOT node
        apply the distributive law.
        start from parent of current node again
    else
        fine, inspect children

After that you should be done.

这篇关于将表达式转换为具有扭曲的连接正态形式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！