Query Evaluation with Soft-Key Constraints

Summary: Introduce soft-key constraints for probabilistic DBs that penalize key violations and model distributions as Markov networks with per-tuple and per-key cardinality potentials. Provide two polynomial-time algorithms for conjunctive-query marginals (single-relation and multi-relation), prove dichotomy to #P-hardness otherwise, and give a syntactic safety criterion: safe iff safe after making each key hard or removed. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1451
Venue: PODS
Year: 2008
Pagerank: 5.093636e-05
Overall Rank: 12,549 | 13.91%
DOI: 10.1145/1376916.1376934

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Abhay Jha (University of Washington)
2. Vibhor Rastogi (University of Washington)
3. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{jha_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Query Evaluation with Soft-Key Constraints}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376934},
        doi = {10.1145/1376916.1376934},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jha, Abhay and Rastogi, Vibhor and Suciu, Dan},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
557	The Theory of Probabilistic Databases	1987	VLDB	0.00016541752
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
2	4,680	Probabilistic Databases with MarkoViews	2012	VLDB
3	2,831	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD
4	7,851	A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries	2021	PODS
5	13,483	Supporting Hard Queries over Probabilistic Preferences	2020	VLDB
6	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
7	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
8	7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
9	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
10	5,225	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB