Reachability and Connectivity Queries in Constraint Databases.

@inproceedings{DBLP:conf/pods/BenediktGLS00,
  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,
               USA},
  publisher = {ACM},
  year      = {2000},
  isbn      = {1-58113-214-X},
  pages     = {104-115},
  ee        = {http://doi.acm.org/10.1145/335168.335213, db/conf/pods/BenediktGLS00.html},
  crossref  = {DBLP:conf/pods/00},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

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]

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

[3]

...

[4]

Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. J. ACM 45(1): 1-34(1998) BibTeX

[5]

...

[6]

Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98 BibTeX

[7]

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

[8]

...

[9]

...

[10]

...

[11]

E. Allen Emerson: Temporal and Modal Logic. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 995-1072 BibTeX

[12]

...

[13]

...

[14]

Erich Grädel, Stephan Kreutzer: Descriptive Complexity Theory for Constraint Databases. CSL 1999: 67-81 BibTeX

[15]

Stéphane Grumbach, Gabriel M. Kuper: Tractable Recursion over Geometric Data. CP 1997: 450-462 BibTeX

[16]

...

[17]

Thomas A. Henzinger: The Theory of Hybrid Automata. LICS 1996: 278-292 BibTeX

[18]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[19]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX

[20]

Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: On Topological Elementary Equivalence of Spatial Databases. ICDT 1997: 432-446 BibTeX

[21]

Bart Kuijpers, Marc Smits: On Expressing Topological Connectivity in Spatial Datalog. CDB 1997: 116-133 BibTeX

[22]

Bart Kuijpers, Jan Van den Bussche: On Capturing First-Order Topological Properties of Planar Spatial Databases. ICDT 1999: 187-198 BibTeX

[23]

Gabriel M. Kuper, Leonid Libkin, Jan Paredaens: Introduction. Constraint Databases 2000: 1-16 BibTeX

[24]

Gerardo Lafferriere, George J. Pappas, Sergio Yovine: A New Class of Decidable Hybrid Systems. HSCC 1999: 137-151 BibTeX

[25]

...

[26]

Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92 BibTeX

[27]

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

[28]

...

[29]

Peter Z. Revesz: Datalog and Constraints. Constraint Databases 2000: 155-170 BibTeX

[30]

Luc Segoufin, Victor Vianu: Querying Spatial Databases via Topological Invariants. PODS 1998: 89-98 BibTeX

[31]

...

[32]

...

Referenced by

1. Jan Van den Bussche: Constraint databases: A tutorial introduction. SIGMOD Record 29(3): 44-51(2000)