Title: Reachability and Connectivity Queries in Constraint Databases

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

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.