DBScholar

Back to papers

Classification of Annotation Semirings over Query Containment

Summary: Axiomatizes commutative annotation semirings under which conjunctive-query containment reduces to existence of specific homomorphisms, covering provenance, probability and multiplicity annotations. Characterizes when such homomorphism checks are necessary/sufficient and derives new decision procedures for containment of unions of conjunctive queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
hbe2e20117f7112e4
Venue
PODS
Year
2012
Pagerank
5.8190435e-05
Overall Rank
6,299 | 57.65%
DOI
10.1145/2213556.2213590

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kostylev_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Classification of Annotation Semirings over Query Containment}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213590},
        doi = {10.1145/2213556.2213590},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kostylev, Egor V. and Reutter, Juan L. and Salamon, András Z.},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank Citing Paper Year Venue Pagerank
10,130 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 5.0751052e-05
11,082 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 4.9793485e-05
11,093 Rewriting Consistent Answers on Annotated Data 2025 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank Cited Paper Year Venue Pagerank
17 Provenance Semirings 2007 PODS 0.00059752575
310 Optimization of Real Conjunctive Queries 1993 PODS 0.00021374145
1,076 Curated Databases 2008 PODS 0.00012159025
1,275 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.00011242154
2,390 Quasi-inverses of Schema Mappings 2007 PODS 8.5367469e-05
Previous Page 1 / 1 Next

Semantically Similar Papers