On the Representation and Querying of Sets of Possible Worlds

Summary: Represents sets of possible worlds with incomplete-information DBs, from Codd-tables to conditioned-tables and views, with polynomial data complexity on complete data. Tight bounds for containment, membership, and uniqueness; Pi2^p-complete; coNP-complete for fixed FO facts; polynomial for bounded possible-facts with positive existential queries; NP-hard with negation or recursion. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2391
Venue: SIGMOD
Year: 1987
Pagerank: 0.00013041389
Overall Rank: 947 | 93.51%
DOI: 10.1145/38713.38724

Incoming Non-self Citations Over Time

Authors

1. Serge Abiteboul (INRIA)
2. Paris Kanellakis (Brown University)
3. Gosta Grahne (University of Helsinki)

BibTeX Citation

@inproceedings{abiteboul_sigmod87,
        title = {{On the Representation and Querying of Sets of Possible Worlds}},
        author = {Abiteboul, Serge and Kanellakis, Paris and Grahne, Gosta},
        series = {{SIGMOD} '87},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/38713.38724},
        url = {https://dl.acm.org/doi/10.1145/38713.38724},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
250	Answering Queries using Humans, Algorithms and Databases	2011	CIDR	0.00023261164
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
1,716	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	9.9330086e-05
2,172	OLAP Over Uncertain and Imprecise Data	2005	VLDB	9.0394311e-05
2,904	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	7.9757931e-05
3,371	Modeling and Querying Possible Repairs in Duplicate Detection	2009	VLDB	7.4697134e-05
3,476	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.3807586e-05
3,723	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.1725638e-05
3,738	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.1602939e-05
5,244	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	6.3018164e-05
5,513	Foundations of Uncertain-Data Integration	2010	VLDB	6.1909879e-05
6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	6.0050351e-05
6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8389373e-05
7,556	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.5997742e-05
7,588	Spheres of Influence for More Effective Viral Marketing	2016	SIGMOD	5.5907856e-05
8,355	Similarity Search and Mining in Uncertain Databases	2010	VLDB	5.445099e-05
12,404	Completeness of Queries over Incomplete Databases	2011	VLDB	5.093636e-05
12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	5.093636e-05
13,129	Complexity of Query Processing in Databases with OR-Objects	1989	PODS	5.093636e-05
13,141	A Family of Incomplete Relational Database Models	1989	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
10	Extending the Data Base Relational Model to Capture More Meaning	1979	SIGMOD	0.0007727299
613	Database Relations with Null Values (Extended Abstract)	1982	PODS	0.00015723523
1,467	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010687075
2,402	Update Semantics for Incomplete Databases	1985	VLDB	8.6276184e-05
3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.1534069e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
2	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
3	2,904	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS
4	7,563	Complexity Aspects of Various Semantics for Disjunctive Databases	1993	PODS
5	2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS
6	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
7	14,014	Querying Partially Sound and Complete Data Sources	2001	PODS
8	3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
9	8,699	Counting Problems over Incomplete Databases	2020	PODS
10	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS