Hypertree Decompositions and Tractable Queries.

@inproceedings{DBLP:conf/pods/GottlobLS99,
  author    = {Georg Gottlob and
               Nicola Leone and
               Francesco Scarcello},
  title     = {Hypertree Decompositions and Tractable Queries},
  booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1999},
  isbn      = {1-58113-062-7},
  pages     = {21-32},
  ee        = {http://doi.acm.org/10.1145/303976.303979, db/conf/pods/GottlobLS99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[2]

Stefan Arnborg: Efficient Algorithms for Combinatorial Problems with Bounded Decomposability - A Survey. BIT 25(1): 2-23(1985) BibTeX

[3]

Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX

[4]

Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX

[5]

Wolfgang Bibel: Constraint Satisfaction from a Deductive Viewpoint. Artif. Intell. 35(3): 401-413(1988) BibTeX

[6]

Hans L. Bodlaender: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput. 25(6): 1305-1317(1996) BibTeX

[7]

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) BibTeX

[8]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[9]

Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70 BibTeX

[10]

Alessandro D'Atri, Marina Moscarini: Recognition Algorithms and Design Methodologies for Acyclic Database Schemes. Advances in Computing Research 3: 43-67(1986) BibTeX

[11]

...

[12]

Rina Dechter, Judea Pearl: Tree Clustering for Constraint Networks. Artif. Intell. 38(3): 353-366(1989) BibTeX

[13]

Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX

[14]

Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX

[15]

Eugene C. Freuder: A Sufficient Condition for Backtrack-Bounded Search. J. ACM 32(4): 755-761(1985) BibTeX

[16]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[17]

Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982) BibTeX

[18]

Georg Gottlob, Nicola Leone, Francesco Scarcello: The Complexity of Acyclic Conjunctive Queries. FOCS 1998: 706-715 BibTeX

[19]

...

[20]

...

[21]

...

[22]

Sheila A. Greibach: The Hardest Context-Free Language. SIAM J. Comput. 2(4): 304-310(1973) BibTeX

[23]

Marc Gyssens, Peter Jeavons, David A. Cohen: Decomposing Constraint Satisfaction Problems Using Database Techniques. Artif. Intell. 66(1): 57-89(1994) BibTeX

[24]

Marc Gyssens, Jan Paredaens: A Decomposition Methodology for Cyclic Databases. Advances in Data Base Theory 1982: 85-122 BibTeX

[25]

Peter Jeavons, David A. Cohen, Marc Gyssens: Closure properties of constraints. J. ACM 44(4): 527-548(1997) BibTeX

[26]

...

[27]

Phokion G. Kolaitis, Moshe Y. Vardi: Conjunctive-Query Containment and Constraint Satisfaction. PODS 1998: 205-213 BibTeX

[28]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[29]

Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19 BibTeX

[30]

Xiaolei Qian: Query Folding. ICDE 1996: 48-55 BibTeX

[31]

Neil Robertson, Paul D. Seymour: Graph Minors. II. Algorithmic Aspects of Tree-Width. J. Algorithms 7(3): 309-322(1986) BibTeX

[32]

Walter L. Ruzzo: Tree-Size Bounded Alternation. J. Comput. Syst. Sci. 21(2): 218-235(1980) BibTeX

[33]

Sven Skyum, Leslie G. Valiant: A Complexity Theory Based on Boolean Algebra. J. ACM 32(2): 484-502(1985) BibTeX

[34]

Ivan Hal Sudborough: Time and Tape Bounded Auxiliary Pushdown Automata. MFCS 1977: 493-503 BibTeX

[35]

Robert Endre Tarjan, Mihalis Yannakakis: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13(3): 566-579(1984) BibTeX

[36]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[37]

Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 BibTeX

[38]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[39]

Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

[40]

...

Referenced by

1. Jörg Flum, Markus Frick, Martin Grohe: Query Evaluation via Tree-Decompositions. ICDT 2001: 22-38
2. Moshe Y. Vardi: Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000: 76-85