The complexity of querying indefinite data about linearly ordered domains

DOI10.1006/JCSS.1997.1455MaRDI QIDQ676427zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

partial orderPTIME subproblemsquery answering

Mathematics Subject Classification ID

Database theory (68P15)

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

Cites work

• A propositional modal logic of time intervals
• Alternation
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Complexity and algorithms for reasoning about time
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3914378 (Why is no real title available?)
• scientific article; zbMATH DE number 67825 (Why is no real title available?)
• scientific article; zbMATH DE number 3497901 (Why is no real title available?)
• scientific article; zbMATH DE number 3599517 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maintaining knowledge about temporal intervals
• Model theory
• Nonconstructive advances in polynomial-time complexity
• Nonconstructive tools for proving polynomial-time decidability
• On conjunctive queries containing inequalities
• On the representation and querying of sets of possible worlds
• Querying logical databases
• Recursively indefinite databases
• The theory of well-quasi-ordering: a frequently discovered concept

Cited in

(29)

• Verification of knowledge bases based on containment checking
• First-order queries on databases embedded in an infinite structure
• Constrained dependencies
• XML with data values: Typechecking revisited.
• Querying temporal and spatial constraint networks in PTIME
• A technique for proving decidability of containment and equivalence of linear constraint queries
• Constraint-generating dependencies
• A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
• On the complexity of tree pattern containment with arithmetic comparisons
• Computing possible and certain answers over order-incomplete data
• Answering conjunctive queries with inequalities
• Certain answers over incomplete XML documents: extending tractability boundary
• Querying incomplete information in RDF with SPARQL
• Data sufficiency for queries on cache
• An extension of the relational data model to incorporate ordered domains
• On conjunctive queries containing inequalities
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• Query answering with transitive and linear-ordered data
• 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
• scientific article; zbMATH DE number 2242592 (Why is no real title available?)
• The query complexity of order-finding
• Possible and certain answers for queries over order-incomplete data
• Query containment under bag and bag-set semantics
• Conjunctive query containment with respect to views and constraints
• Conjunctive queries with comparisons
• Rewriting queries using views in the presence of arithmetic comparisons

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)