Reachability and connectivity queries in constraint databases
Michael Benedikt, Martin Grohe, Leonid O. Libkin, Luc Segoufin · 2000
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.