Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions

Annotated databases are databases in which each fact in a relation is annotated with a value from some algebraic structure. Starting with the influential work on database provenance [12, 13], there has been an extensive investigation of several different aspects of annotated databases, including the study of conjunctive query containment for annotated databases [11, 15] and the evaluation of Datalog programs on annotated databases [14]. In these investigations, the annotations are values from some fixed semiring $𝕂=(K,+,\times ,0,1)$. Thus, standard relational databases are annotated databases in which the annotations are $1$ (true) and $0$ (false), while bag databases are annotated databases in which the annotations are non-negative integers denoting the multiplicities. This framework, which is often referred to as semiring semantics, has spanned first-order logic [9] and least fixed-point logic [6].

During the early days of relational database theory it was realized that “acyclic” database schemas possess a number of desirable semantic properties. In fact, three different notions of “acyclicity” were identified and extensively investigated during the 1980s, namely, acyclicity (also known as $\alpha$-acyclicity), $\beta$-acyclicity, and $\gamma$-acyclicity. On undirected graphs (equivalently, on database schemas consisting of binary relation symbols only) these notions coincide with the notion of an acyclic graph, but they form a strict hierarchy on hypergraphs (equivalently, on arbitrary database schemas) with $\beta$-acyclicity being a stricter notion than acyclicity, and $\gamma$-acyclicity being a stricter notion than $\beta$-acyclicity.

The study of acyclic schemas was initiated by Yannakakis, who focused on the evaluation of acyclic joins [16]. After this, Fagin, Beeri, Maier, and Yannakakis [4] showed that acyclic schemas are precisely the ones possessing the local-to-global consistency property, that is, every collection of pairwise consistent relations $R_1,\mathrm{\dots },R_m$ over such schemas is globally consistent (i.e., there is a relation $T$ whose projection on the attributes of $R_i$ is equal to $R_i$, for $1\le i\le m$). Fagin et al. [4] also characterized acyclicity in terms of the existence of monotone sequential join expressions, i.e., expressions of the form $(((\mathrm{\cdots }(R_1⨝R_2)⨝\mathrm{\cdots })⨝R_{m-1})⨝R_m)$ with the property that if the relations $R_1,\mathrm{\dots },R_m$ are pairwise consistent, then every intermediate sequential join expression $((\mathrm{\cdots }(R_1⨝R_2)⨝\mathrm{\cdots })⨝R_{i-1})$ produces a relation that is consistent with the relation $R_i$. Results about acyclicity yield results about $\beta$-acyclicity, since a schema is $\beta$-acyclic if and only if every sub-schema of it is acyclic. Fagin [8] studied $\gamma$-acyclicity and showed that a schema is $\gamma$-acyclic if and only if every connected sequential join expression is monotone. Intuitively, this means that every sequential join expression is monotone, provided no join between relations with disjoint sets of attributes is allowed.

Atserias and Kolaitis [2] studied the interplay between local consistency and global consistency for annotated relations. Since the definition of consistency of annotated relations uses only the projection operation on relations and since projection is defined using only addition $+$, they considered $𝕂$-relations where the annotations come from a monoid $𝕂=(K,+,0)$. They identified a condition on monoids, called the inner consistency property, and showed that a positive monoid $𝕂=(K,+,0)$ has the inner consistency property if and only if every acyclic schema $H$ has the local-to-global consistency property for $𝕂$-relations (i.e., every pairwise consistent collection of $𝕂$-relations over $H$ is globally consistent). It was not clear, however, whether the results about acyclic schemas and sequential join expressions in [4] can be extended to annotated relations, since, as shown in [1], the analog of the standard join for bags need not be a witness to the consistency of two consistent bags. In a subsequent paper, Atserias and Kolaitis [3] introduced the notion of a consistency witness function on a positive monoid $𝕂$, which is a function $W$ that, given two $𝕂$-relations $R$ and $S$, returns a $𝕂$-relation $W(R,S)$ that is a consistency witness for $R$ and $S$, provided that $R$ and $S$ are consistent $𝕂$-relations. They also introduced the notion of a monotone sequential $\mathrm{c}$-join expression, which is analogous to that of a monotone sequential join expression with some arbitrary consistency witness function in place of the standard join. Using these notions, it was shown in [3] that the characterization of acyclicity in terms of monotone sequential join expressions in [4] extends to characterizations of acyclicity in terms of monotone sequential $\mathrm{c}$-join expressions on monoids having the inner consistency property; furthermore, the inner consistency property itself can be characterized in such terms.

Here, we investigate $\gamma$-acyclic schemas and establish that the desirable semantic properties of $\gamma$-acyclic schemas extend to annotated relations. The two main results are as follows:

1. 1.

   If $𝕂$ is a positive commutative monoid and $H$ is a schema such that every connected sequential $\mathrm{c}$-join-expression over $H$ is monotone on $𝕂$ w.r.t. some consistency witness function on $𝕂$, then $H$ is $\gamma$-acyclic.

2. 2.

   If $𝕂$ is a positive commutative monoid that has the inner consistency property and $H$ is a schema which is $\gamma$-acyclic, then every connected sequential $\mathrm{c}$-join-expression over $H$ is monotone on $𝕂$ w.r.t. every consistency witness function on $𝕂$.

As a byproduct of these two main results, we obtain a characterization of the inner consistency property in terms of $\gamma$-acyclicity and connected sequential $\mathrm{c}$-join expressions. Furthermore, our work sheds light on the role of the join of two standard relations. Specifically, our results reveal that, in the study of the various notions of acyclicity in [8], the only relevant property of the join of two standard relations is that it is a witness to the consistency of the two relations, provided these two relations are consistent. In the setting of annotated relations, this property of the standard join is captured by the notion of a consistency witness function.

The rest of the paper is organized as follows. Section 2 contains the definitions of the basic notions, while Section 3 contains the definition of a consistency witness function and related notions. To make the paper as self-contained as possible, the earlier results about acyclic schemas are summarized in Section 4. Section 5 discusses $\beta$-acyclic schemas. Section 6 contains the main results about $\gamma$-acyclic schemas and annotated relations.

Let $𝕂=(K,+,0)$ be a positive commutative monoid.

• $\mathrm{■}$

  Two $𝕂$-relations $R(X)$ and $S(Y)$ are consistent if there is a $𝕂$-relation $T(XY)$ such that $T[X]=R$ and $T[Y]=S$. Such a $𝕂$-relation $T$ is a consistency witness for $R$ and $S$.

• $\mathrm{■}$

  A collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of $𝕂$-relations over a schema $X_1,\mathrm{\dots },X_m$ is globally consistent if there is a $𝕂$-relation $T(X_1\mathrm{\dots }{X}_m)$ such that $T[X_i]=R_i$, for $i$ with $1\le i\le m$. Such a $𝕂$-relation $T$ is a consistency witness for $R_1,\mathrm{\dots },R_m$.

Note that if $R_1(X_1),\mathrm{\dots },R_m(X_m)$ is a globally consistent collection of $𝕂$-relations, then the relations $R_1(X_1),\mathrm{\dots },R_m(X_m)$ are pairwise consistent. Indeed, if $T$ is a consistency witness for $R_1(X_1),\mathrm{\dots },R_m(X_m)$, then for all $i$ and $j$ with $1\le i,j\le m$, we have that the $𝕂$-relation $T[X_i{X}_j]$ is a consistency witness for $R_i$ and $R_j$, because

where, in each case, the first equality follows from the definition of global consistency and the second equality follows from Proposition 1.

It is well known that the converse fails even for standard relations, i.e., there are standard relations that are pairwise consistent but not globally consistent. The main result by Beeri et al. [4] characterizes the schemas for which the pairwise consistency of a collection of standard relations implies that they are globally consistent. Quite recently, this result was extended to $𝕂$-relations over positive monoids that satisfy a condition called the inner consistency property [2]. We will discuss this extension in the next section. For now, we consider the following notion, which was introduced and studied in [3].

• $\mathrm{■}$

  A consistency witness function on $𝕂$ is a function $W$ that takes as arguments two $𝕂$-relations $R(X)$ and $S(Y)$, and returns as value a $𝕂$-relation $W(R,S)$ over $XY$ such that if $R$ and $S$ are consistent $𝕂$-relations, then $W(R,S)$ is a consistency witness for $R$ and $S$.

As shown in [2], the witness functions in the first three preceding examples are instances of the standard join ${⨝}_{𝕂,\mathrm{S}}$ on a monoid $𝕂$ that can be expanded to a bounded distributive lattice. For instance, the powerset monoid $\mathbb{P}(A)=(𝒫(A),\cup ,\mathrm{\varnothing })$ can be expanded to the bounded distributive lattice $(𝒫(A),\cup ,\cap ,\mathrm{\varnothing },A)$. Furthermore, the witness functions in the last two preceding examples are instances of the Vorob’ev join ${⨝}_{𝕂,\mathrm{V}}$ on a monoid $𝕂$ that can be expanded to a semifield. For instance, the monoid $𝕋=((-\mathrm{\infty },\mathrm{\infty }],\min ,\mathrm{\infty })$ can be expanded to the tropical semifield $((-\mathrm{\infty },\mathrm{\infty }],\min ,+,-,\mathrm{\infty },0)$.

Note that the bag monoid $\mathbb{N}-(N,+,0)$ was not included in the preceding examples. As pointed out in [1], the bag-join operation of bags (the analog of the standard join for bags) is not a consistency witness function on the bag monoid $\mathbb{N}$. Furthermore, the analog of the Vorob’ev join is not well-defined on $\mathbb{N}$. A consistency witness function for $\mathbb{N}$ can be obtained via an iterative algorithm, called the northwest corner method (see [2] for details).

A join expression is an expression involving standard relations and applications of the join operation $⨝$ on standard relations [4, 8]. In [3], the notion of a $\mathrm{c}$-join expression and its variants were introduced as a generalization of the notion of join expression to arbitrary consistency witness functions and $𝕂$-relations. The precise definitions are as follows.

Let $X_1,\mathrm{\dots },X_m$ be a schema and let ${⨝}_{\mathrm{c}}$ be a binary function symbol, which will be interpreted by some consistency witness function.

• $\mathrm{■}$

  The collection of $\mathrm{c}$-join expressions over $X_1,\mathrm{\dots },X_m$ is the smallest collection of strings that contains each $X_i$ and has the property that if $E_1$ and $E_2$ are in the collection, then also the string $(E_1{⨝}_{\mathrm{c}}{E}_2)$ is in the collection.

• $\mathrm{■}$

  The collection of sequential $\mathrm{c}$-join expressions over $X_1,\mathrm{\dots },X_m$ is the smallest collection of strings that contains each $X_i$ and has the property that if $E$ is in the collection and $X$ is one of the $X_i$’s, then also the string $(E{⨝}_{\mathrm{c}}X)$ is in the collection.

Note that a (sequential) $\mathrm{c}$-join expression over $X_1,\mathrm{\dots },X_m$ need not contain every set $X_i$.

Clearly, the string $((X_1{⨝}_{\mathrm{c}}{X}_2){⨝}_{\mathrm{c}}{X}_3)$ is a sequential $\mathrm{c}$-join-expression, while the string $((X_1{⨝}_{\mathrm{c}}{X}_2){⨝}_{\mathrm{c}}(X_3{⨝}_{\mathrm{c}}{X}_4))$ is a $\mathrm{c}$-join expression, but not a sequential one.

Semantics to $\mathrm{c}$-join expressions are assigned in a straightforward way as follows.

Let $X_1,\mathrm{\dots },X_m$ be a schema and let $E$ be a $\mathrm{c}$-join-expression over $X_1,\mathrm{\dots },X_m$. If $W$ is a consistency witness function on $𝕂$ and $R_1(X_1),\mathrm{\dots },R_m(X_m)$ is a collection of $𝕂$-relations, we write $E(W,R_1,\mathrm{\dots },R_m)$ to denote the $𝕂$-relation over $X_1\mathrm{\cdots }{X}_m$ obtained by evaluating $E$ when ${⨝}_{\mathrm{c}}$ is interpreted by $W$ and each $X_i$ is interpreted by $R_i$ for $i=1,\mathrm{\dots },m$.

The next notion yields a sufficient condition for a $\mathrm{c}$-join expression to give rise to global consistency witnesses.

• $\mathrm{■}$

  Let $E$ be a $\mathrm{c}$-join expression over a schema $X_1,\mathrm{\dots },X_m$, let $W$ be a consistency witness function on $𝕂$, and let $R_1(X_1),\mathrm{\dots },R_m(X_m)$ be a collection of $𝕂$-relations. We say that $E$ is monotone with respect to $W$ and $R_1(X_1),\mathrm{\dots },R_m(X_m)$ if for every sub-expression $E_1{⨝}_{\mathrm{c}}{E}_2$ of $E$, we have that the $𝕂$-relations $E_1(W,R_1,\mathrm{\dots },R_m)$ and $E_2(W,R_1,\mathrm{\dots },R_m)$ are consistent.

The next proposition from [3] is proved in a straightforward way by induction on the construction of $\mathrm{c}$-join expressions and by using Proposition 1.

As mentioned in Section 2, if $R_1,\mathrm{\dots },R_m$ are standard relations that are globally consistent, then they are pairwise consistent, but the converse does not always hold. For example, consider the triangle schema $\{A,B\},\{B,C\},\{C,A\}$ and the standard relations $R_1(A,B)=\{(0,0),(1,1)\}$, $R_2(B,C)=\{(0,1),(1,0)\}$, $R_3(C,A)=\{(0,0),(1,1)\}$. It is easy to check that these standard relations are pairwise consistent; however, they are not globally consistent since $((R_1⨝R_2)⨝R_3)=\mathrm{\varnothing }$. Beeri et al. [4] characterized the schemas for which every collection of pairwise consistent standard relations is globally consistent by showing that these are precisely the acyclic (also known as $\alpha$-acyclic) schemas. To give the precise definition of an acyclic schema, we need to first introduce some basic notions about hypergraphs.

Let $H=(V,F)$ be a hypergraph in which each vertex belong to at least one hyperedge.

• $\mathrm{■}$

  A path in $H$ is a sequence $X_1,\mathrm{\dots },X_k$ of hyperedges of $H$ such that $X_i\cap X_{i+1}\ne \mathrm{\varnothing }$, for every $i$ with . In this case, we say that there is a path from $X_1$ to $X_k$.

• $\mathrm{■}$

  We say that a set $G$ of hyperedges of $H$ is connected if for every two distinct hyperedges $X$ and $X^{\prime }$ of $G$, there is a path from $X$ to $X^{\prime }$.

• $\mathrm{■}$

  A connected component of $H$ is a maximal connected set of hyperedges of $H$

• $\mathrm{■}$

  We say that $H$ is connected if the set $F$ of the hyperedges of $H$ is connected (in other words, $H$ has a single connected component); otherwise, we say that $H$ is disconnected.

• $\mathrm{■}$

  $H$ is reduced if no hyperedge of $H$ is properly contained in some other hyperedge of $H$.

• $\mathrm{■}$

  The reduction of $H$ is the hypergraph $(V,F^{\prime })$, where $F^{\prime }$ consists of the hyperedges in $F$ that are not properly contained in some other hyperedge in $F$.

• $\mathrm{■}$

  If $U\subseteq V$, then the induced hypergraph $H[U]$ is the hypergraph $(U,\{X\cap U:X\in F\}\setminus \{\mathrm{\varnothing }\})$. Also, the restriction of $H$ on $U$, denoted $H\upharpoonright U$, is the reduction of the hypergraph $H[U]$.

• $\mathrm{■}$

  Let $H$ be a reduced hypergraph and let $X,X^{\prime }$ be two distinct hyperedges. We say that $Y=X\cap X^{\prime }$ is an articulation set of $H$ if the number of connected components of $H\upharpoonright (V\setminus Y)$ is bigger than the number of connected components of $H$.

• $\mathrm{■}$

  Let $H$ be a reduced hypergraph. We say that $H$ is acyclic if the following condition holds: for every set $U\subseteq V$, if $H\upharpoonright U$ is connected and has at least two hyperedges, then it has an articulation set; otherwise, we say that $H$ is cyclic.

• $\mathrm{■}$

  We say that $H$ is acyclic if its reduction is acyclic; otherwise, it is cyclic. Acyclic hypergraphs are also known as $\alpha$-acyclic hypergraphs, while cyclic hypergraphs are also known as $\alpha$-cyclic hypergraphs.

Admittedly, the notion of an acyclic hypergraph appears to be difficult to grasp when encountered for the first time. Intuitively, it generalizes to hypergraphs the property that a graph is acyclic if and only if every connected component of it with at least two edges has an articulation point. It is well known that there is a polynomial-time algorithm for testing if a hypergraph is acyclic; this algorithm is due to Graham [10] and, independently, to Yu and Ozsoyoglu [17], and it is known as the GYO algorithm (see also [8]).

There are several different structural conditions that are equivalent to acyclicity. We discuss two of these notions next.

Let $H=(V,F)$ be a hypergraph.

• $\mathrm{■}$

  The Gaifman graph $G(H)$ of $H$ is the undirected graph with nodes the attributes of $H$ and such that there is an edge between two attributes of $H$ if and only if both these attributes belong to one of the hyperedges of $H$.

• $\mathrm{■}$

  $H$ is conformal if every clique of $G(H)$ is contained in one of the hyperedges of $H$.

• $\mathrm{■}$

  $H$ is chordal if every cycle of $G(H)$ of length at least $4$ has a chord, i.e., there is an edge of $G(H)$ that is not an edge of the cycle.

• $\mathrm{■}$

  $H$ has the running intersection property if there is an ordering $Y_1,\mathrm{\dots },Y_m$ of the hyperedges of $H$ such that for every $i\le m$, there is a such that $(Y_1\cup \mathrm{\cdots }\cup Y_{i-1})\cap Y_i\subseteq Y_j$.

The proof of the next result can be found in [4].

The triangle schema $\{A,B\},\{B,C\},\{C,A\}$ is cyclic because it is not conformal (but it is chordal); the 4-cycle schema $\{A,B\},\{B,C\},\{C,D\},\{D,A\}$ is cyclic because it is not chordal (but it is conformal). For every $n\ge 2$, the $n$-path schema $P_n$ with hyperedges $\{A_1,A_2\},\{A_2,A_3\},\mathrm{\dots },\{A_n,A_{n+1}\}$ is acyclic because it is both conformal and chordal. One can also reason about these schemas using the running intersection property. Finally, consider the schema $\{A,B,C\},\{C,D,E\},\{E,F,A\},\{A,C,E\}$. It has the running intersection property via the ordering $\{A,B,C\},\{A,C,E\},\{C,D,E\},\{E,F,A\}$, hence it is acyclic.

Beeri et al. [4] showed that acyclicity can be characterized in terms of useful semantic properties, where by “semantic” we mean a property of the hypergraph whose definition involves also standard relations. Specifically, consider the following two properties.

Let $H$ be a hypergraph with $X_1,\mathrm{\dots },X_m$ as its hyperedges.

• $\mathrm{■}$

  $H$ has the local-to-global consistency property for standard relations if for every collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of pairwise consistent standard relations over $H$, we have that this collection is globally consistent.

• $\mathrm{■}$

  $H$ admits a monotone join expression if there is a $\mathrm{c}$-join expression $E$ such that

  1. i

     $E$ is monotone with respect to the standard join operation $⨝$ and every collection of pairwise consistent relations $R_1(X_1),\mathrm{\dots },R_m(X_m)$;

  2. ii

     Every hyperedge $X_i$ of $H$ occurs in $E$.

As mentioned in Section 2, if a collection of relations is globally consistent, then it is pairwise consistent. Thus, if a schema has the local-to-global consistency property for standard relations, then global consistency coincides with pairwise consistency for relations over that schema. Furthermore, if a schema admits a monotone join expression, then, in view of Proposition 4, this join expression can be used to construct witnesses to global consistency of collections of pairwise consistent relations.

With the notions of local-to-global consistency property and monotone join expression at hand, the main result in Beeri et al. [4] can be stated as follows.

Thus, the triangle schema and the $4$-cycle schema do not have the local-to-global consistency property for standard relations and do not admit a monotone join expression, but each $n$-path schema does, and so does the schema $\{A,B,C\},\{C,D,E\},\{E,F,A\},\{A,C,E\}$.

In [2], the following question was investigated: does Theorem 6 extend from standard relations to $𝕂$-relations, where $𝕂$ is an arbitrary positive commutative monoid?

The first realization in [2] was that acyclicity is a necessary, but not always sufficient, condition for the local-to-global consistency property to hold for $𝕂$-relations. More formally, we say that a hypergraph $H=\{X_1,\mathrm{\dots },X_m\}$ has the local-to-global consistency property for $𝕂$-relations if every collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of pairwise consistent $𝕂$-relations is also globally consistent.

We can now state the precise result about the necessity of acyclicity.

Furthermore, in [2], a class of positive commutative monoids $𝕂$ was identified for which the acyclicity of a hypergraph $H$ is a sufficient condition for $H$ to have the local-to-global consistency property for $𝕂$-relations.

• $\mathrm{■}$

  Two $𝕂$-relations $R(X)$ and $S(Y)$ are inner consistent if $R[X\cap Y]=S[X\cap Y]$.

• $\mathrm{■}$

  We say that $𝕂$ has the inner consistency property if whenever two $𝕂$-relations are inner consistent, they are also consistent.

Note that, using Proposition 1, it is easy to verify that if $R$ and $S$ are consistent $𝕂$-relations, then they are also inner consistent. Consequently, for monoids with the inner consistency property, the notions of consistency and inner consistency coincide. In particular, this holds true for the the Boolean monoid $𝔹=(\{0,1\},\vee ,0)$.

In [1], it was shown that the bag monoid $\mathbb{N}=(N,+,0)$ has the inner consistency property. In [2], several other monoids were shown to have the inner consistency property, including the monoids $𝕍=([0,1],\max ,0)$, ${ℝ}^{\ge 0}=([0,\mathrm{\infty }),+,0)$, $𝕋=((-\mathrm{\infty },\mathrm{\infty }],\min ,\mathrm{\infty })$, and the power set monoids $\mathbb{P}(A)=(𝒫(A),\cup ,\mathrm{\varnothing })$, for every set $A$. In contrast, no numerical semigroup other than the bag monoid has the inner consistency property.

To state the extension of Theorem 6 to $𝕂$-relations, we need some additional notions, which were introduced in [3].

Let $𝕂$ be a positive commutative monoid, let $X_1,\mathrm{\dots },X_m$ be a schema, and let $E$ be a $\mathrm{c}$-join expression over $X_1,\mathrm{\dots },X_m$.

• $\mathrm{■}$

  First, recall from Section 3, that $E$ is monotone with respect to a consistency witness function $W$ on $𝕂$ and a collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of $𝕂$-relations if for every sub-expression $E_1{⨝}_{\mathrm{c}}{E}_2$ of $E$, we have that the $𝕂$-relations $E_1(W,R_1,\mathrm{\dots },R_m)$ and $E_2(W,R_1,\mathrm{\dots },R_m)$ are consistent.

• $\mathrm{■}$

  We say that $E$ is monotone on $𝕂$ if there is a consistency witness function $W$ on $𝕂$ such that $E$ is monotone with respect to $W$ and every collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of pairwise consistent $𝕂$-relations.

• $\mathrm{■}$

  We say that $E$ is strongly monotone on $𝕂$ if for every consistency witness function $W$ on $𝕂$, we have that $E$ is monotone with respect to $W$ and every collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of pairwise consistent $𝕂$-relations.

Finally, we define what it means for a schema to admit a monotone and a strongly monotone $\mathrm{c}$-join expression.

• $\mathrm{■}$

  A schema $X_1,\mathrm{\dots },X_m$ admits a monotone $\mathrm{c}$-join expression on $𝕂$ if there is a $\mathrm{c}$-join-expression $E$ over $X_1,\mathrm{\dots },X_m$ such that $E$ is monotone on $𝕂$ and every hyperedge $X_i$ occurs in $E$.

• $\mathrm{■}$

  A schema $X_1,\mathrm{\dots },X_m$ admits a strongly monotone $\mathrm{c}$-join expression on $𝕂$ if there is a $\mathrm{c}$-join-expression $E$ over $X_1,\mathrm{\dots },X_m$ such that $E$ is strongly monotone on $𝕂$ and every hyperedge $X_i$ occurs in $E$.

We can now state one of the main results from [2, 3].

Theorem 8 yields Theorem 6 of Beeri et al. [4] by taking $𝕂$ to be the Boolean monoid $𝔹$. In fact, Theorem 8 yields something stronger: the standard join $⨝$ can be replaced in Theorem 6 by an arbitrary consistency witness function for standard relations. In effect, this means that the only property of the standard join needed in Theorem 6 is that the standard join is a consistency witness function for standard relations.

As shown in [2], the inner consistency property actually characterizes the positive commutative monoids $𝕂$ for which every acyclic hypergraph has the local-to-global consistency property for $𝕂$-relations.

Their good structural and semantic properties notwithstanding, acyclic hypergraphs suffer from the drawback that acyclicity is not a hereditary property, that is to say, a sub-hypergraph of an acyclic hypergraph need not be acyclic. For example, the hypergraph $\{A,B,C\},\{A,B\},\{B,C\},\{C,A\}$ is acyclic but it contains as a sub-hypergraph the triangle hypergraph $\{A,B\}$, $\{B,C\}$, $\{C,A\}$, which is cyclic.

Motivated by the preceding considerations, Fagin [8] introduced the following notion.

• $\mathrm{■}$

  A hypergraph $H$ is $\beta$-acyclic if every sub-hypergraph of $H$ is acyclic; otherwise, $H$ is $\beta$-cyclic.

For example, the hypergraph $H^{\ast }$ with hyperedges $\{A,B,C\},\{A,B\},\{A,C\}$ is $\beta$-acyclic. There is a polynomial-time algorithm for testing if a hypergraph is $\beta$-acyclic (see [8]).

Fagin [8] found several different characterizations of $\beta$-acyclicity, including some involving the absence of cycles of certain types. In the sequel, we will use the following one.

• $\mathrm{■}$

  A weak $\beta$-cycle in a hypergraph $H$ is a sequence $Y_1,A_1,Y_2,A_2,\mathrm{\dots },Y_k,A_k,Y_{k+1}$ such that $k\ge 3$ and the following properties hold:

  1. 1.

     $Y_1,\mathrm{\dots },Y_k$ are distinct hyperedges of $H$ and $Y_{k+1}=Y_1$;

  2. 2.

     $A_1,\mathrm{\dots },A_k$ are distinct nodes of $H$;

  3. 3.

     For $1\le i\le k$, the node $A_i$ is in $Y_i\cap Y_{i+1}$.

  4. 4.

     For $1\le i\le k$, the node $A_i$ is not in any hyperedge $Y_j$ other than $Y_i$ and $Y_{i+1}$.

For example, consider the schema $\{A,B,C\},\{C,D,E\},\{E,F,A\},\{A,C,E\}$, which was shown earlier to be acyclic. The sequence $\{A,B,C\},C,\{C,D,E\},E,\{E,F,A\},A,\{A,B,C\}$ is a weak $\beta$-cycle, hence this schema is $\beta$-cyclic.

Because of the hereditary nature of $\beta$-acyclicity, the characterizations of acyclicity in Section 4 give rise to characterizations of $\beta$-acyclicity. Thus, the following result holds.

Fagin [8] introduced and studied $\gamma$-acyclic hypergraphs, which form a proper subclass of the class of $\beta$-acyclic hypergraphs. As with $\beta$-acyclic hypergraphs, there are several equivalent formulations of the notion of a $\gamma$-acyclic hypergraph in terms of absence of cycles of certain types, including the following one.

• $\mathrm{■}$

  A weak $\gamma$-cycle in a hypergraph $H$ is a sequence $Y_1,A_1,Y_2,A_2,\mathrm{\dots },Y_k,A_k,Y_{k+1}$ such that $k\ge 3$ and the following properties hold:

  1. 1.

     $Y_1,\mathrm{\dots },Y_k$ are distinct hyperedges of $H$ and $Y_{k+1}=Y_1$;

  2. 2.

     $A_1,\mathrm{\dots },A_k$ are distinct nodes of $H$;

  3. 3.

     For $1\le i\le k$, the node $A_i$ is in $Y_i\cap Y_{i+1}$;

  4. 4.

     For $i=1,2$, the node $A_i$ is not in any hyperedge $Y_j$ other than $Y_i$ and $Y_{i+1}$.

• $\mathrm{■}$

  A hypergraph $H$ is $\gamma$-acyclic if $H$ has no weak $\gamma$-cycle; otherwise, $H$ is $\gamma$-cyclic.

Clearly, every sub-hypergraph of a $\gamma$-acyclic hypergraph is $\gamma$-acyclic as well. Observe that the only difference between a weak $\beta$-cycle and a weak $\gamma$-cycle is in the fourth condition of the definitions of these notions: the requirement that the node $A_i$ belongs only to the hyperedges $Y_i$ and $Y_{i+1}$ holds for every $i\le k$ in the case of a weak $\beta$-cycle, while it holds for $i=1,2$ in the case of a weak $\gamma$-cycle. In particular, every weak $\beta$-cycle is also a weak $\gamma$-cycle; consequently, every $\gamma$-acyclic hypergraph is also $\beta$-acyclic. The converse, however, is not true. To see this, consider the hypergraph $H^{\ast }$ with hyperedges $\{A,B,C\},\{A,B\},\{A,C\}$, which, as pointed out in Section 5, is $\beta$-acyclic. Clearly, the sequence $\{A,B\},B,\{A,B,C\},C,\{A,C\},A,\{A,B\}$ is a weak $\gamma$-cycle, hence this hypergraph is $\gamma$-cyclic. It is also easy to see that for every $n\ge 2$, the $n$-path hypergraph $P_n$ with hyperedges $\{A_1,A_2\},\mathrm{\dots },\{A_n,A_{n+1}\}$ is $\gamma$-acyclic. Note that there is a polynomial-time algorithm, due to D’ Atri and Moscarini [7], for testing whether or not a hypergraph is $\gamma$-acyclic (see also [8, Section 9.4]).

There are several different structural characterizations of $\gamma$-acyclic hypergraphs, including one which is due to Brault-Baron [5] and which involves the hypergraph $H^{\ast }$ above. To describe this characterization, let us recall the following basic notion from Section 4.

• $\mathrm{■}$

  Let $H=(V,F)$ be a hypergraph and let $U$ be a subset of the set $V$ of the nodes of $H$. The induced hypergraph $H[U]$ is the hypergraph with hyperedges $\{X\cap U:X\in E\}\setminus \{\mathrm{\varnothing }\}$.

In fact, Brault-Baron [5] defines a $\gamma$-acyclic hypergraph to be a hypergraph that satisfies the second condition in Proposition 12; he then shows that this condition is equivalent to the D’ Atri and Moscarini algorithm [7] producing the empty hypergraph, hence this condition is equivalent to Fagin’s [8] definition of $\gamma$-acyclicity.

Fagin [8] established that $\gamma$-acyclic hypergraphs have certain desirable semantic properties; the main such property involves the notion of a connected join expression.

• $\mathrm{■}$

  A join expression $E$ is connected if for each of its sub-expressions $(E_1⨝E_2)$, there is an attribute that appears in both $E_1$ and $E_2$.

In particular, if $E$ is a sequential join expression $(((\mathrm{\cdots }(Y_1⨝Y_2)⨝\mathrm{\cdots })⨝Y_{k-1})⨝Y_k)$, then $E$ is connected if and only if for every with $1\le i\le k$, we have that $(Y_1\cup \mathrm{\cdots }\cup Y_{i-1})\cap Y_i\ne \mathrm{\varnothing }$. For example, the sequential join expression $((\{A_1,A_2\}⨝\{A_2,A_3\})⨝\{A_3,A_4\})$ is connected, while the sequential join expression $(\{A_1,A_2\}⨝\{A_3,A_4\})$ is not connected.

We can now state the main semantic characterization of $\gamma$-acyclicity, obtained in [8].

The notion of a connected join expression extends to the notion of a connected $\mathrm{c}$-join expression in a straightforward way.

• $\mathrm{■}$

  A $\mathrm{c}$-join expression $E$ is connected if for each of its sub-expressions $(E_1{⨝}_{\mathrm{c}}{E}_2)$, there is an attribute that appears in both $E_1$ and $E_2$.

In particular, if $E$ is a sequential $\mathrm{c}$-join expression $(((\mathrm{\cdots }(Y_1{⨝}_{\mathrm{c}}{Y}_2){⨝}_{\mathrm{c}}\mathrm{\cdots }){⨝}_{\mathrm{c}}{Y}_{k-1}){⨝}_{\mathrm{c}}{Y}_k)$, then $E$ is connected if for every with $1\le i\le k$, we have that $(Y_1\cup \mathrm{\cdots }\cup Y_{i-1})\cap Y_i\ne \mathrm{\varnothing }$.

It is now natural to ask: does Theorem 13 extend and how does it extend to $\gamma$-acyclic hypergraphs, $\mathrm{c}$-join expressions, and $𝕂$-relations, where $𝕂$ is a positive commutative monoid?

Let $𝕂$ be a positive commutative monoid and let $E$ be a $\mathrm{c}$-join expression. Recall that $E$ is monotone on $𝕂$ if there is a consistency witness function $W$ on $𝕂$ such that $E$ is monotone with respect to $W$ and every collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of pairwise consistent $𝕂$-relations. Recall further that $E$ is strongly monotone on $𝕂$ if $E$ is monotone with respect to every consistency witness function $W$ on $𝕂$ and every collection $R_1(X_1),\mathrm{\dots },R_m(X_m)$ of pairwise consistent $𝕂$-relations.

In what follows in this section, we will establish the following results:

1. 1.

   If $H$ is a hypergraph such that every connected sequential $\mathrm{c}$-join-expression over $H$ is monotone on $𝕂$, then $H$ is $\gamma$-acyclic.

2. 2.

   If $𝕂$ has the inner consistency property and $H$ is $\gamma$-acyclic, then every connected sequential $\mathrm{c}$-join-expression over $H$ is strongly monotone on $𝕂$,