Querying Uncertain Data with Aggregate Constraints

Summary: Uncertain data with aggregate constraints on record sets makes finding qualified possible worlds by per-tuple sampling inefficient. The paper proposes constraint-aware sampling and MCMC sampling to produce high-quality query results for uncertain data under aggregate constraints with reasonable cost. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4496
Venue: SIGMOD
Year: 2011
Pagerank: 6.0615445e-05
Overall Rank: 5,866 | 59.76%
DOI: 10.1145/1989323.1989409

Incoming Non-self Citations Over Time

Authors

1. Mohan Yang (Microsoft; Shanghai Jiao Tong University)
2. Haixun Wang (Microsoft)
3. Haiquan Chen (Auburn University)
4. Wei-Shinn Ku (Auburn University)

BibTeX Citation

@inproceedings{yang_sigmod11,
        title = {{Querying Uncertain Data with Aggregate Constraints}},
        author = {Yang, Mohan and Wang, Haixun and Chen, Haiquan and Ku, Wei-Shinn},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989409},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989409},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,098	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.9035475e-05
8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.4574671e-05
9,194	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	5.3058708e-05
12,206	Generating Top-k Packages via Preference Elicitation	2014	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
331	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020936658
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
1,254	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.0001147266
1,520	Conditioning Probabilistic Databases	2008	VLDB	0.00010510496
1,638	U-DBMS: A Database System for Managing Constantly-Evolving Data	2005	VLDB	0.00010155338
2,314	SASE: Complex Event Processing over Streams	2007	CIDR	8.7619735e-05
2,410	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.6126774e-05
3,973	Uncertainty Management in Rule-Based Information Extraction Systems	2009	SIGMOD	6.9810029e-05
4,653	Query language support for incomplete information in the MayBMS system	2007	VLDB	6.5850987e-05
5,834	Leveraging Spatio-Temporal Redundancy for RFID Data Cleansing	2010	SIGMOD	6.0721842e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,225	Queries with Arithmetic on Incomplete Databases	2020	PODS
2	699	Data Integration with Uncertainty	2007	VLDB
3	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
4	7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
5	12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD
6	359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
7	2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
8	1,986	Scalable Probabilistic Databases with Factor Graphs and MCMC	2010	VLDB
9	12,467	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
10	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD