The complexity of query evaluation in indefinite temporal constraint databases

DOI10.1016/S0304-3975(96)00124-7zbMATH Open0887.68029OpenAlexW2091084325MaRDI QIDQ1369238FDOQ1369238

Authors: 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

Recommendations

• Querying temporal constraint networks: A unifying approach
• Querying temporal and spatial constraint networks in PTIME
• Publication:4945218
• Publication:4508935
• The Evaluation and the Computational Complexity of Datalog Queries of Boolean Constraint Databases

zbMATH Keywords

query evaluationconstraint database\(\mathcal L\)-constraint databases

Mathematics Subject Classification ID

Database theory (68P15)

Cites Work

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

Cited In (12)

• Constraint-generating dependencies
• Backtracking algorithms for disjunctions of temporal constraints
• Time-bounded query generator for constraint acquisition
• On the consistency of cardinal direction constraints
• Querying incomplete information in RDF with SPARQL
• Title not available (Why is that?)
• Indexing moving points
• A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
• Querying temporal constraint networks: A unifying approach
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
• Composing cardinal direction relations
• Querying temporal and spatial constraint networks in PTIME

This page was built for publication: The complexity of query evaluation in indefinite temporal constraint databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1369238)