数据库查询是NP-Hard问题

作者:, 发表于

问题来自美人他爹Wangjianshuo's blog

一个查询的例子: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.


上一篇:PCP - Probabilistic Checkable Proof2008年10月19日
PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一,它给了NP问题一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP

下一篇:动态修改Excel数据表的数据来源2010年1月13日
Excel有一个很有用的功能是直接导入外部数据库或者使用外部数据源建立数据透视表和数据透视图。但比较可惜的是,这个数据源的查询语句是静态的


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。