On the representation and querying of sets of possible worlds

DOI10.1016/0304-3975(51)90007-2zbMath0741.68039OpenAlexW2050171146MaRDI QIDQ1174717

Gösta Grahne, Serge Abiteboul, Paris C. Kanellakis

Publication date: 25 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(51)90007-2

zbMATH Keywords

data complexityconditioned-tablesincomplete information database

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Related Items (25)

Certain answers over incomplete XML documents: extending tractability boundary ⋮ Constraint satisfaction with an object-oriented knowledge representation language ⋮ Querying incomplete information in RDF with SPARQL ⋮ Intuitionistic interpretation of deductive databases with incomplete information ⋮ Certain answers as objects and knowledge ⋮ Querying disjunctive databases through nonmonotonic logics ⋮ XML Schema Mappings ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Supporting various top-k queries over uncertain datasets ⋮ Data cleaning and query answering with matching dependencies and matching functions ⋮ On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees ⋮ An initial approach to the evaluation of possibilistic queries addressed to possibilistic databases. ⋮ Efficient processing of probabilistic set-containment queries on uncertain set-valued data ⋮ On the semantics of top-\(k\) ranking for objects with uncertain data ⋮ World-set decompositions: Expressiveness and efficient algorithms ⋮ The complexity of querying indefinite data about linearly ordered domains ⋮ Recursively indefinite databases ⋮ On indexing evidential data ⋮ Data exchange and schema mappings in open and closed worlds ⋮ Towards an algebraic theory of information integration ⋮ About the processing of possibilistic queries involving a difference operation ⋮ Reasoning about partially ordered events ⋮ Fragments of Bag Relational Algebra: Expressiveness and Certain Answers ⋮ Querying temporal and spatial constraint networks in PTIME ⋮ Negative Knowledge for Certain Query Answers

Cites Work

• Unnamed Item
• Querying logical databases
• Database relations with null values
• In memoriam Witold Lipski, jun. (1949--1985)
• Testing the universal instance assumption
• The polynomial-time hierarchy
• Structure and complexity of relational queries
• The complexity of evaluating relational queries
• Horn clause queries and generalizations
• Incomplete Information in Relational Databases
• On Databases with Incomplete Information
• On the Complexity of Testing Implications of Functional and Join Dependencies

This page was built for publication: On the representation and querying of sets of possible worlds