✦ LIBER ✦

Hypertree Decompositions and Tractable Queries

✍ Scribed by Georg Gottlob; Nicola Leone; Francesco Scarcello

Book ID: 102587333
Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 368 KB
Volume: 64
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.2001.1809

No coin nor oath required. For personal study only.

✦ Synopsis

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 (Ch. Chekuri and A.

📜 SIMILAR VOLUMES

Weighted hypertree decompositions and op

Weighted hypertree decompositions and optimal query plans

✍ Francesco Scarcello; Gianluigi Greco; Nicola Leone 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 497 KB

[Lecture Notes in Computer Science] Math

[Lecture Notes in Computer Science] Mathematical Foundations of Computer Science 2012 Volume 7464 || Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity?

✍ Rovan, Branislav; Sassone, Vladimiro; Widmayer, Peter 📂 Article 📅 2012 🏛 Springer Berlin Heidelberg 🌐 German ⚖ 244 KB

[IEEE 2008 IEEE International Conference

[IEEE 2008 IEEE International Conference on Multimedia and Expo (ICME) - Hannover, Germany (2008.06.23-2008.04.26)] 2008 IEEE International Conference on Multimedia and Expo - Intelligent Concept-Oriented and Content-Based Image Retrieval by using data mining and query decomposition techniques

✍ Tseng, Vincent. S.; Ja-Hwung Su, ; Hao-Hua Ku, ; Bo-Wen Wang, 📂 Article 📅 2008 🏛 IEEE ⚖ 304 KB