一个查询的例子： NOT (AND ((C1>5), OR ((C2<6),(C3<>9))))
问题 1 ：给出两个这样的查询 Q1 和 Q2 ，如何确定 Q1 的结果是否是 Q2 结果的子集？
上面两篇文章主要是讨论实际工作中怎么解决问题 1。下面从理论上分析一下这个问题。
问题 2 ：判断 Q1 查询结果是否为空集。
在问题 1 中让 Q2 查询结果为空集，故问题 1 是比问题 2 更难的一个问题。
论断：问题 2 是NP-hard的。
证明：从 3SAT 问题很容易规约到问题 2。
结论：问题 1 是 NP-Hard 的，除非 NP=P ，不可能有多项式级别的解。也就是理论上而言，解决上面的问题除了枚举没有别的好方法了。
当然以上只是理论，实际应用中，$ 3^n$ 的计算速度和$ 2^n$ 的计算速度还是有很大的区别。如何解决 NP-Hard 问题也是一个被广泛研究的课题，毕竟实际工作中很多问题都是 NP-Hard 的。
Q. E. D.
