6
数据库查询是 NP-Hard 问题
source link: https://zhiqiang.org/cs/database-query-is-np-hard.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
数据库查询是 NP-Hard 问题
一个查询的例子： 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 ，不可能有多项式级别的解。也就是理论上而言，解决上面的问题除了枚举没有别的好方法了。
当然以上只是理论，实际应用中，3n3n 的计算速度和2n2n 的计算速度还是有很大的区别。如何解决 NP-Hard 问题也是一个被广泛研究的课题，毕竟实际工作中很多问题都是 NP-Hard 的。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK