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
1580
Venue
PODS
Year
2012
Pagerank
5.952604e-05
Overall Rank
6,166 | 57.70%
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
9,946 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 5.1915905e-05
10,639 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 5.093636e-05
10,650 Rewriting Consistent Answers on Annotated Data 2025 PODS 5.093636e-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.00059843817
309 Optimization of Real Conjunctive Queries 1993 PODS 0.00021768596
1,060 Curated Databases 2008 PODS 0.00012371807
1,269 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.000113935
2,339 Quasi-inverses of Schema Mappings 2007 PODS 8.7249825e-05
Previous Page 1 / 1 Next

Semantically Similar Papers