Querying logical databases

DOI10.1016/0022-0000(86)90016-4MaRDI QIDQ579967zbMATH OpenOpenAlexFDO

Authors Moshe Y. Vardi

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0022-0000(86)90016-4

zbMATH Keywords

approximation algorithmclosed-world databases with unknown valuescomplexity of evaluating queries in logical databasesdatabase managementrelational databases

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Review text

We study here the complexity of evaluating queries in logical databases. We focus on Reither's model of closed-world databases with unknown values. We show that in this setting query evaluation is harder than query evaluation for physical databases. For example, while 1st-order queries over physical databases can be evaluated in logarithmic space, evaluation of 1st-order queries in the studied model is co-NP-complete. We describe an approximation algorithm for query evaluation that enables one to implement a logical database on the top of a standard database management system.

Recommendations

• scientific article; zbMATH DE number 18538
• scientific article; zbMATH DE number 219205
• scientific article; zbMATH DE number 4049159
• The Evaluation and the Computational Complexity of Datalog Queries of Boolean Constraint Databases
• Implementation of logical query languages for databases

Cites work

• A logic for default reasoning
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• In memoriam Witold Lipski, jun. (1949--1985)
• Null values in a relational data base
• Structure and complexity of relational queries
• The polynomial-time hierarchy
• The Semantics of Predicate Logic as a Programming Language

Cited in

(17)

• Dynamic query interpretation in relational databases
• On the representation and querying of sets of possible worlds
• The complexity of propositional closed world reasoning and circumscription
• Intuitionistic interpretation of deductive databases with incomplete information
• Querying disjunctive databases through nonmonotonic logics
• Incomplete deductive databases
• The complexity of query evaluation in indefinite temporal constraint databases
• Tractable reasoning via approximation
• Simulating Dynamic Systems Using Linear Time Calculus Theories
• scientific article; zbMATH DE number 4049159 (Why is no real title available?)
• scientific article; zbMATH DE number 4064541 (Why is no real title available?)
• scientific article; zbMATH DE number 2020203 (Why is no real title available?)
• Paraconsistent logic and query answering in inconsistent databases
• The complexity of querying indefinite data about linearly ordered domains
• Recursively indefinite databases
• A propositional encoding for first-order clausal entailment over infinitely many constants
• Towards an algebraic theory of information integration

This page was built for publication: Querying logical databases

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