我编写了一个将表达式解析为抽象语法树的小应用程序。现在,我对表达式使用了一堆启发式方法来决定如何最好地评估查询。不幸的是,有些例子使查询计划非常糟糕。
我已经找到了一种可以证明更好地猜测应该如何评估查询的方法,但是我需要首先将我的表达式放入 CNF 或 DNF 中,以便获得可证明的正确答案。我知道这可能会导致潜在的指数时间和空间,但对于我的用户运行的典型查询,这不是问题。
现在,为了简化复杂的表达式,我一直手动转换为 CNF 或 DNF。(好吧,也许不是一直,但我确实知道这是如何使用例如德摩根定律、分配定律等来完成的。)但是,我不确定如何开始将其转换为可作为算法实现的方法。我看过关于查询优化的论文,有几篇以“首先我们将事物放入 CNF”或“首先我们将事物放入 DNF”开始,但他们似乎从未解释过他们实现这一目标的方法。
我应该从哪里开始?