Reachability and Connectivity Queries in Constraint Databases.

Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin: Reachability and Connectivity Queries in Constraint Databases. PODS 2000: 104-115
  author    = {Michael Benedikt and
               Martin Grohe and
               Leonid Libkin and
               Luc Segoufin},
  title     = {Reachability and Connectivity Queries in Constraint Databases},
  booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
               on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
  publisher = {ACM},
  year      = {2000},
  isbn      = {1-58113-214-X},
  pages     = {104-115},
  ee        = {, db/conf/pods/BenediktGLS00.html},
  crossref  = {DBLP:conf/pods/00},
  bibsource = {DBLP,}


Copyright © 2000 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.


Printed Edition

Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, May 15-17, 2000, Dallas, Texas, USA. ACM 2000, ISBN 1-58113-214-X
Contents BibTeX

Online Edition: ACM Digital Library


Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
Foto N. Afrati, Stavros S. Cosmadakis, Stéphane Grumbach, Gabriel M. Kuper: Linear vs Polynomial Constraints in Database Query Languages. PPCP 1994: 181-192 BibTeX
Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. J. ACM 45(1): 1-34(1998) BibTeX
Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98 BibTeX
Michael Ben-Or, Dexter Kozen, John H. Reif: The Complexity of Elementary Algebra and Geometry. J. Comput. Syst. Sci. 32(2): 251-264(1986) BibTeX
E. Allen Emerson: Temporal and Modal Logic. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 995-1072 BibTeX
Erich Grädel, Stephan Kreutzer: Descriptive Complexity Theory for Constraint Databases. CSL 1999: 67-81 BibTeX
Stéphane Grumbach, Gabriel M. Kuper: Tractable Recursion over Geometric Data. CP 1997: 450-462 BibTeX
Thomas A. Henzinger: The Theory of Hybrid Automata. LICS 1996: 278-292 BibTeX
Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX
Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: On Topological Elementary Equivalence of Spatial Databases. ICDT 1997: 432-446 BibTeX
Bart Kuijpers, Marc Smits: On Expressing Topological Connectivity in Spatial Datalog. CDB 1997: 116-133 BibTeX
Bart Kuijpers, Jan Van den Bussche: On Capturing First-Order Topological Properties of Planar Spatial Databases. ICDT 1999: 187-198 BibTeX
Gabriel M. Kuper, Leonid Libkin, Jan Paredaens: Introduction. Constraint Databases 2000: 1-16 BibTeX
Gerardo Lafferriere, George J. Pappas, Sergio Yovine: A New Class of Decidable Hybrid Systems. HSCC 1999: 137-151 BibTeX
Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92 BibTeX
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-Order Queries on Finite Structures Over the Reals. SIAM J. Comput. 27(6): 1747-1763(1998) BibTeX
Peter Z. Revesz: Datalog and Constraints. Constraint Databases 2000: 155-170 BibTeX
Luc Segoufin, Victor Vianu: Querying Spatial Databases via Topological Invariants. PODS 1998: 89-98 BibTeX

Referenced by

  1. Jan Van den Bussche: Constraint databases: A tutorial introduction. SIGMOD Record 29(3): 44-51(2000)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:25 2009