From Complete to Incomplete Information and Back

Summary: Proposes World-set Algebra (WSA), a natural SQL/RA analog for incomplete information, enabling mapping from a complete database to multiple possible worlds. WSA is conservative over relational algebra for complete-to-complete queries, supports explicit uncertainty constructs, and enables efficient translation and optimization in RDBMS. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3894
Venue: SIGMOD
Year: 2007
Pagerank: 8.655056e-05
Overall Rank: 2,491 | 82.68%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
560	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00020141923
1,371	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012323502
3,251	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3215694e-05
3,505	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.0337815e-05
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
4,942	Query language support for incomplete information in the MayBMS system	2007	VLDB	5.8176224e-05
5,759	Indexing Correlated Probabilistic Databases	2009	SIGMOD	5.3392211e-05
5,796	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3240234e-05
5,823	Believe It or Not: Adding Belief Annotations to Databases	2009	VLDB	5.3129967e-05
6,321	Tiresias: A Demonstration of How-To Queries	2012	SIGMOD	5.112523e-05
6,838	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9109732e-05
7,561	Efficient Recovery of Missing Events	2013	VLDB	4.7102455e-05
9,274	Ranking Distributed Probabilistic Data	2009	SIGMOD	4.3646295e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
101	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.0004955674
1,297	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	0.00012758233
2,726	A Framework for Implementing Hypothetical Queries	1997	SIGMOD	8.2245669e-05
3,496	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.0397186e-05
4,699	Semantic Representations and Query Languages for Or-sets	1993	PODS	5.9885891e-05
7,405	The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data	2005	SIGMOD	4.7378885e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,502	Data Exchange and Incomplete Information	2006	PODS	7.0366655e-05
13,813	Querying Partially Sound and Complete Data Sources	2001	PODS	-
3,324	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2213002e-05
8,803	Coping with Incomplete Data: Recent Advances	2020	PODS	4.4470842e-05
2,769	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.1450304e-05
6,273	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1323078e-05
5,460	Relative Information Completeness	2009	PODS	5.4957751e-05
3,681	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.8492288e-05
7,393	Incomplete Information and Certain Answers in General Data Models	2011	PODS	4.7428879e-05
14,258	Completeness Information and Its Application to Query Processing	1986	VLDB	-