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,273 | Determinacy of Real Conjunctive Queries. The Boolean Case | 2022 | PODS | 5.1270241e-05 |
| 7,024 | A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations | 2023 | SIGMOD | 4.8530001e-05 |
| 10,919 | Consistency of Relations over Monoids | 2024 | PODS | 4.1905499e-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.00027012705 |
| 924 | The U. R. Strikes Back | 1982 | PODS | 0.00015249498 |
| 3,311 | Attacking Diophantus: Solving a Special Case of Bag Containment | 2019 | PODS | 7.2361776e-05 |
| 3,782 | Bag Query Containment and Information Theory | 2020 | PODS | 6.7691169e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,782 | Bag Query Containment and Information Theory | 2020 | PODS | 6.7691169e-05 |
| 10,000 | A Unifying Algorithm for Hierarchical Queries | 2026 | PODS | 4.1905499e-05 |
| 6,604 | Properties Of Database Schemata With Functional Dependencies | 1984 | PODS | 4.9923197e-05 |
| 13,039 | Dependency Characterizations For Acyclic Database Schemes | 1984 | PODS | 4.1905499e-05 |
| 1,520 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.00011524911 |
| 6,945 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8874695e-05 |
| 7,464 | The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability | 2010 | PODS | 4.7186999e-05 |
| 3,931 | On The Complexity And Axiomatizability Of Consistent Database States | 1984 | PODS | 6.6192327e-05 |
| 6,761 | On The Recognition Of Coverings Of Acyclic Database Hypergraphs | 1983 | PODS | 4.9300962e-05 |
| 10,919 | Consistency of Relations over Monoids | 2024 | PODS | 4.1905499e-05 |