Skip to Main content Skip to Navigation
Journal articles

Reachability and connectivity queries in constraint databases

Michael Benedikt 1 Martin Grohe 2 Leonid Libkin 3 Luc Segoufin 4 
4 GEMO - Integration of data and knowledge distributed over the web
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Friday, June 5, 2020 - 1:36:29 PM
Last modification on : Sunday, June 26, 2022 - 12:15:58 PM


Files produced by the author(s)




Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin. Reachability and connectivity queries in constraint databases. Journal of Computer and System Sciences, Elsevier, 2003, 66 (1), pp.169-206. ⟨10.1016/S0022-0000(02)00034-X⟩. ⟨hal-02796363⟩



Record views


Files downloads