Consistency of Relations over Monoids

Summary: Examines local-to-global consistency for K-relations in positive commutative monoids. Acyclicity is necessary but not sufficient; defines a transportation property to classify monoids, with a pairwise-consistency variant that preserves global consistency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1970
Venue: PODS
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,136 | 23.60%
DOI: 10.1145/3651608

Incoming Non-self Citations Over Time

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

Authors

1. Albert Atserias (Centre de Recerca Matemàtica; Universitat Politècnica de Catalunya)
2. Phokion G. Kolaitis (IBM; University of California Santa Cruz)

BibTeX Citation

@inproceedings{atserias_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Consistency of Relations over Monoids}},
        url = {https://dl.acm.org/doi/10.1145/3651608},
        doi = {10.1145/3651608},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Atserias, Albert and Kolaitis, Phokion G.},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,177	Codd's Theorem for Databases over Semirings	2026	PODS	5.093636e-05
10,650	Rewriting Consistent Answers on Annotated Data	2025	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
1,111	The U. R. Strikes Back	1982	PODS	0.00012131168
7,186	Structure and Complexity of Bag Consistency	2021	PODS	5.6777112e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
2	9,933	Semantic Acyclicity Under Constraints	2016	PODS
3	4,184	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS
4	12,991	Structural Totality and Constraint Stratification	1995	PODS
5	8,506	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
6	9,483	Local Transformations and Conjunctive-Query Equivalence	2012	PODS
7	33	Consistent Query Answers in Inconsistent Databases	1999	PODS
8	7,759	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
9	4,659	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS
10	7,186	Structure and Complexity of Bag Consistency	2021	PODS