Structure and Complexity of Bag Consistency

Summary: Extends Beeri et al.'s local-to-global equivalence to bags: schema hypergraph acyclic iff local-to-global consistency holds for multisets. Analyzes global-consistency complexity for bags: in NP; fixed-schema dichotomy—poly iff acyclic, NP-complete otherwise. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h1c0a5d3066075104
Venue: PODS
Year: 2021
Pagerank: 5.5503389e-05
Overall Rank: 7,330 | 50.72%
DOI: 10.1145/3452021.3458329

Incoming Non-self Citations Over Time

Authors

1. Albert Atserias (Polytechnic University of Catalonia)
2. Phokion G. Kolaitis (IBM; University of California Santa Cruz)

BibTeX Citation

@inproceedings{atserias_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Structure and Complexity of Bag Consistency}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458329},
        doi = {10.1145/3452021.3458329},
        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 = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,666	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.7157324e-05
7,419	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.5326094e-05
11,484	Consistency of Relations over Monoids	2024	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
1,138	The U. R. Strikes Back	1982	PODS	0.00011865234
3,526	Bag Query Containment and Information Theory	2020	PODS	7.2321894e-05
3,570	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.1977783e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,526	Bag Query Containment and Information Theory	2020	PODS
2	10,391	A Unifying Algorithm for Hierarchical Queries	2026	PODS
3	6,834	Properties Of Database Schemata With Functional Dependencies	1984	PODS
4	13,517	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
5	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
6	7,140	Semantic Acyclicity on Graph Databases	2013	PODS
7	7,922	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
8	4,753	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS
9	7,343	On The Recognition Of Coverings Of Acyclic Database Hypergraphs	1983	PODS
10	11,484	Consistency of Relations over Monoids	2024	PODS