The complexity of query evaluation in indefinite temporal constraint databases

DOI10.1016/S0304-3975(96)00124-7zbMath0887.68029OpenAlexW2091084325MaRDI QIDQ1369238

Manolis Koubarakis

Publication date: 19 October 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00124-7

zbMATH Keywords

constraint databasequery evaluation\(\mathcal L\)-constraint databases

Mathematics Subject Classification ID

Database theory (68P15)

Related Items

Querying incomplete information in RDF with SPARQL ⋮ A linear time algorithm for monadic querying of indefinite data over linearly ordered domains ⋮ Indexing moving points ⋮ On the consistency of cardinal direction constraints ⋮ Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning ⋮ Constraint-generating dependencies ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ Querying temporal and spatial constraint networks in PTIME ⋮ Composing cardinal direction relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Querying logical databases
• A closed-form evaluation for Datalog queries with integer (gap)-order constraints
• Foundations of a functional approach to knowledge representation
• Real addition and the polynomial hierarchy
• On time-space classes and their relation to the theory of real addition
• The complexity of logical theories
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• On the representation and querying of sets of possible worlds
• Temporal constraint networks
• The problem of incomplete information in relational databases
• The polynomial-time hierarchy
• An efficient decision procedure for the theory of rational order
• The computational complexity of logical theories
• Principles and practice of constraint programming. 2nd international workshop, PPCP '94, Rosario, Orcas Island, Washington, DC, USA, May 2-4, 1994. Proceedings
• Intuitionistic interpretation of deductive databases with incomplete information
• Model theory
• Structure and complexity of relational queries
• Incomplete Information in Relational Databases
• A Decision Procedure for the First Order Theory of Real Addition with Order
• Presburger arithmetic with bounded quantifier alternation
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning