The complexity of querying indefinite data about linearly ordered domains

DOI10.1006/JCSS.1997.1455zbMATH Open0876.68035OpenAlexW2031639195MaRDI QIDQ676427FDOQ676427

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

Recommendations

• The complexity of query evaluation in indefinite temporal constraint databases
• Computing possible and certain answers over order-incomplete data
• A linear time algorithm for monadic querying of indefinite data over linearly ordered domains

zbMATH Keywords

partial orderquery answeringPTIME subproblems

Mathematics Subject Classification ID

Database theory (68P15)

Cites Work

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

Cited In (28)

• Conjunctive query containment with respect to views and constraints
• On conjunctive queries containing inequalities
• Decidable containment of recursive queries
• Possible and certain answers for queries over order-incomplete data
• Computing possible and certain answers over order-incomplete data
• Certain answers over incomplete XML documents: extending tractability boundary
• Constraint-generating dependencies
• On the complexity of tree pattern containment with arithmetic comparisons
• A technique for proving decidability of containment and equivalence of linear constraint queries
• On the finite controllability of conjunctive query answering in databases under open-world assumption
• Querying incomplete information in RDF with SPARQL
• Data exchange: semantics and query answering
• The query complexity of order-finding
• A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
• XML with data values: Typechecking revisited.
• Data sufficiency for queries on cache
• Verification of knowledge bases based on containment checking
• An extension of the relational data model to incorporate ordered domains
• Constrained dependencies
• First-order queries on databases embedded in an infinite structure
• Query answering with transitive and linear-ordered data
• Title not available (Why is that?)
• Rewriting queries using views in the presence of arithmetic comparisons
• Answering conjunctive queries with inequalities
• Query containment under bag and bag-set semantics
• Title not available (Why is that?)
• Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
• Querying temporal and spatial constraint networks in PTIME

This page was built for publication: The complexity of querying indefinite data about linearly ordered domains

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