Rewriting Consistent Answers on Annotated Data

Summary: Semiring semantics with limited negation for annotated data; consistent answers are the minimum over repairs. Self-join free CQs with keys: CQA is rewritable iff the attack graph is acyclic; extends Koutris-Wijsen to semirings; bag semiring NP-hard and hard to approximate under strong cycles. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2013
Venue: PODS
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,650 | 26.94%
DOI: 10.1145/3725247

Incoming Non-self Citations Over Time

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

Authors

1. Phokion Kolaitis (IBM; University of California Santa Cruz)
2. Nina Pardal (University of Huddersfield; University of Sheffield)
3. Jonni Virtema (University of Sheffield)
4. Jef Wijsen (University of Mons)

BibTeX Citation

@inproceedings{kolaitis_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{Rewriting Consistent Answers on Annotated Data}},
        url = {https://dl.acm.org/doi/10.1145/3725247},
        doi = {10.1145/3725247},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kolaitis, Phokion and Pardal, Nina and Virtema, Jonni and Wijsen, Jef},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.9625097e-05
2,600	Convergence of Datalog over (Pre-) Semirings	2022	PODS	8.3571843e-05
5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS	6.0926349e-05
5,844	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS	6.0687501e-05
6,166	Classification of Annotation Semirings over Query Containment	2012	PODS	5.952604e-05
6,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.9213518e-05
7,088	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	5.7068548e-05
7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	5.5993651e-05
9,133	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	5.3169677e-05
11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	5.093636e-05
11,136	Consistency of Relations over Monoids	2024	PODS	5.093636e-05
11,146	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,524	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS
2	7,088	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS
3	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
4	12,210	Certain Query Answering in Partially Consistent Databases	2014	VLDB
5	7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
6	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
7	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
8	8,626	Charting the Tractability Frontier of Certain Conjunctive Query Answering	2013	PODS
9	9,133	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS
10	5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS