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: 1856
Venue: PODS
Year: 2021
Pagerank: 5.6777112e-05
Overall Rank: 7,186 | 50.70%
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,542	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.8466322e-05
7,269	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.6595955e-05
11,136	Consistency of Relations over Monoids	2024	PODS	5.093636e-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
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
1,111	The U. R. Strikes Back	1982	PODS	0.00012131168
3,457	Bag Query Containment and Information Theory	2020	PODS	7.3981641e-05
3,498	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.3629798e-05

Semantically Similar Papers

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