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: 3956
Venue: SIGMOD
Year: 2007
Pagerank: 8.4818577e-05
Overall Rank: 2,514 | 82.76%
DOI: 10.1145/1247480.1247559

Incoming Non-self Citations Over Time

Authors

1. Lyublena Antova (Saarland University)
2. Christoph Koch (Saarland University)
3. Dan Olteanu (Saarland University)

BibTeX Citation

@inproceedings{antova_sigmod07,
        title = {{From Complete to Incomplete Information and Back}},
        author = {Antova, Lyublena and Koch, Christoph and Olteanu, Dan},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247559},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247559},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
494	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017526549
1,096	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012189583
3,483	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.372823e-05
3,590	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.2801454e-05
4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.8810237e-05
4,653	Query language support for incomplete information in the MayBMS system	2007	VLDB	6.5850987e-05
5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD	6.2142725e-05
5,586	Believe It or Not: Adding Belief Annotations to Databases	2009	VLDB	6.1598576e-05
6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.9693818e-05
6,638	Tiresias: A Demonstration of How-To Queries	2012	SIGMOD	5.8168173e-05
6,712	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.7962014e-05
8,008	Efficient Recovery of Missing Events	2013	VLDB	5.5077375e-05
9,425	Ranking Distributed Probabilistic Data	2009	SIGMOD	5.2711481e-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
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
1,690	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	0.00010001011
3,002	A Framework for Implementing Hypothetical Queries	1997	SIGMOD	7.8667842e-05
3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.1534069e-05
4,522	Semantic Representations and Query Languages for Or-sets	1993	PODS	6.6466406e-05
6,359	The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data	2005	SIGMOD	5.9019991e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,934	Data Exchange and Incomplete Information	2006	PODS
2	14,014	Querying Partially Sound and Complete Data Sources	2001	PODS
3	3,433	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS
4	2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS
5	8,837	Coping with Incomplete Data: Recent Advances	2020	PODS
6	6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD
7	5,617	Relative Information Completeness	2009	PODS
8	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
9	7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS
10	14,459	Completeness Information and Its Application to Query Processing	1986	VLDB