数据库查询是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，不可能有多项式级别的解。也就是理论上而言，解决上面的问题除了枚举没有别的好方法了。
当然以上只是理论，实际应用中，
的计算速度和
的计算速度还是有很大的区别。如何解决NP-Hard问题也是一个被广泛研究的课题，毕竟实际工作中很多问题都是NP-Hard的。
Merry Christmas ~ O(∩_∩)O ~
灰度sTyles送给你最美好的祝福 ~
* ,
_/^_
* /.-. *
* `/&` *
,@.*;@,
/_o.I %_ *
* (`’–:o(_@;
/`;–.,__ `’) *
;@`o % O,*`’`&
* (`’–)_@ ;o %’() *
/`;–._`”–._O’@;
/&*,()~o`;-.,_ `””`)
* /`,@ ;+& () o*`;-’;
(`””–.,_0o*`;-’ &()
/-.,_ “”–….-’`) *
* /@%;o`:;’–,.__ __.’
;*,&(); @ % &^;~`”`o;@(); *
/()Evlos & ().oFriendsO
`”=”==””==,,,.,=”==”===”`
__.—-.(-”#####—…___…—–._
‘` )_`”””””`
.–’ ‘)
o( )_-
`”””` `
眼睛都看花了，看不懂呀