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
- 2330
- Venue
- SIGMOD
- Year
- 1987
- Pagerank
- 0.00016225326
- Overall Rank
- 823 | 94.29%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 20 of 20 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 118 |
Answering Queries using Humans, Algorithms and Databases |
2011 |
CIDR |
0.00045860394 |
| 1,703 |
Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach |
2008 |
SIGMOD |
0.00010820803 |
| 1,771 |
Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data |
2000 |
VLDB |
0.00010606967 |
| 2,273 |
OLAP Over Uncertain and Imprecise Data |
2005 |
VLDB |
9.1447774e-05 |
| 2,352 |
Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases |
1989 |
PODS |
8.9815852e-05 |
| 3,320 |
Data Functions, Datalog and Negation (Extended Abstract) |
1988 |
SIGMOD |
7.2212998e-05 |
| 3,366 |
Modeling and Querying Possible Repairs in Duplicate Detection |
2009 |
VLDB |
7.1671634e-05 |
| 4,158 |
Butterfly Counting on Uncertain Bipartite Graphs |
2022 |
VLDB |
6.3898204e-05 |
| 4,165 |
The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs |
2014 |
SIGMOD |
6.3843974e-05 |
| 5,556 |
Foundations of Uncertain-Data Integration |
2010 |
VLDB |
5.4394558e-05 |
| 5,763 |
Top-k Nearest Neighbor Search In Uncertain Data Series |
2015 |
VLDB |
5.3358283e-05 |
| 6,271 |
Identifying the Extent of Completeness of Query Answers over Partially Complete Databases |
2015 |
SIGMOD |
5.1273783e-05 |
| 6,865 |
Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data |
2011 |
VLDB |
4.9002126e-05 |
| 7,540 |
Spheres of Influence for More Effective Viral Marketing |
2016 |
SIGMOD |
4.7111607e-05 |
| 7,634 |
ReStore - Neural Data Completion for Relational Databases |
2021 |
SIGMOD |
4.6866388e-05 |
| 8,084 |
Similarity Search and Mining in Uncertain Databases |
2010 |
VLDB |
4.5861412e-05 |
| 12,217 |
Completeness of Queries over Incomplete Databases |
2011 |
VLDB |
4.1905499e-05 |
| 12,386 |
Query Answering Techniques on Uncertain and Probabilistic Data |
2008 |
SIGMOD |
4.1905499e-05 |
| 12,944 |
Complexity of Query Processing in Databases with OR-Objects |
1989 |
PODS |
4.1905499e-05 |
| 12,956 |
A Family of Incomplete Relational Database Models |
1989 |
VLDB |
4.1905499e-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