  Since the early days of relational databases, it was realized that acyclic
hypergraphs give rise to database schemas with desirable structural and
algorithmic properties. In a by-now classical paper, Beeri, Fagin, Maier, and
Yannakakis established several different equivalent characterizations of
acyclicity; in particular, they showed that the sets of attributes of a schema
form an acyclic hypergraph if and only if the local-to-global consistency
property for relations over that schema holds, which means that every
collection of pairwise consistent relations over the schema is globally
consistent. Even though real-life databases consist of bags (multisets), there
has not been a study of the interplay between local consistency and global
consistency for bags. We embark on such a study here and we first show that the
sets of attributes of a schema form an acyclic hypergraph if and only if the
local-to global consistency property for bags over that schema holds. After
this, we explore algorithmic aspects of global consistency for bags by
analyzing the computational complexity of the global consistency problem for
bags: given a collection of bags, are these bags globally consistent? We show
that this problem is in NP, even when the schema is part of the input. We then
establish the following dichotomy theorem for fixed schemas: if the schema is
acyclic, then the global consistency problem for bags is solvable in polynomial
time, while if the schema is cyclic, then the global consistency problem for
bags is NP-complete. The latter result contrasts sharply with the state of
affairs for relations, where, for each fixed schema, the global consistency
problem for relations is solvable in polynomial time.
