On the representation and querying of sets of possible worlds
Authors:
Open Access
- 1 December 1987
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 16 (3) , 34-48
Abstract
We represent a set of possible worlds using an incomplete information database. The representation techniques that we study form a hierarchy, which generalizes relations of constants. This hierarchy ranges from the very simple Codd-table, (i e , a relation of constants and distinct variables called nulls, which stand for values present but unknown), to much more complex mechanisms involving views on conditioned-tables, (i e , queries on Codd-tables together with conditions). The views we consider are the queries that have polynomial data-complexity on complete information databases. Our conditions are conjunctions of equalities and inequalities. (1) We provide matching upper and lower bounds on the data-complexity of testing containement , membership , and uniqueness for sets of possible worlds and we fully classify these problems with respect to our representation hierarchy. The most surprising result in this classification is that it is complete in Π 2 p , whether a set of possible worlds represented by a Codd-table is a subset of a set of possible worlds represented by a Codd-table with one conjuction of inequalities. (2) We investigate the data-complexity of querying incomplete information databases. We examine both asking for certain facts and for possible facts . Our approach is algebraic but our bounds also apply to logical databases. We show that asking for a certain fact is coNP-complete, even for a fixed first order query on a Codd-table. We thus strengthen a lower bound of [16], who showed that this holds for a Codd-table with a conjunction of inequalities. For each fixed positive existential query we present a polynomial algorithm solving the bounded possible fact problem of this query on conditioned-tables. We show that our approach is, in a sense, the best possible, by deriving two NP-completeness lower bounds for the bounded possible fact problem when the fixed query contains either negation or recursion.Keywords
This publication has 12 references indexed in Scilit:
- Horn clause queries and generalizationsThe Journal of Logic Programming, 1985
- Querying logical databases1985
- Incomplete Information in Relational DatabasesJournal of the ACM, 1984
- The complexity of evaluating relational queriesInformation and Control, 1983
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- On the Complexity of Testing Implications of Functional and Join DependenciesJournal of the ACM, 1981
- On Databases with Incomplete InformationJournal of the ACM, 1981
- Testing the universal instance assumptionInformation Processing Letters, 1980
- Extending the database relational model to capture more meaningACM Transactions on Database Systems, 1979
- The polynomial-time hierarchyTheoretical Computer Science, 1976