Reachability and connectivity queries in constraint databases

DOI10.1016/S0022-0000(02)00034-XzbMath1026.68036OpenAlexW2714643361MaRDI QIDQ1394800

Luc Segoufin, Martin Grohe, Michael Benedikt, Leonid O. Libkin

Publication date: 25 June 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00034-x

zbMATH Keywords

connectivity propertiesreachability properties

Mathematics Subject Classification ID

Database theory (68P15)

Related Items (4)

On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets

Cites Work

• The complexity of elementary algebra and geometry
• Model theory.
• Topological queries in spatial databases
• Description of the connected components of a semialgebraic set in single exponential time
• Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
• Adding a path connectedness operator to \(FO+poly(linear)\)
• Querying spatial databases via topological invariants
• O-minimal hybrid systems.
• Relational queries over interpreted structures
• Definable Sets in Ordered Structures. III
• Languages that Capture Complexity Classes
• Relational expressive power of constraint query languages
• First-Order Queries on Finite Structures Over the Reals
• Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reachability and connectivity queries in constraint databases