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 orderquery answeringPTIME subproblems

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

• 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?)
• 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
• 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

(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
• Certain answers over incomplete XML documents: extending tractability boundary
• Computing possible and certain answers over order-incomplete data
• 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
• Rewriting queries using views in the presence of arithmetic comparisons
• scientific article; zbMATH DE number 2242592 (Why is no real title available?)
• Answering conjunctive queries with inequalities
• Query containment under bag and bag-set semantics
• Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• 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)