Computer Science – Databases
Scientific paper
1998-12-28
Journal of Computer and System Sciences, 64(3):579-627, 2002
Computer Science
Databases
30 pages, 7 figures, uses fancybox, epsfig, epic, and eepic
Scientific paper
10.1006/jcss.2001.1809
Several important decision problems on conjunctive queries (CQs) are NP-complete in general but become tractable, and actually highly parallelizable, if restricted to acyclic or nearly acyclic queries. Examples are the evaluation of Boolean CQs and query containment. These problems were shown tractable for conjunctive queries of bounded treewidth and of bounded degree of cyclicity. The so far most general concept of nearly acyclic queries was the notion of queries of bounded query-width introduced by Chekuri and Rajaraman (1997). While CQs of bounded query width are tractable, it remained unclear whether such queries are efficiently recognizable. Chekuri and Rajaraman stated as an open problem whether for each constant k it can be determined in polynomial time if a query has query width less than or equal to k. We give a negative answer by proving this problem NP-complete (specifically, for k=4). In order to circumvent this difficulty, we introduce the new concept of hypertree decomposition of a query and the corresponding notion of hypertree width. We prove: (a) for each k, the class of queries with query width bounded by k is properly contained in the class of queries whose hypertree width is bounded by k; (b) unlike query width, constant hypertree-width is efficiently recognizable; (c) Boolean queries of constant hypertree width can be efficiently evaluated.
Gottlob Georg
Leone Nicola
Scarcello Francesco
No associations
LandOfFree
Hypertree Decompositions and Tractable Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hypertree Decompositions and Tractable Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypertree Decompositions and Tractable Queries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-33994