dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Hypertree Decompositions and Tractable Queries.

Georg Gottlob, Nicola Leone, Francesco Scarcello: Hypertree Decompositions and Tractable Queries. PODS 1999: 21-32
@inproceedings{DBLP:conf/pods/GottlobLS99,
  author    = {Georg Gottlob and
               Nicola Leone and
               Francesco Scarcello},
  editor    = {Victor Vianu and
               Christos H. Papadimitriou},
  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, USA},
  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

CDROM Version: Load the CDROM "DiSC, Volume 2 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Victor Vianu, Christos H. Papadimitriou (Eds.): Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, USA. ACM Press 1999, ISBN 1-58113-062-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Stefan Arnborg: Efficient Algorithms for Combinatorial Problems with Bounded Decomposability - A Survey. BIT 25(1): 2-23(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Wolfgang Bibel: Constraint Satisfaction from a Deductive Viewpoint. Artif. Intell. 35(3): 401-413(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Hans L. Bodlaender: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput. 25(6): 1305-1317(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Alessandro D'Atri, Marina Moscarini: Recognition Algorithms and Design Methodologies for Acyclic Database Schemes. Advances in Computing Research 3: 43-67(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
...
[12]
Rina Dechter, Judea Pearl: Tree Clustering for Constraint Networks. Artif. Intell. 38(3): 353-366(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Eugene C. Freuder: A Sufficient Condition for Backtrack-Bounded Search. J. ACM 32(4): 755-761(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Georg Gottlob, Nicola Leone, Francesco Scarcello: The Complexity of Acyclic Conjunctive Queries. FOCS 1998: 706-715 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
...
[21]
...
[22]
Sheila A. Greibach: The Hardest Context-Free Language. SIAM J. Comput. 2(4): 304-310(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Marc Gyssens, Peter Jeavons, David A. Cohen: Decomposing Constraint Satisfaction Problems Using Database Techniques. Artif. Intell. 66(1): 57-89(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Marc Gyssens, Jan Paredaens: A Decomposition Methodology for Cyclic Databases. Advances in Data Base Theory 1982: 85-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Peter Jeavons, David A. Cohen, Marc Gyssens: Closure properties of constraints. J. ACM 44(4): 527-548(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
...
[27]
Phokion G. Kolaitis, Moshe Y. Vardi: Conjunctive-Query Containment and Constraint Satisfaction. PODS 1998: 205-213 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
Xiaolei Qian: Query Folding. ICDE 1996: 48-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[31]
Neil Robertson, Paul D. Seymour: Graph Minors. II. Algorithmic Aspects of Tree-Width. J. Algorithms 7(3): 309-322(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
Walter L. Ruzzo: Tree-Size Bounded Alternation. J. Comput. Syst. Sci. 21(2): 218-235(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[33]
Sven Skyum, Leslie G. Valiant: A Complexity Theory Based on Boolean Algebra. J. ACM 32(2): 484-502(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[34]
Ivan Hal Sudborough: Time and Tape Bounded Auxiliary Pushdown Automata. MFCS 1977: 493-503 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[36]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[37]
Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[38]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[39]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[40]
...

Last update Fri Sep 14 17:28:37 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page