Paper Info
Title
The containment problem for Real conjunctive queries with inequalities
Abstract
Query containment is a fundamental algorithmic problem in database query processing and optimization. Under set semantics, the query-containment problem for conjunctive queries has long been known to be NP-complete. In real database systems, however, queries are usually evaluated under bag semantics, not set semantics. In particular, SQL queries are evaluated under bag semantics and return multisets as answers, since duplicates are not eliminated unless explicitly requested. The exact complexity of the query-containment problem for conjunctive queries under bag semantics has been an open problem for more than a decade; in fact, it is not even known whether this problem is decidable.Here, we investigate, under bag semantics, the query-containment problem for conjunctive queries with inequalities. It has been previously shown that, under set semantics, this problem is complete for the second level of the polynomial hierarchy. Our main result asserts that, under bag semantics, the query-containment problem for conjunctive queries with inequalities is undecidable. Actually, we establish the stronger result that this problem is undecidable even if the following two restrictions hold at the same time: (1) the queries use just a single binary relation; and (2) the total number of inequalities is bounded by a certain fixed value. Moreover, the same undecidability results hold under bag-set semantics.
Year
DOI
Venue
2006
10.1145/1142351.1142363
PODS
Keywords
Field
DocType
main result,real conjunctive query,database query processing,bag-set semantics,open problem,bag semantics,query-containment problem,fundamental algorithmic problem,conjunctive query,sql query,set semantics,conjunctive queries,inequalities,database system,binary relation
Polynomial hierarchy,Discrete mathematics,Operational semantics,Conjunctive query,Open problem,Computer science,Binary relation,Theoretical computer science,Boolean conjunctive query,Semantics,Undecidable problem
Conference
ISBN
Citations 
PageRank 
1-59593-318-2
28
1.19
References 
Authors
10
3
Name
Order
Citations
PageRank
T. S. Jayram1137375.87
Phokion G. Kolaitis22733514.37
Erik Vee374743.61