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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,275 | Determinacy of Real Conjunctive Queries. The Boolean Case | 2022 | PODS | 5.1319495e-05 |
| 7,022 | A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations | 2023 | SIGMOD | 4.8576599e-05 |
| 10,915 | Consistency of Relations over Monoids | 2024 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 335 | Optimization of Real Conjunctive Queries | 1993 | PODS | 0.00027036073 |
| 920 | The U. R. Strikes Back | 1982 | PODS | 0.00015338004 |
| 3,307 | Attacking Diophantus: Solving a Special Case of Bag Containment | 2019 | PODS | 7.2431594e-05 |
| 3,775 | Bag Query Containment and Information Theory | 2020 | PODS | 6.775636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,775 | Bag Query Containment and Information Theory | 2020 | PODS | 6.775636e-05 |
| 10,001 | A Unifying Algorithm for Hierarchical Queries | 2026 | PODS | 4.1945683e-05 |
| 6,603 | Properties Of Database Schemata With Functional Dependencies | 1984 | PODS | 4.9971153e-05 |
| 13,028 | Dependency Characterizations For Acyclic Database Schemes | 1984 | PODS | 4.1945683e-05 |
| 1,522 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.0001153051 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 7,473 | The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability | 2010 | PODS | 4.7198203e-05 |
| 3,917 | On The Complexity And Axiomatizability Of Consistent Database States | 1984 | PODS | 6.6328189e-05 |
| 6,761 | On The Recognition Of Coverings Of Acyclic Database Hypergraphs | 1983 | PODS | 4.9348368e-05 |
| 10,915 | Consistency of Relations over Monoids | 2024 | PODS | 4.1945683e-05 |