Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948
December 22, 2009

是王建硕提出的。他用英文写的,我用英文和他探讨了一下,觉得还是很有意思的一个题目。我这里用中文总结一下,免得忘记了。

有一个数据库的表T,表里面有多个列Ci,每个列的值域是实数。在这个表上可以定义查询。一个查询Q是一个表达式树,这个表达式树的非叶子结点,都是布尔表达式;而叶子结点,都是比较表达式。比较表达式的意思,就是一个列的名字Ci,一个比较运算符(<,<=,>,>=,<>)这些,然后一个实数值。

一个查询的例子:NOT (AND ((C1>5), OR ((C2<6),(C3<>9))))

问题是:给出两个这样的查询Q1和Q2,如何确定Q1的结果是否是Q2结果的子集?

这个的确是一个比较难的题目,因为比较的是两个查询,而不是两个结果集合。建硕也指出,这里最麻烦的,是那些比较表达式,因为它们是多个列上面的比较。

我给出了一个解法,是这样的:

  1. 对比较表达式进行改造,变为值域。比如:C1>=3变为:C1:[3,+∞);C2<>9变为:C2:(-∞,9) OR C2:(9,+∞)
  2. 对布尔表达式进行计算,最终的目的,是把表达式树变成一组item的OR的运算;而每个item,是一组factor之间的AND运算;每个factor,是一个值域。每个item里面,一个列名Ci最多只能出现一次。
  3. 对于每一个item,找出里面没有出现的列名Ci,增加相应的值域Ci(-∞,+∞)。
  4. 剩下的事情就简单了。对于Q2里面所有的item,看Q1里面是否存在一个item可以把它覆盖。如果是,那么Q2的结果,一定是Q1的子集。

这个是代数的解法,对应的几何映射,就是一个N维空间,其中N是表T的列的数目。每个列,都是空间里面的一维。每个item,都是空间里面的一个区域。每个查询,就是空间里面的一组这样的区域。表格T里面的任何一个可能的列,都是空间里面的一个点。查询的结果,就是落在这组空间里面的点的集合。

那么计算Q2是否是Q1的子集,就是计算Q2定义的空间区域集合,是否能被Q1定义的空间区域集合所容纳。

7 Comments »


  1. # 对布尔表达式进行计算,最终的目的,是把表达式树变成一组item的OR的运算;而每个item,是一组factor之间的AND运算;每个factor,是一个值域。每个item里面,一个列名Ci最多只能出现一次。

    How do you know this can always be done?

    It’s true that all logical formulas can be converted into disjunctive normal form, but in your solution you have extra constraints:

    “每个item里面,一个列名Ci最多只能出现一次。”

    I also think this can be done. The intuition is that for all the constraints concerning a particular column Ci, we should be able to converted it into this form:
    Cons1(Ci) or Cons2(Ci) or Cons3(Ci)
    while Cons1, Cons2… are mutually exclusive. Then we should be able to put every Consj(Ci) into a different item in disjunctive normal form(DNF), or the same item in conjunctive normal form(CNF).
    However, I can’t give a rigid mathematical proof for this for now.

    While you’re using DNF, I think it might be a better idea to use CNF, so that every item is only concerned with one column and one column only.

    There could be some inconveniences for DNF if we do this programmingly. Say we’re given
    query A:
    C2:(-∞,9] OR C2:[9,+∞)
    and
    query B:
    C2:(-∞,10) OR C2:(10,+∞)

    According to your rules we can’t say result of query B is a subset of result of query A because (-∞,10) can’t be covered. So we need to merge all the items that can be merged in the DNF at the end of step 2. (but then, can we still guarantee that one column appears not more than once in one item?)

    And also for every item in DNF, we have to compare it with every item in the other DNF. While for CNF we just need to compare it with the corresponding item concerning the same column.

    Topologically speaking, DNF decomposes the query to a few nonadjacent sets, while CNF decomposes the query into its projections on all axis(columns)

    Apparently CNF offers much less complexity for this problem.

    But, with all that being said, we still need a mathematical proof.

    Comment by Song Wei — December 22, 2009 @ 2:55 pm

  2. 没错。从几何意义上说,判断一组物体是否可以放进另外一组空间,也是有相当计算量的事情。其中一个原因是空间的切割 - 在你的表述里面,就是那个 “9] OR [9″ 的部分,这里9就是一个切割。

    我们这里讨论的相对简单一些,因为我们讨论的是方体,各个维度之间没有复杂的相关关系,如果我们在这个问题里面扔进去一个双曲面,就有乐子看了。 :D

    CNF的方法我还需要认真想想。总之,多谢你的回复。

    Comment by 美人她爹 — December 22, 2009 @ 6:08 pm

  3. 此问题是NP-hard的,理论上而言不存在多项式的算法~

    见:http://zhiqiang.org/blog/science/computer-science/database-query-is-np-hard.html

    Comment by zhang — December 22, 2009 @ 6:54 pm


  4. Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

    Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

    不好意思,我发现我说得不对。
    下班了可以用中文。。。
    DNF里每一个column可以保证不出现多余一次,因为item里面都是and。你说的是可行的。

    想让所有query的CNF里面每一个item都只跟一个column相关,是不可能的。因为这样的话每一个query(N維空间中的区域)就可以简单的用其N个投影重构。这是不可能的。问题中的query格式可以描述N维空间中任何形状的多边形。

    我同意zhang所说。DNF有一个问题是可能会搞出很多项来。见
    http://www.statemaster.com/encyclopedia/Disjunctive-normal-form
    我现在不能判断这个是不是比brutal force的枚举更好。
    brutal force的枚举的话复杂度是
    O(n1 n2 n3… nN),其中nj是关于Cj的叶节点数量。

    一个quick and dirty 的hack是根据数据的特性来决定枚举的顺序。

    Comment by Song — December 22, 2009 @ 8:33 pm

  5. 多谢大家参与。这个题,还是美人她爹提到的DNF是最重要的一个解题的关键,就是把一个布尔表达式变成一个析取范式(disjunctive normal form),然后就比较简单了。最近又在忙其他的事情,还没来的写这个从一般表达式变成析取范式的算法,这应该是比较标准的,但是没有写过,谁让自己不是计算机系的呢?

    Comment by Jian Shuo Wang — December 25, 2009 @ 7:17 am

  6. [...] 问题来自美人他爹和Wangjianshuo’s blog [...]

    Pingback by 数据库查询是NP-Hard问题 @ 阅微堂 — January 21, 2010 @ 6:25 pm

  7. 音楽アモイファミリーのウェブサイトの統計によると、中国市場でナイキは昨年、

    Comment by ナイキシューズ — September 19, 2012 @ 11:56 pm

RSS feed for comments on this post. TrackBack URI

Leave a comment 说两句吧