Back to papers
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
- 2329
- Venue
- SIGMOD
- Year
- 1987
- Pagerank
- 0.00016220185
- Overall Rank
- 827 | 94.25%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 20 of 20 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 119 |
Answering Queries using Humans, Algorithms and Databases |
2011 |
CIDR |
0.0004564788 |
| 1,707 |
Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach |
2008 |
SIGMOD |
0.00010816111 |
| 1,773 |
Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data |
2000 |
VLDB |
0.00010609478 |
| 2,268 |
OLAP Over Uncertain and Imprecise Data |
2005 |
VLDB |
9.1497575e-05 |
| 2,347 |
Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases |
1989 |
PODS |
8.9890664e-05 |
| 3,317 |
Data Functions, Datalog and Negation (Extended Abstract) |
1988 |
SIGMOD |
7.2283048e-05 |
| 3,360 |
Modeling and Querying Possible Repairs in Duplicate Detection |
2009 |
VLDB |
7.1742067e-05 |
| 4,171 |
Butterfly Counting on Uncertain Bipartite Graphs |
2022 |
VLDB |
6.3879236e-05 |
| 4,179 |
The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs |
2014 |
SIGMOD |
6.3800553e-05 |
| 5,548 |
Foundations of Uncertain-Data Integration |
2010 |
VLDB |
5.4446854e-05 |
| 5,758 |
Top-k Nearest Neighbor Search In Uncertain Data Series |
2015 |
VLDB |
5.339397e-05 |
| 6,273 |
Identifying the Extent of Completeness of Query Answers over Partially Complete Databases |
2015 |
SIGMOD |
5.1323078e-05 |
| 6,946 |
Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data |
2011 |
VLDB |
4.8909775e-05 |
| 7,542 |
Spheres of Influence for More Effective Viral Marketing |
2016 |
SIGMOD |
4.7156855e-05 |
| 7,634 |
ReStore - Neural Data Completion for Relational Databases |
2021 |
SIGMOD |
4.6911382e-05 |
| 8,087 |
Similarity Search and Mining in Uncertain Databases |
2010 |
VLDB |
4.5899317e-05 |
| 12,209 |
Completeness of Queries over Incomplete Databases |
2011 |
VLDB |
4.1945683e-05 |
| 12,378 |
Query Answering Techniques on Uncertain and Probabilistic Data |
2008 |
SIGMOD |
4.1945683e-05 |
| 12,934 |
Complexity of Query Processing in Databases with OR-Objects |
1989 |
PODS |
4.1945683e-05 |
| 12,946 |
A Family of Incomplete Relational Database Models |
1989 |
VLDB |
4.1945683e-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.
Semantically Similar Papers