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: 3895
Venue: SIGMOD
Year: 2007
Pagerank: 8.6470623e-05
Overall Rank: 2,493 | 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.0002012328
1,376	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012315734
3,256	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3135363e-05
3,509	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.0283775e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
4,941	Query language support for incomplete information in the MayBMS system	2007	VLDB	5.8129205e-05
5,767	Indexing Correlated Probabilistic Databases	2009	SIGMOD	5.3341473e-05
5,807	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3189104e-05
5,837	Believe It or Not: Adding Belief Annotations to Databases	2009	VLDB	5.3078955e-05
6,320	Tiresias: A Demonstration of How-To Queries	2012	SIGMOD	5.107614e-05
6,837	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9063121e-05
7,562	Efficient Recovery of Missing Events	2013	VLDB	4.7057229e-05
9,280	Ranking Distributed Probabilistic Data	2009	SIGMOD	4.3604461e-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.00067607389
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
103	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00049520051
1,294	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	0.0001274686
2,730	A Framework for Implementing Hypothetical Queries	1997	SIGMOD	8.217357e-05
3,503	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.0332465e-05
4,699	Semantic Representations and Query Languages for Or-sets	1993	PODS	5.98279e-05
7,405	The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data	2005	SIGMOD	4.7333266e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,507	Data Exchange and Incomplete Information	2006	PODS	7.0299158e-05
13,827	Querying Partially Sound and Complete Data Sources	2001	PODS	-
3,325	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2149375e-05
2,776	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.1371926e-05
8,802	Coping with Incomplete Data: Recent Advances	2020	PODS	4.4428211e-05
6,271	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1273783e-05
5,467	Relative Information Completeness	2009	PODS	5.4904942e-05
3,683	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.84255e-05
7,391	Incomplete Information and Certain Answers in General Data Models	2011	PODS	4.7383385e-05
14,272	Completeness Information and Its Application to Query Processing	1986	VLDB	-