Welcome to D
SIGMOD'00
PODS'00
= PODS'00 Webs
= Plenary Talk
<<< = PODS'00 Pape>>>
SIGMOD Recor
CIKM 2000/CI
COMAD 2000
Data Enginee
DL 2000
DPDJ
EDBT 2000
Hypertext 20
ICDE 2000
KDD 2000
KDD Explorat
KRDB 2000
SBBD 2000
SIGIR 2000
SIGIR Forum
SSDBM 2000
TODS
VLDB'00
VLDBJ

Reachability and Connectivity Queries in Constraint Databases


Michael Benedikt, Martin Grohe, Leonid Libkin, and Luc Segoufin

  View Paper (PDF)  

Return to Spatial and Constraint Databases


Abstract

It is known that standard query languages for constraint databases lack the power to express connectivity properties. Such properties are important in the context of geographical databases, where one naturally wishes to ask queries about connectivity (what are the connected components of a given set?) or reachability (is there a path from A to B that lies entirely in a given region?). No existing constraint query languages that allow closed form evaluation can express these properties.

In the first part of the paper, we show that in principle there is no obstacle to getting closed languages that can express connectivity and reachability queries. In fact, we show that adding any topological property to standard languages like FO + LIN and FO+POLY results in a closed language. In the second part of the paper, we look for tractable closed languages for expressing reachability and connectivity queries. We introduce path logic, which allows one to state properties of paths with respect to given regions. We show that it is closed, has polynomial time data complexity for linear and polynomial constraints, and can express a large number of reachability properties beyond simple connectivity. Query evaluation in the logic involves obtaining a discrete abstraction of a continuous path, and model-checking of temporal formulae on the discrete structure.


References


Note: References link to DBLP on the Web.

[1]
Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
[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
[3]
...
[4]
Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong : Relational Expressive Power of Constraint Query Languages. JACM 45(1) : 1-34(1998)
[5]
...
[6]
Michael Benedikt , Leonid Libkin : Languages for Relational Databases over Interpreted Structures. PODS 1997 : 87-98
[7]
Michael Ben-Or , Dexter Kozen , John H. Reif : The Complexity of Elementary Algebra and Geometry. JCSS 32(2) : 251-264(1986)
[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
[12]
...
[13]
...
[14]
Erich Grädel , Stephan Kreutzer : Descriptive Complexity Theory for Constraint Databases. CSL 1999 : 67-81
[15]
Stéphane Grumbach , Gabriel M. Kuper : Tractable Recursion over Geometric Data. CP 1997 : 450-462
[16]
...
[17]
Thomas A. Henzinger : The Theory of Hybrid Automata. LICS 1996 : 278-292
[18]
Neil Immerman : Languages that Capture Complexity Classes. SIAM J. Comput. 16(4) : 760-778(1987)
[19]
Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz : Constraint Query Languages. JCSS 51(1) : 26-52(1995)
[20]
Bart Kuijpers , Jan Paredaens , Jan Van den Bussche : On Topological Elementary Equivalence of Spatial Databases. ICDT 1997 : 432-446
[21]
Bart Kuijpers , Marc Smits : On Expressing Topological Connectivity in Spatial Datalog. CDB 1997 : 116-133
[22]
Bart Kuijpers , Jan Van den Bussche : On Capturing First-Order Topological Properties of Planar Spatial Databases. ICDT 1999 : 187-198
[23]
Gabriel M. Kuper , Leonid Libkin , Jan Paredaens : Introduction. Constraint Databases 2000 : 1-16
[24]
Gerardo Lafferriere , George J. Pappas , Sergio Yovine : A New Class of Decidable Hybrid Systems. HSCC 1999 : 137-151
[25]
...
[26]
Christos H. Papadimitriou , Dan Suciu , Victor Vianu : Topological Queries in Spatial Databases. PODS 1996 : 81-92
[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)
[28]
...
[29]
Peter Z. Revesz : Datalog and Constraints. Constraint Databases 2000 : 155-170
[30]
Luc Segoufin , Victor Vianu : Querying Spatial Databases via Topological Invariants. PODS 1998 : 89-98
[31]
...
[32]
...

Referenced by

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

BIBTEX


@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},
   crossref  = {DBLP:conf/pods/00},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.