๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Reachability and connectivity queries in constraint databases

โœ Scribed by Michael Benedikt; Martin Grohe; Leonid Libkin; Luc Segoufin


Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
401 KB
Volume
66
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis


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.


๐Ÿ“œ SIMILAR VOLUMES


Querying temporal and spatial constraint
โœ Manolis Koubarakis; Spiros Skiadopoulos ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 311 KB

We start with the assumption that temporal and spatial knowledge usually captured by constraint networks can be represented and queried more effectively by using the scheme of indefinite constraint databases. Because query evaluation in this scheme is in general a hard computational problem, we seek

An Indexing and Retrieval Mechanism for
โœ Guang-Ho Cha; Chin-Wan Chung ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 563 KB

A content-based image retrieval mechanism to support complex similarity queries is presented. The image content is defined by three kinds of features: quantifiable features describing the visual information, nonquantifiable features describing the semantic information, and keywords describing more a