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: he3bae6e011421f2a
Venue: SIGMOD
Year: 1987
Pagerank: 0.00012766663
Overall Rank: 971 | 93.48%
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
259	Answering Queries using Humans, Algorithms and Databases	2011	CIDR	0.00022916014
1,397	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010787659
1,756	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	9.7161465e-05
2,205	OLAP Over Uncertain and Imprecise Data	2005	VLDB	8.8519761e-05
2,966	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	7.8019358e-05
3,426	Modeling and Querying Possible Repairs in Duplicate Detection	2009	VLDB	7.3053186e-05
3,541	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2127593e-05
3,797	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.0139295e-05
3,821	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.0018898e-05
5,260	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	6.2041665e-05
5,652	Foundations of Uncertain-Data Integration	2010	VLDB	6.0492525e-05
6,109	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8825187e-05
6,148	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.8684233e-05
7,596	Spheres of Influence for More Effective Viral Marketing	2016	SIGMOD	5.48564e-05
7,710	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.471539e-05
8,529	Similarity Search and Mining in Uncertain Databases	2010	VLDB	5.3206989e-05
12,701	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9769913e-05
12,867	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.9769913e-05
13,425	Complexity of Query Processing in Databases with OR-Objects	1989	PODS	4.9769913e-05
13,437	A Family of Incomplete Relational Database Models	1989	VLDB	4.9769913e-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.00075910134
628	Database Relations with Null Values (Extended Abstract)	1982	PODS	0.00015434033
1,503	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010450365
2,459	Update Semantics for Incomplete Databases	1985	VLDB	8.431401e-05
3,808	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.0068633e-05

Semantically Similar Papers

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