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.00012772086
Overall Rank: 970 | 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.00022923243
1,396	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.0001079253
1,755	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	9.7206727e-05
2,204	OLAP Over Uncertain and Imprecise Data	2005	VLDB	8.8558582e-05
2,965	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	7.8051404e-05
3,426	Modeling and Querying Possible Repairs in Duplicate Detection	2009	VLDB	7.3087723e-05
3,541	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2161746e-05
3,794	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.0172514e-05
3,820	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.005206e-05
5,275	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	6.2005202e-05
5,651	Foundations of Uncertain-Data Integration	2010	VLDB	6.0521173e-05
6,108	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8850424e-05
6,146	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.8712024e-05
7,589	Spheres of Influence for More Effective Viral Marketing	2016	SIGMOD	5.4882381e-05
7,704	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.4741304e-05
8,522	Similarity Search and Mining in Uncertain Databases	2010	VLDB	5.3232189e-05
12,695	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9793485e-05
12,861	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.9793485e-05
13,419	Complexity of Query Processing in Databases with OR-Objects	1989	PODS	4.9793485e-05
13,431	A Family of Incomplete Relational Database Models	1989	VLDB	4.9793485e-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.00075944947
628	Database Relations with Null Values (Extended Abstract)	1982	PODS	0.0001544126
1,503	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010455233
2,459	Update Semantics for Incomplete Databases	1985	VLDB	8.4353518e-05
3,807	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.0097907e-05

Semantically Similar Papers

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