The complexity of querying indefinite data about linearly ordered domains

DOI10.1006/jcss.1997.1455zbMath0876.68035OpenAlexW2031639195MaRDI QIDQ676427

Ron van der Meyden

Publication date: 18 March 1997

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

Full work available at URL: https://doi.org/10.1006/jcss.1997.1455

zbMATH Keywords

partial orderquery answeringPTIME subproblems

Mathematics Subject Classification ID

Database theory (68P15)

Related Items

Certain answers over incomplete XML documents: extending tractability boundary, Querying incomplete information in RDF with SPARQL, Data sufficiency for queries on cache, A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Rewriting queries using views in the presence of arithmetic comparisons, Answering conjunctive queries with inequalities, Constrained dependencies, XML with data values: Typechecking revisited., On the complexity of tree pattern containment with arithmetic comparisons, Query containment under bag and bag-set semantics, Conjunctive query containment with respect to views and constraints, Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons, On the finite controllability of conjunctive query answering in databases under open-world assumption, Decidable containment of recursive queries, Data exchange: semantics and query answering, A technique for proving decidability of containment and equivalence of linear constraint queries, Constraint-generating dependencies, Verification of knowledge bases based on containment checking, Computing possible and certain answers over order-incomplete data, Querying temporal and spatial constraint networks in PTIME

Cites Work

• Maintaining knowledge about temporal intervals
• Querying logical databases
• Recursively indefinite databases
• Nonconstructive advances in polynomial-time complexity
• On the representation and querying of sets of possible worlds
• Model theory
• The theory of well-quasi-ordering: a frequently discovered concept
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• On conjunctive queries containing inequalities
• Nonconstructive tools for proving polynomial-time decidability
• Alternation
• Complexity and algorithms for reasoning about time
• A propositional modal logic of time intervals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item