# Reasoning on Property Graphs with Graph Generating Dependencies

Larissa C. Shimomura<EMAIL_ADDRESS>Nikolay Yakovets
<EMAIL_ADDRESS>George Fletcher<EMAIL_ADDRESS>Eindhoven University of
Technology, Department of Mathematics and Computer Science , PO Box 513 5600
MB - Eindhoven, The Netherlands

###### Abstract

Graph Generating Dependencies (GGDs) informally express constraints between
two (possibly different) graph patterns which enforce relationships on both
graph’s _data_ (via property value constraints) and its _structure_ (via
topological constraints). Graph Generating Dependencies (GGDs) can express
tuple- and equality-generating dependencies on property graphs, both of which
find broad application in graph data management. In this paper, we discuss the
reasoning behind GGDs. We propose algorithms to solve the _satisfiability_ ,
_implication_ , and _validation_ problems for GGDs and analyze their
complexity. To demonstrate the practical use of GGDs, we propose an algorithm
which finds inconsistencies in data through validation of GGDs. Our
experiments show that even though the validation of GGDs has high
computational complexity, GGDs can be used to find data inconsistencies in a
feasible execution time on both synthetic and real-world data.

###### keywords:

Graph Dependencies, Graph Data Management, Tuple-generating Dependencies,
Property Graphs

###### MSC:

[2020] 68U35 , 68P15

††journal: Journal of LaTeX Templates

##  1 Introduction

Constraints play a key role in data management research, e.g., in the study of
data quality, data integration and exchange, and query optimization [1, 2, 3,
4, 5, 6, 7, 8]. The use of graph-structured data sets has increased in
different domains, such as social networks, biological networks and knowledge
graphs. As consequence, the study of graph dependencies is also of increasing
practical interest [9, 4] and it also raises new challenges as graphs are
typically schemaless and relationships are first-class citizens.

To address this practical need, recently, different classes of dependencies
for graphs have been proposed, for example, Graph Functional Dependencies
(GFDs [6]), Graph Entity Dependencies (GEDs [5]) and Graph Differential
Dependencies (GDDs [10]). However, these types of dependencies focus on
generalizing functional dependencies (i.e., variations of _equality_
-generating dependencies) and cannot fully capture _tuple_ -generating
dependencies (tgds) for graph data [4].

As an example, we might want to enforce the constraint on a human resources
graph that “if two _people_ vertices have the same _name_ and _address_
property-values and they both have a works-at edge to the same _company_
vertex, then there should be a _same-as_ edge between the two people”. This is
an example of a tgd on graph data, as satisfaction of this constraint requires
the existence of an edge (i.e., the _same-as_ edge), and when it is not
satisfied, the graph is _repaired_ by generating _same-as_ edges where
necessary. tgds are important for many applications, e.g., data cleaning and
integration [3, 8].

Indeed, tgds arise naturally in graph data management applications. Given the
lack of tgds for graphs in the current study of graph dependencies, a new
class of graph dependencies called Graph Generating Dependencies (GGDs) have
been proposed [11]. The GGDs fully support tgds for property graphs (i.e.,
tgds for graphs where vertices and edges can have associated property values,
such as names and addresses in our example above – a very common data model in
practical graph data management systems) and generalize earlier graph
dependencies. The main contribution of the GGDs is the ability to extend tgds
to graph data. Informally, a GGD expresses a constraint between two (possibly
different) graph patterns enforcing relationships between property (data)
values and a topological structure.

In this paper, we study three reasoning problems on property graphs with GGDs:
satisfiability, implication and validation. By studying these problems we can
understand how GGDs behave in applications and what are their limitations. In
our experiments, we show how the validation algorithm can be used to identify
data inconsistencies according to GGDs. Our results show scenarios in which
GGDs can be used in practice.

##  2 Related Work

We place GGDs in the context of relational and graph dependencies. In the
following subsections, we present the main types of relational and graph
dependencies proposed in the literature related to aspects proposed for GGDs.

###  2.1 Relational Data Dependencies

The classical Functional Dependencies (FDs) have been widely studied and
extended for contemporary applications in data management. Related to the
GGDs, other classes of dependencies proposed for relational data are the
Conditional Functional Dependencies (CFDs [2, 3]) and the Differential
Dependencies (DDs [12]). CFDs were proposed for data cleaning tasks where the
main idea is to enforce an FD only for a set of tuples specified by a
condition, unlike the original FDs in which the dependency holds for the whole
relation [13].

DDs extend the FDs by specifying looser constraints according to user-defined
distance functions between attribute values [12]. That is, given two tuples
$t_{1}$ and $t_{2}$, if the distance $\delta$ between two tuple attributes
$x$, $\delta\\{t_{1}(x),t_{2}(x)\\}$ agree on a specified difference/threshold
then the distance between their attributes $y$,
$\delta\\{t_{1}(y),t_{2}(y)\\}$ should also agree on a specified
difference/threshold. Since DDs are defined according to thresholds,
previously proposed algorithms for FDs discovery cannot be applied, hence, new
discovery algorithms were proposed for this class of dependencies [14, 15,
16]. Besides the new approaches of the discovery algorithms, Song et. al [12]
also addressed its difference from previous classes of dependencies and
analyzed the consistency problem of a set of DDs, the implication problem, and
defined the minimal cover of a set of DDs.

Tuple-generating dependencies (tgds) are a well-known type of dependency with
applications in data integration and data exchange [17, 18]. Special cases of
tgds and its extensions also have a wide range of applications [19], e.g., the
inclusion dependencies (INDs). An IND states that all values of a certain
attribute combination are also contained in the values of another attribute
combination [20]. Kruse et al. [21] studied the discovery of INDs, more
specifically, conditional inclusion dependencies (CINDs) for RDF data [21]. In
this work, we use their discovery algorithm for generating input GGDs for our
experiments.

An example of an extension of tgds are the constrained tuple-generating
dependencies (ctgds) [22] which add a condition (a constraint) on variables.
The paper by Maher and Srivastava [22] proposes two Chase procedures to solve
the implication problem for ctgds and the conditions in which these procedures
can be terminated early.

###  2.2 Graph Dependencies

Graph dependencies proposed for the property graphs include the graph
functional dependencies (GFDs), graph entity dependencies (GEDs), and graph
differential dependencies (GDDs) [6, 5, 10]. GFDs are formally defined as a
pair $(Q[\overline{x}],X\rightarrow Y)$ in which $Q[\overline{x}]$ is a graph
pattern that defines a topological constraint while $X,Y$ are two sets of
literals that define the property-value functional dependencies of the GFD.
The property-value dependency is defined for the vertex attributes present in
the graph pattern. GEDs [5] subsume GFDs and can express FDs, GFDs, and
equality-generating dependencies (egds). Besides the property-value
dependencies present in GFDs, GEDs also carry special literals to enable
identification of vertices in the graph pattern. GDDs extend GEDs by
introducing distance functions instead of equality functions, similar to DDs
for relational data but defined over a topological constraint expressed by a
graph pattern.

Similar to the definition of our proposed GGDs, Graph Repairing Rules (GRRs
[23]) were proposed to express automatic repairing semantics for graphs. The
semantics of a GRR is: given a source graph pattern it should be repaired to a
given target graph pattern. The graph-pattern association rules (GPARs [24])
is a specific case of tgds and has been applied to social media marketing. A
GPAR is a constraint of the form $Q(x,y)\Rightarrow q(x,y)$ which states that
if there exists an isomorphism from the graph pattern $Q(x,y)$ to a subgraph
of the data graph, then an edge labeled $q$ between the vertices $x$ and $y$
is likely to hold.

Other types of dependencies recently proposed for property graphs include
Temporal Graph Functional Dependencies (TGFDs) [25] and Graph Probabilistic
Dependencies (GPDs) [26]. The main idea of TGFDs is to extend GFDs by adding a
time constraint. Semantically, a TGFD enforces a topological constraint and a
dependency to hold within a time interval. GPDs extend GFDs by including a
probability value $P$ in which the sets of literal $Y$ is defined by $X$. Even
though GPDs also introduce more relaxed constraints, their approach has a
different semantic to the use of differential/similarity constraints of GDDs
and GGDs.

The main differences of the proposed GGDs compared to previous works are: (i)
the use of differential constraints, (ii) edges are treated as first-class
citizens in the graph patterns (in alignment with the property graph model)
and, (iii) the ability to entail the generation of new vertices and edges (see
Section 4 for details). With these new features, GGDs can encode relations
between two graph patterns as well as the (dis)similarity between its vertices
and edges properties values. In general, GGD is the first constraint formalism
for property graphs supporting both egds and tgds.

In the first study of GGDs [11], the authors introduced the definition and
semantics of the this new class of dependencies. In this paper, we focus on
three fundamental reasoning problems of GGDs over property graphs and show how
GGDs can be used in practice to detect data inconsistencies.

##  3 Preliminaries

In this section, we summarize standard notation and concepts that will be used
throughout the paper [5, 12, 9, 11]. Let $O$ be a set of objects, $L$ be a
finite set of labels, $K$ be a set of property keys, and $N$ be a set of
values. We assume these sets to be pairwise disjoint. A property graph is a
structure $(V,E,\eta,\lambda,\nu)$ where:

  * •

$V\subseteq O$ is a finite set of objects, called vertices;

  * •

$E\subseteq O$ is a finite set of objects, called edges;

  * •

$\eta:E\rightarrow V\times V$ is function assigning to each edge an ordered
pair of vertices;

  * •

$\lambda:V\cup E\rightarrow P(L)$ is a function assigning to each object a
finite set of labels (i.e., $P(S)$ denotes the set of finite subsets of set
$S$). Abusing the notation, we will use $\lambda_{v}$ for the function
assigning labels to vertices and $\lambda_{e}$ for the function that assigns
labels to the edges; and

  * •

$\nu:(V\cup E)\times K\rightarrow N$ is partial function assigning values for
properties/attributes to objects, such that the object sets $V$ and $E$ are
disjoint (i.e., $V\cap E=\emptyset$) and the set of domain values where $\nu$
is defined is finite.

A graph pattern is a directed graph
$Q[\overline{x}]=(V_{Q},E_{Q},\lambda_{Q},\eta_{Q})$ where $V_{Q}$ and $E_{Q}$
are finite sets of pattern vertices and edges, respectively, and $\lambda_{Q}$
is a function that assigns a label $\lambda_{Q}(u)$ to each vertex $u\in
V_{Q}$ or edge $e\in E_{Q}$, and $\eta_{Q}$ assigns to each edge an ordered
pair of vertices. Abusing notation, we use ${\lambda_{v}}_{Q}$ as a function
to assign labels to vertices and ${\lambda_{e}}_{Q}$ to assign labels to
edges. Additionally, $\overline{x}$ is a list of variables that include all
the vertices in $V_{Q}$ and edges in $E_{Q}$.

We say a label $l$ matches a label $l^{\prime}\in L$, denoted as $l\asymp
l^{\prime}$, if $l\in L$ and $l=l^{\prime}$ or $l=$ ‘-’ (wildcard) . A match
denoted as $h[\overline{x}]$ of a graph pattern $Q[\overline{x}]$ in a graph G
is a homomorphism of $Q[\overline{x}]$ to G such that for each vertex $u\in
V_{Q},{\lambda_{v}}_{Q}(u)\asymp{\lambda_{v}}(h(u))$; and for each edge
$e=(u,u^{\prime})\in E_{Q}$, there exists an edge
$e^{\prime}=(h(u),h(u^{\prime}))$ and
${\lambda_{e}}_{Q}(e)\asymp{\lambda_{e}}(e^{\prime})$.

We denote as $\llbracket Q[\overline{x}],\phi\rrbracket_{G}$ the evaluation
results of the graph pattern query $Q[\overline{x}]$ on the graph G, such that
the results of this evaluation also satisfy constraints in $\phi$, i.e.,
$Q[\overline{x}]\models\phi$.

A differential function $\phi[A]$ on attribute $A$ is a constraint of
difference over $A$ according to a distance metric [12]. Given two tuples
$t_{1},t_{2}$ in an instance I of relation R, $\phi[A]$ is true if the
difference between $t_{1}.A$ and $t_{2}.A$ agrees with the constraint
specified by $\phi[A]$, where $t_{1}.A$ and $t_{2}.A$ refers to the value of
attribute $A$ in tuples $t_{1}$ and $t_{2}$, respectively. We use the
differential constraint idea to define constraints over attributes in GGDs.

##  4 GGD: Syntax and Semantics

In this section, we review the syntax and semantics of the GGDs in [11]. A
Graph Generating Dependency (GGD) is a dependency of the form

$Q_{s}[\overline{x}],\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}],\phi_{t}$

where:

  * •

$Q_{s}[\overline{x}]$ and $Q_{t}[\overline{x},\overline{y}]$ are graph
patterns, called source graph pattern and target graph pattern, respectively;

  * •

$\phi_{s}$ is a set of differential constraints defined over the variables
$\overline{x}$ (variables of the graph pattern $Q_{s}$); and

  * •

$\phi_{t}$ is a set of differential constraints defined over the variables
$\overline{x}\cup\overline{y}$, in which $\overline{x}$ are the variables of
the source graph pattern $Q_{s}$ and $\overline{y}$ are any additional
variables of the target graph pattern $Q_{t}$.

A differential constraint in $\phi_{s}$ on $[\overline{x}]$ (resp., in
$\phi_{t}$ on $[\overline{x},\overline{y}]$) is a constraint of one of the
following forms [10, 12]:

  1. 1.

$\delta_{A}(x.A,c)\leq t_{A}$

  2. 2.

$\delta_{A_{1}A_{2}}(x.A_{1},x^{\prime}.A_{2})\leq t_{A_{1}A_{2}}$

  3. 3.

$x=x^{\prime}$ or $x\neq x^{\prime}$

where $x,x^{\prime}\in\overline{x}$ (resp. $\in\overline{x}\cup\overline{y}$)
for $Q_{s}[\overline{x}]$ (resp. for $Q_{t}[\overline{x},\overline{y}]$),
$\delta_{A}$ is a user-defined _similarity function_ for the property $A$ and
$x.A$ is the property value of variable $x$ on $A$, $c$ is a constant of the
domain of property $A$ and $t_{A}$ is a pre-defined threshold. The
differential constraints defined by (1) and (2) can use the operators
$(=,<,>,\leq,\geq,\neq)$.

The constraint (3) $x=x^{\prime}$ states that $x$ and $x^{\prime}$ are the
same entity (vertex/edge) and it can also use the inequality operator stating
that $x\neq x^{\prime}$. An important feature of GGDs is that both vertices
and edges are considered variables (in source and target graph patterns),
which allows to compare vertex-vertex variables, edge-edge and vertex-edge
variables.

Consider a graph pattern $Q[\overline{z}]$, a set of differential constraints
$\phi_{z}$ and a match of this pattern represented by $h[\overline{z}]$ in a
graph $G$. The match $h[\overline{z}]$ satisfies $\phi_{z}$, denoted as
$h[\overline{z}]\models\phi_{z}$ if the match $h[\overline{z}]$ satisfies
every differential constraint in $\phi_{z}$. If $\phi_{z}={\emptyset}$ then
$h[\overline{z}]\models\phi_{z}$ for any match of the graph pattern
$Q[\overline{z}]$ in $G$.

Given a GGD $Q_{s}[\overline{x}],\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}],\phi_{t}$ we denote the matches of the source
graph pattern $Q_{s}[\overline{x}]$ as $h_{s}[\overline{x}]$ while the matches
of the target graph pattern $Q_{t}[\overline{x},\overline{y}]$ are denoted by
$h_{t}[\overline{x},\overline{y}]$ which can include the variables from the
source graph pattern $\overline{x}$ and additional variables $\overline{y}$
particular to the target graph pattern.

A GGD $\sigma=Q_{s}[\overline{x}],\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}],\phi_{t}$ holds in a graph G, denoted as
$G\models\sigma$, if and only if for every match $h_{s}[\overline{x}]$ of the
source graph pattern $Q_{s}[\overline{x}]$ in $G$ satisfying the set of
constraints $\phi_{s}$, there exists a match
$h_{t}[\overline{x},\overline{y}]$ of the graph pattern
$Q_{t}[\overline{x},\overline{y}]$ in $G$ satisfying $\phi_{t}$ such that for
each $x$ in $\overline{x}$ it holds that $h_{s}(x)=h_{t}(x)$. If a GGD does
not hold in $G$ then it is _violated_. Such violations can be fixed by
_generating_ new vertices/edges in graph $G$ according to the violated GGD.

##  5 Properties of GGDs

In this section, we define properties and concepts of GGDs that are used in
the proposed algorithms to solve the reasoning problems we will study in
Section 7.

#### Subjugation

To define subjugation for GGDs, we adapt the subjugation definition on the
sets of differential constraints from the GDDs [10] and subsumption of DDs
[12]. A differential function $\phi_{1}$ subjugates a second differential
function $\phi_{2}$ if for any graph pattern match $h[\overline{x}]$, if
$h[\overline{x}]$ satisfies $\phi_{2}$ ($h[\overline{x}]\models\phi_{2}$),
then $h[\overline{x}]$ also satisfies $\phi_{1}$
($h[\overline{x}]\models\phi_{1}$) [12].

A set of GGD differential constraints $\tau$ subjugates another set of GGD
differential constraints $\omega$, denoted as $\tau\succeq\omega$, iff:

  1. 1.

for every constraint $\delta_{A}(x.A,c)\leq t_{A}\in\tau$, there exists
$\delta_{A}(x.A,c)\leq t_{A}^{\prime}\in\omega$ and $t_{A}\geq
t_{A}^{\prime}$;

  2. 2.

for every constraint $\delta_{A_{1}A_{2}}(x.A_{1},x^{\prime}.A_{2})\leq
t_{A_{1}A_{2}}\in\tau$, there exists $\\\
\delta_{A_{1}A_{2}}(x.A_{1},x^{\prime}.A_{2})\leq
t_{A_{1}A_{2}}^{\prime}\in\omega$ and $t_{A_{1}A_{2}}\geq
t_{A_{1}A_{2}}^{\prime}$;

  3. 3.

for every constraint $x=x^{\prime}\in\tau$ there exists
$x=x^{\prime}\in\omega$;

Given the transitivity and properties of differential constraints studied by
[12], we have the following proposition.

###### Proposition 1

Suppose $\tau,\omega$ and $\psi$ are sets of differential constraints in GGDs,
if $\tau\succeq\psi$ and $\psi\succeq\omega$ then $\tau\succeq\omega$ [12].

#### Graph query containment

Graph pattern queries can be expressed as conjunctive queries (CQs) [9].
According to Chandra and Merlin [27], given two conjunctive queries
$q_{1},q_{2}$, $q_{1}\sqsubseteq q_{2}$ is equivalent to the existence of a
homomorphism $h$ from $q_{2}$ to $q_{1}$. Given this definition, we have the
following proposition.

###### Proposition 2

A graph pattern query $Q_{1}$ is contained in a graph pattern query $Q_{2}$
denoted as $Q_{1}\sqsubseteq Q_{2}$, if the answer set of $Q_{1}$ is contained
in the answer set of $Q_{2}$ for every possible property graph $G$, which
means that there exists a homomorphism $h$ from $Q_{2}$ to $Q_{1}$.

Figure 1: Containment Example

###### Example 1

Consider the graph patterns $Q_{\alpha}$ and $Q_{\beta}$ and its respective
sets of differential constraints $\phi_{\alpha}$ and $\phi_{\beta}$ in Figure
1. Observe that exists an homomorphic mapping of the nodes
$h(x^{\prime})=x,h(u^{\prime})=u,h(v^{\prime})=v$ in $Q_{\alpha}$ to the nodes
in $Q_{\beta}$, therefore we can conclude that $Q_{\alpha}\sqsubseteq
Q_{\beta}$. Considering this homomorphic mapping from $Q_{\alpha}$ to
$Q_{\beta}$, the differential constraint of $\phi_{\beta}$,
$\delta_{A}(u^{\prime}.A,9)\leq 7$ subjugates the differential constraint
$\delta_{A}(u.A,9)\leq 5$ of $\phi_{\alpha}$ and the differential constraint
of $\phi_{\beta}$, $\delta_{A}(v^{\prime}.A,x^{\prime}.A)>0$ subjugates the
differential constraint $\delta_{A}(v.A,x.A)\geq 1$ of $\phi_{\alpha}$ as any
value that satisfies the differential constraints of $\phi_{\alpha}$ also
satisfies the differential constraints of $\phi_{\beta}$. Consequently, we can
conclude that $\phi_{\beta}\succeq\phi_{\alpha}$.

#### Infeasibility and disjoint differential constraints

A set of constraints $\phi$ is infeasible if there does not exist a nonempty
graph pattern match $h[\overline{x}]$ of a graph pattern $Q[\overline{x}]$
over any nonempty graph $G$, such that $h[\overline{x}]\models\phi$. Two
differential constraints $\phi_{a}$ and $\phi_{b}$ are disjoint if their
intersection (conjunction) is infeasible
($\phi_{a}\wedge\phi_{b}$=infeasible). The conjunction of a differential
constraint $\phi_{a}$ with its complement $\overline{\phi_{a}}$
($\phi_{a}\wedge\overline{\phi_{a}}$), is always infeasible [12].

Figure 2: Example GGDs

###### Example 2

Consider the GGD $\sigma_{2}$ of Figure 2 and the set of differential
constraints
$\phi=\\{\delta_{\text{hours}}(\text{s.hours},10)>5,\delta_{\text{hours}}(\text{s.hours},10)<5\\}$,
the set $\phi$ is infeasible as the differential constraints
$\delta_{\text{hours}}(\text{s.hours},10)>5$ and
$\delta_{\text{hours}}(\text{s.hours},10)<5$ are disjoint. In conclusion,
there are no nonempty matches of the graph pattern that can satisfy the set
$\phi$.

#### GGDs interaction

A GGD $\sigma_{1}=Q_{s1}[\overline{x}],\phi_{s1}\rightarrow
Q_{t1}[\overline{x},\overline{y}],\phi_{t1}$ interacts on the source (resp. on
the target) with a GGD $\sigma_{2}=Q_{s2}[\overline{x}],\phi_{s2}\rightarrow
Q_{t2}[\overline{x},\overline{y}],\phi_{t2}$ if and only if the intersection
between $Q_{s1}[\overline{x}]\phi_{s1}$ and $Q_{s2}[\overline{x}]\phi_{s2}$
(resp. $Q_{t1}[\overline{x},\overline{y}]\phi_{t1}$ and
$Q_{t2}[\overline{x},\overline{y}]\phi_{t2}$) is not empty. Considering
$Q_{s1}=\\{V_{s1},E_{s1},\lambda_{s1},\eta_{s1}\\}$ and
$Q_{s2}=\\{V_{s2},E_{s2},\lambda_{s2},\eta_{s2}\\}$, we define the
intersection of $Q_{s1}[\overline{x}]\phi_{s1}$ and
$Q_{s2}[\overline{x}]\phi_{s2}$ as a graph pattern
$Q_{\cap}=\\{V_{\cap},E_{\cap},\lambda_{\cap},\eta_{\cap}\\}$ in which
$Q_{\cap}$ is the maximal graph pattern (maximal set of subgoals of a
conjunctive query) of $Q_{s1}$ and $Q_{s2}$ such that there exists a
homomorphic mapping from $Q_{\cap}$ to $Q_{s1}$ and from $Q_{\cap}$ to
$Q_{s2}$. We define $Q_{\cap}$ as:

  * •

$V_{\cap}$ is the set of nodes $v\in V_{s1}$ such that there exists
$\lambda_{s1}(v)\asymp\lambda_{s2}(v^{\prime})$ or
$\lambda_{s2}(v^{\prime})\asymp\lambda_{s1}(v)$, where $v^{\prime}\in V_{s2}$.
Additionally, the differential constraints in $\phi_{s1}$ that refer to $v\in
V_{s1}$ are feasible to the differential constraints in $\phi_{s2}$ that refer
to $v^{\prime}\in V_{s2}$.

  * •

$E_{\cap}$ is the set of edges $e\in E_{s1}$ such that there exists
$\lambda_{s1}(e)\asymp\lambda_{s2}(e^{\prime})$ or
$\lambda_{s2}(e^{\prime})\asymp\lambda_{s1}(e)$, where $e^{\prime}\in E_{s2}$.
The labels of the source and target of $e$ and $e^{\prime}$ also match,
formally, considering $\eta_{s1}(e)=(v_{1},v_{2})$ and
$\eta_{s2}=(v_{3},v_{4})$, $\lambda_{s1}(v_{1})\asymp\lambda_{s2}(v_{3})$ and
$\lambda_{s1}(v_{2})\asymp\lambda_{s2}(v4)$ are true. Additionally, the
differential constraints in $\phi_{s1}$ that refer to $e\in E_{s1}$ are
feasible to the differential constraints in $\phi_{s2}$ that refer to
$e^{\prime}\in E_{s2}$.

  * •

$\lambda_{\cap}$ is the function $\lambda_{s1}$ which assigns the labels to
the nodes and edges in $Q_{\cap}$ (in this case, same labels as in
$Q_{s1}[\overline{x}]$).

  * •

$\eta_{\cap}$ is the function $\eta_{s1}$ which assigns a pair of vertices in
$V_{\cap}$ to $E_{\cap}$.

The graph pattern $Q_{\cap}$ is not empty if $V_{\cap}\neq\\{\emptyset\\}$ or
$E_{\cap}\neq\\{\emptyset\\}$. Informally, two GGDs interact if their sources
or targets can possibly match some of the same nodes and/or edges in a graph
$G$.

###### Example 3

Consider the GGDs in Figure 2 with empty $\phi_{s}$ and $\phi_{t}$. In this
example, the GGD $\sigma_{2}$ interacts on the source with the GGD
$\sigma_{3}$. The GGD $\sigma_{2}$ and the GGD $\sigma_{3}$ can both match the
same nodes in a graph $G$ to the node project $p$ present in the source of
both GGDs.

#### Transitive GGDs

Given a set of GGDs $\Sigma$, we say that a GGD $\sigma_{1}\in\Sigma$ is
transitive if there exists a GGD $\sigma_{2}\in\Sigma$ in which the target
side of $\sigma_{2}$ interacts with the source side of $\sigma_{1}$. Formally,
consider $\sigma_{1}=Q_{s1}[\overline{x}],\phi_{s1}\rightarrow
Q_{t1}[\overline{x},\overline{y}],\phi_{t1}$ and
$\sigma_{2}=Q_{s2}[\overline{x}],\phi_{s2}\rightarrow
Q_{t2}[\overline{x},\overline{y}],\phi_{t2}$, $\sigma_{1}$ is transitive if
$Q_{t2}[\overline{x},\overline{y}],\phi_{t2}\Leftarrow
Q_{s1}[\overline{x}],\phi_{s1}$ ($\llbracket
Q_{t2}[\overline{x},\overline{y}],\phi_{t2}\rrbracket_{G}\subseteq\llbracket
Q_{s1}[\overline{x}],\phi_{s1}\rrbracket_{G}$). Informally, $\sigma_{1}$ is
transitive in $\Sigma$ if there exists a $\sigma_{2}$ in which its target side
can trigger the source side of $\sigma_{1}$

###### Example 4

Consider the GGDs in Figure 2 with empty $\phi_{s}$ and $\phi_{t}$. In this
example, we can clearly see that the GGD $\sigma_{3}$ is transitive as what is
enforced by the target of $\sigma_{2}$ interacts with the source side of
$\sigma_{3}$. When repairing a graph $G$ according to $\sigma_{2}$ we can
possibly generate new matches of the source graph pattern of $\sigma_{3}$.
Which means that the repairing of a GGD can also trigger the repairing of
another GGD.

##  6 The Chase Procedure for GGDs

The Chase procedure was originally proposed for testing logical implication
between sets of dependencies [17] and has gained attention due to its
application in data exchange, query optimization and data repair [8]. In this
section, we define the Chase procedure for GGDs to solve the satisfiability
and implication problems. Our Chase procedure is based on the standard Chase
procedure for tgds and GEDs [22, 5].

The Chase procedure for ctgds and GEDs were both defined considering the
equality of attributes. Given the differential constraints in $\phi_{s}$ and
$\phi_{t}$ of the GGDs, we use the idea of range of values in this Chase
procedure. We use the graph $G_{1}$ and the GGD $\sigma_{\gamma}$ in Figure 3
as a running example in this section.

Figure 3: Chase Example

###  6.1 The Chase for GGDs

Following the Chase methods designed for GEDs [5] and tgds [28], we define the
Chase method according to range relations. Consider a graph
$G=(V,E,\eta,\lambda,\nu)$ and a set $\Sigma$ of GGDs, we define the Chase for
GGDs as a sequence of Chase steps on $G$. Next, we define the concept of range
classes and Chase steps.

#### Range Class

For each $x\in(V\cup E)$, its range class (denoted as $[x]_{R_{q}}$) is a set
of nodes or edges $y\in(V\cup E)$ of $G$ that are identified as $x$. The node
or edge $y$ can be identified as $x$ because of the enforced constraints on
GGDs of the type $x=y$ (see GGDs definition on Section 4). For each attribute
$A$ of $x\in(V\cup E)$ formally denoted as $\nu(x,A)$ , its range class is
denoted as $[x.A]_{R_{q}}$. Informally, the range class refers to the possible
set of values that an attribute can have enforced by a GGD in $\Sigma$.

According to a GGD, the differential constraints defines the possible values
of an attribute, as a consequence, we use the same semantics of the
differential constraints to define the attribute range class. For each
attribute $A$ of $x\in(V\cup E)$, its range class $[x.A]_{R_{q}}$ contains a
set of range class quadruples named $rcq=(\delta_{A},val_{A},t_{A},op_{A})$
that refers to the differential constraints of a GGD involving $x.A$, in
which:

  * •

$\delta_{A}$ is the distance used in the differential constraint;

  * •

$val_{A}$ is the set of attribute values that $\nu(x.A)$ is compared to;

  * •

$t_{A}$ is the threshold used in the differential constraint and,

  * •

$op_{A}$ is the operator of the differential constraint that is being compared
to $(<,>,\leq,\geq,=,\neq)$

A $rcq_{1}=(\delta_{A},val_{A},t_{A},op_{A})$ subsumes a second
$rcq_{2}=(\delta_{B},val_{B},t_{B},op_{B})$ according to the same subjugation
properties of a differential constraint (see Section 5). A range class
$[x.A]_{R_{q}}$ subsumes a range class $[y.B]_{R_{q}}$, denoted as
$[x.A]_{R_{q}}\succeq[y.B]_{R_{q}}$, if (i)$x$ and $y$ are the same node or
edge on $G$ and, (ii) every $rcq$
$(\delta_{B},val_{B},t_{B},op_{B})\in[y.B]_{R_{q}}$ is subsumed by a $rcq$
$(\delta_{A},val_{A},t_{A},op_{A})\in[x.A]_{R_{q}}$.

#### Chasing - Initialization

\- Given a graph $G=(V,E,\eta,\lambda,\nu)$ and a set $\Sigma$ of GGDs, we
start the Chase procedure by initializing the range classes of each node and
edge of $G$. For each $x\in(V\cup E)$, $[x]_{R_{q}}$ = $\\{x\\}$ and each
attribute range class $[x.A]_{R_{q}}=\\{(,x.A,0,=)\\}$, that means
initializing each range class with a $rcq$ that indicates its own value.

Figure 4: Range Classes Initialization

###### Example 5

To run Chase over the graph $G_{1}$ in Figure 3, we initialize the range
classes of each node and vertex of $G$ as well as the range classes of its
attributes (see Figure 4). As mentioned, we initialize each range class with
an $rcq$ that indicates its own value. Observe that, in this case, each $rcq$
is initialized without a distance function attached, to represent the
attribute value. In case this attribute was built according to a differential
constraint, the $rcq$ would be initialized according to this differential
constraint.

#### Chasing - Match

\- After initializing the range classes of each node and edge in $G$, to apply
each Chase step according to a GGD $\sigma\in\Sigma$, we need to find matches
of the source side and the target side of $\sigma$ in $G$. In the Chase, a
match $h_{s}[\overline{x}]$ of a graph pattern $Q[\overline{x}]$ is a
homomorphism of $Q[\overline{x}]$ to G such that for each vertex $u\in
V_{Q},{\lambda_{v}}_{Q}(u)\asymp{\lambda_{v}}(h(u))$; and for each edge
$e=(u,u^{\prime})\in E_{Q}$, there exists an edge
$e^{\prime}=(h(u),h(u^{\prime}))$ and
${\lambda_{e}}_{Q}(e)\asymp{\lambda_{e}}(e^{\prime})$. And, we check if
$h_{s}[\overline{x}]\models\phi_{s}$ according to the information in the range
classes of each vertex and edge of $h_{s}[\overline{x}]$. Formally, for each
vertex and edge $u$ in $h_{s}[\overline{x}]\models\phi_{s}$, if its range
class $[u]_{R_{q}}$ subsumes the possible values of $u$ constrained by
$\phi_{s}$ and its attributes range classes $[u.A]_{R_{q}}$ subsumes the
possible values of $u.A$ constrained by $\phi_{s}$.

#### Chasing - Step

The Chase procedure is a sequence of Chase steps denoted as:

$G\xrightarrow{(\sigma,h_{s}[\overline{x}]\models\phi_{s})}G^{\prime}$

A Chase step according to a GGD $\sigma\in\Sigma$ can be applied if there
exists a match of its source side, $h_{s}[\overline{x}]\models\phi_{s}$ in
$G$. Each Chase step expands $G$ by generating new nodes or edges and performs
a set of updates on the range classes of nodes and edges according to $\sigma$
and a match $h_{s}[\overline{x}]$ of the source graph pattern of $\sigma$, the
result of these updates is a graph $G^{\prime}$. These updates are executed
according to the following steps:

  1. 1.

Update the range classes of the nodes and edges in $h_{s}[\overline{x}]$
according to $\phi_{s}$ (see Range Classes Updates - $\phi_{s}$ and
$\phi_{t}$);

  2. 2.

Search for a match of the target side of the GGD $\sigma$: (1) If there are no
matches of the target side, we add new nodes and edges to $G$ and initialize
its range classes according to $\phi_{t}$. (2) If there are matches of the
target side, for each match we update its range classes according to
$\phi_{t}$ (see Generation of new nodes and edges).

  3. 3.

Check if the Chase step is consistent. If the step is not consistent then stop
the Chase (see Consistency).

Next, we give details on each one of the mentioned updates.

#### Range Classes Updates - $\phi_{s}$ and $\phi_{t}$

Given $h_{s}(\overline{x})$, for each node or edge $x$ matched in
$h_{s}[\overline{x}]$, get the differential constraints in $\phi_{s}$ that
refer to $x$, denoted as $\phi_{x}$.

  * •

Consider that $x^{\prime}$ is the variable names of $x$. If a constraint of
the type $\delta(x^{\prime}.A,c)\leq t_{A}$ or $\delta(x^{\prime}.A,y.B)\leq
t_{AB}$ is in $\phi_{x}$, rewrite it as a $rcq$ of the type
$\Phi=(\delta,val,t,op)$. If exists a $rcq$
$(\delta_{A},val_{A},t_{A},op_{A})$ in $[x.A]_{R_{q}}$ that is subsumed by
$\Phi$, we update the $rcq(\delta_{A},val_{A},t_{A},op_{A})\in[x.A]_{R_{q}}$
with the values of $\Phi$. Else, if such subsumption does not exist, add
$\Phi$ to $[x.A]_{R_{q}}$ ($[x.A]_{R_{q}}=[x.A]_{R_{q}}\cup\\{\Phi\\}$).

  * •

Consider that $x^{\prime}$ and $y^{\prime}$ are the variable names of $x$ and
$y$. If a constraint of the type $x^{\prime}=y^{\prime}$ is in $\phi_{x}$, in
which $y$ is a node or edge in $h_{s}(\overline{x})$. Add $y$ to the range
class of $x$, $[x]_{R_{q}}=[x]_{R_{q}}\cup y$.

Informally, we update each node or edge range class with the loosest threshold
from $\phi_{s}$ hence each attribute has the largest number of possible
values.

In case there exists a target match, $h_{t}[\overline{x,y}]\models\phi_{t}$,
we enforce the constraints in $\phi_{t}$ in $G$ by updating the range classes
of the nodes and edges that were matched in $h_{t}[\overline{x,y}]$. We update
the range classes in the same way as we do with $\phi_{s}$ on
$h_{s}[\overline{x}]$.

#### Generation of new nodes and edges

Given the Chase step $(\sigma,h_{s}[\overline{x}]\models\sigma)$, we generate
new nodes and edges in the graph $G$ if there are no matches of the target
side $Q_{t}[\overline{x,y}]\phi_{t}$. We generate nodes and edges that refer
to the set $\overline{y}$ of variables in $Q_{t}[\overline{x},\overline{y}]$
of the target graph pattern, as the set $\overline{x}$ refers to the source
variables and exist in the graph (match $h_{s}[\overline{x}]$). For each
variable $y\in\overline{y}$, if $y$ refers to an node in
$Q_{t}[\overline{x,y}]$, we create a new node or edge $u$ in which:
(i)$\lambda_{Q_{t}}(u)=\lambda(u)$ ($\lambda$ is a label assigning functions
of the target graph pattern and for the graph G respectively), (ii) initialize
its range class $[u]_{R_{q}}=\\{u\\}$ and if there exist a differential
constraint in $\phi_{t}$ that refers to an attribute of $u$, suppose $u.C$, we
create a range class $[u.C]_{R_{q}}$ and initialize it with a $rcq$ with the
information of this differential constraint. Finally, we add $u$ to the graph
$G$, in case $u$ is a node $V=V\cup{u}$, or in case it is an edge
$E=E\cup{u}$.

#### Consistency

\- We say that a Chase step is not consistent in $G$ if:

  1. 1.

there exists a node or an edge $y$ in $[x]_{R_{q}}$ in which the
$\lambda(x)\not\asymp\lambda(y)$ and $\lambda(y)\not\asymp\lambda(x)$ (label
conflict) or,

  2. 2.

there exists a $rcq$ $\omega=(\delta_{B},val_{B},t_{B},op_{B})$ on an
attribute $y.B$ in $[x.A]_{R_{q}}$ in which $\omega\wedge[x.A]_{R_{q}}$ = not
feasible.

Otherwise, the Chase step is consistent. When the Chase step is consistent, it
means that there are no contradictions and the target side of the GGD was
correctly enforced. By the end of the step, we can merge each node and each
edge in $[x]_{R_{q}}$ and also its range classes $[x.A]_{R_{q}}$.

#### Chase - Termination

\- The Chase procedure terminates if and only if one of the following
conditions holds:

  1. 1.

There are no possible updates/expansions on $G$ according to any
$\sigma\in\Sigma$. In this case, the Chase terminates and the Chase steps
sequence is valid.

  2. 2.

A Chase step is inconsistent. In this case, the Chase terminates and the Chase
steps sequence is invalid.

Figure 5: Chase Application of $\sigma_{\gamma}$

###### Example 6

Figure 5 shows the final results of the graph $G_{1}$ after the application of
$\sigma_{\gamma}$. Observe that, to enforce the GGD $\sigma_{\gamma}$, new
nodes of the label “Place” and new edges of the label “isLocatedIn” were
generated. Since in $\sigma_{\gamma}$, the target differential constraints
$\phi_{t}=\emptyset$, then the nodes and edges were generated without
attributes.

#### The Problem of Chase Termination

Analogous to tgds and ctgds, given the generating property of the GGDs, the
Chase might not terminate even when there are no inconsistent Chase steps
[22]. Termination of different versions of the Chase procedure for tgds have
been long studied in the literature [29, 30, 28]. In general, the Chase
termination problem for tgds is not decidable but there are positive results
on sets of tgds with specific syntactic properties [29].

A well-known property that has been proven that the Chase procedure terminates
is when the set of tgds is weakly-acyclic. Informally, a set of tgds is
weakly-acyclic if there is no cascading of generating null values during the
Chase procedure [31]. The problem of checking if a set of tgds is weakly-
acyclic is polynomial in the size of the set [28] as it is verified by
building a directed graph called dependency graph derived from the set of tgds
(see details in [31]). Besides weak-acyclicity, other generalizations and
properties of sets of tgds that can ensure Chase termination have been
identified in the literature (see [28] for a survey).

#### Use of Chase for Repairing Graphs with GGDs

The Chase procedure is often used in the literature as a method to repair data
according to a set of dependencies [4, 8, 2]. The repairing problem for the
GGDs can also be seen as a method to enforce the target constraints of each
GGD in a graph, which is the goal of the proposed Chase for GGDs. However, the
Chase will always generate new nodes and edges which is a naive solution and
might not always generate useful information. Therefore, new strategies should
be proposed to choose when to generate and when to modify the existing graph.
The problem of graph data repair using GGDs will be addressed in future work.

##  7 Reasoning for GGDs

In this section, we discuss the three following fundamental problems and their
complexity:

  * •

_Validation_ \- Given a set of GGDs $\Sigma$ and a non-empty graph $G$, does
the set of GGDs $\Sigma$ hold in $G$, denoted as $G\models\Sigma$?

  * •

_Satisfiability_ \- A set of GGDs $\Sigma$ is satisfiable if (i) there exists
a graph $G$ which is a model of $\Sigma$ ($G\models\Sigma$) and (ii) for each
GGD $\sigma\in\Sigma$ there exists a match of $Q_{s}[\overline{x}]$ in $G$.
Given a set $\Sigma$, is $\Sigma$ satisfiable?

  * •

_Implication_ \- Given a set of GGDs $\Sigma$ and a GGD $\sigma$, does
$\Sigma$ imply $\sigma$, i.e. is $\sigma$ a logical consequence of $\Sigma$,
(denoted by $\Sigma\models\sigma$) for every non-empty graph G that satisfies
$\Sigma$?

###  7.1 Validation

We first study the validation problem for GGDs. This problem has already been
discussed in [11]. The validation problem for GGDs is defined as: Given a
finite set $\Sigma$ of GGDs and graph G, does $G\models\Sigma$ (i.e.,
$G\models\sigma$ for each $\sigma\in\Sigma$)? An algorithm to validate a GGD
$\sigma=Q_{s}[\overline{x}],\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}],\phi_{t}$ was proposed in [11]. This
algorithm returns true if the $\sigma$ is validated and returns false if
$\sigma$ is violated. Algorithm 1 summarizes the steps of the validation
algorithm.

Algorithm 1 Validation of Graph Generating Dependency

1:procedure Validation($\sigma=Q_{s}[\overline{x}]\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}]\phi_{t}$, Graph $G$)

2: Search for matches of the source graph pattern, $\llbracket
Q_{s}[\overline{x}]\rrbracket_{G}$

3: for each match $h_{s}[\overline{x}]\in\llbracket
Q_{s}[\overline{x}]\rrbracket_{G}$ do

4: if $h_{s}[\overline{x}]$ satisfies the source differential constraints
(ie., $h_{s}[\overline{x}]\models\phi_{s}$) then

5: Search for matches of the target graph pattern $\llbracket
Q_{t}[\overline{x},\overline{y}]\rrbracket_{G}$ where for a match
$h_{t}(\overline{x},\overline{y})$ for all $x\in\overline{x}$ there is
$h_{s}(x)=h_{t}(x)$.

6: if $\llbracket Q_{t}[\overline{x},\overline{y}]\rrbracket_{G}=\emptyset$
then

7: return false

8: if $\not\exists h_{t}[\overline{x},\overline{y}]\in\llbracket
Q_{t}[\overline{x},\overline{y}]\rrbracket_{G}\models\phi_{t}$ then

9: return false

10: return true $\triangleright$ If the for loop ended without returning a
value then it means that the GGD is validated

Algorithm 1 is repeated for each $\sigma\in\Sigma$. For each match on which
$\sigma$ is violated, new vertices/edges can be generated in order to repair
it (i.e, in order to make the GGD $\sigma$ valid on $G$).

A problem in $\Pi_{2}^{P}$ complexity is a problem solvable by a
nondeterministic Turing machine with an oracle for a coNP problem [32]. Given
the complexity of evaluation of the source and target side of a GGD and its
semantics, to prove the complexity of the validation problem for GGDs we can
directly reduce it to a $\forall$-QSAT problem by adapting the reduction
presented in [33] for the evaluation of tgds.

Graph pattern matching queries can be expressed as conjunctive queries (CQ)
[9] which are well-known to have NP-complete evaluation complexity [33]. This
complexity has been proven in the literature by reducing the graph pattern
matching problem into a SAT problem [34, 35, 36]. Considering that the
complexity of evaluating the set of source and target differential
constraints, $\phi_{s}$ and $\phi_{t}$, is in P, the the cost of evaluating if
a graph pattern match satisfies a set of differential constraints is linear to
the number of differential constraints in this set. Hence, overall, the
complexity of evaluating the source and target constraints of a GGD separately
is dominated by the complexity of the evaluation of the graph patterns.

The $\forall$-QSAT problem has been proven to be in $\Pi_{2}^{P}$ complexity
[33, 32, 37], hence, the following theorem.

###### Theorem 1

The validation algorithm of GGDs is in $\Pi_{2}^{P}$ complexity.

The graph pattern matching problem is solvable in PTIME when the graph pattern
has bounded treewidth [6, 33], which corresponds to graph patterns covering
over 99% of graph patterns observed in practice [38]. Suppose that both source
and target graph pattern matching are both treewidth bounded. In this case, we
can substitute the NP complexity of evaluating the graph patterns by a P
complexity, and the overall complexity in this case drops to coNP complete
(see similar proof in [33]).

###  7.2 Satisfiability

A set of GGDs $\Sigma$ is satisfiable if: (i) there exists a graph $G$ which
is a model of $\Sigma$ ($G\models\Sigma$) and (ii) for each GGD
$\sigma\in\Sigma$ there exists a match of $Q_{s}[\overline{x}]$ in $G$. Then,
the satisfiability problem is to determine if a given set of GGDs $\Sigma$ is
satisfiable.

Before considering the general satisfiability problem as outlined above, we
discuss if a single GGD $\sigma$ of the set $\Sigma$ is satisfiable or not.
The satisfiability of a GGD $\sigma$ depends on the satisfiability of the sets
of differential constraints $\phi_{s}$ and $\phi_{t}$ and not on the
topological constraints (source and target graph patterns).

The satisfiability problem for differential constraints was studied by [12] in
the context of differential dependencies (DDs) for relational databases. A set
$\phi$ of differential constraints is unsatisfiable if the intersection of any
two differential constraints in $\phi$ is infeasible (see infeasibility
definition in Section 5). Observe an example of this case in Example 7.

Assuming that the set of source (and target) differential constraints
$\phi_{s}$ (and $\phi_{t}$) of each GGD $\sigma$ in the set $\Sigma$ is
satisfiable, we discuss the satisfiability of the _set_ of GGDs $\Sigma$, as
defined at the beginning of the section. Informally, the satisfiability
problem is to check if the GGDs defined in $\Sigma$ conflict with each other.
Similar to the previously proposed graph dependencies [6, 5], a set $\Sigma$
of GGDs may not be satisfiable.

Figure 6: Graph patterns in GGDs.

###### Example 7

Consider the graph pattern $Q_{1}$ shown in Figure 6. Suppose
$\phi_{s}=\\{(\delta_{type}(b.type,``full-time")=0)$,
$(\delta_{type}(b.type,``full-time")>1)\\}$. Observe that the differential
constraints in $\phi_{s}$ are disjoint. This means that it is not possible to
agree on all differential constraints of $\phi_{s}$, so $\phi_{s}$ is
infeasible.

###### Example 8

Consider the graph patterns shown in Figure 6 and the following two GGDs:
$\sigma_{1}=Q_{1}[a,b,c]\\{\emptyset\\}\rightarrow
Q_{3}[b,c,x]\\{\delta_{A}(b.A,\alpha)>10\\}$ and
$\sigma_{2}=Q_{2}[k,l,m,n,y]\\{\emptyset\\}\rightarrow
Q_{3}[b,c,x]\\{\delta_{A}(b.A,\alpha)\leq 10\\}$ in which $\alpha$ is a
constant value. There might exist matches of $Q_{1}$ and $Q_{2}$ that map to
the same nodes and edges for the labels {project, managedBy, employee}, even
though this implies the same target graph pattern, the constraints $\phi_{t}$
of $\sigma_{1}$ and $\sigma_{2}$ are disjoint. In consequence, these two GGDs
are not satisfiable.

GGDs defined with different graph patterns may interact with each other.
Additional challenges of the GGDs satisfiability compared to the proposed
graph dependencies in the literature are: (i) dealing with additional
complexity of GGDs target graph pattern $Q_{t}[\overline{x},\overline{y}]$
which is an extension of the source graph pattern and (ii) the checking of the
feasibility of differential constraints in $\phi_{t}$ in the cases in which
the graph pattern variables are mapped to the same nodes or edges of the graph
$G$. To analyse the satisfiability of a set of GGDs, we use the Chase
procedure presented in Section 6.

A set $\Sigma$ is said to be satisfiable if there exists a graph $G$ which is
a model of $\Sigma$ ($G\models\Sigma$) and for each GGD $\sigma\in\Sigma$
there exists a match of $Q_{s}[\overline{x}]\phi_{s}$ in $G$. To verify the
satisfiability of $\Sigma$, we build a canonical graph $G_{\Sigma}$ which
contains one match of the source side of each one of the GGDs in $\Sigma$. The
graph $G_{\Sigma}$ is defined as
$(V_{\Sigma},E_{\Sigma},\lambda_{\Sigma},\eta_{\Sigma},\nu_{\Sigma})$. Each
vertex $v\in V_{\Sigma}$ and each $e\in E_{\Sigma}$ are a tuple of
$(l,v,[v.R_{q}])$ in which $l$ and $v$ is the label and the variable alias of
the vertex/edge, respectively, and $[v.R_{q}]$ is the set of range classes
attached to this vertex/edge ($[v]_{R_{q}}$ and attribute range classes, i.e.
$[v.A]_{R_{q}}$). For each variable $x$ in $Q_{s}[\overline{x}]\phi_{s}$ of
$\sigma\in\Sigma$, we add $x$ to $G_{\Sigma}$ according to the following
steps:

  1. 1.

If $G_{\Sigma}$ is empty: (a) For each variable $x\in\overline{x}$, create a
range class for the variable $x$, $[x]_{R_{q}}$. Search for differential
constraints in $\phi_{s}$ that involve the variable $x$. For each of one of
the differential constraints, create a $rcq$ and add it to $[x]_{R_{q}}$. In
case the $rcq$ refers to a property of $x$, i.e. $x.A$, create and add the
$rcq$ to $[x.A]_{R_{q}}$. (b) If $x\in V_{Q}$ of $Q_{s}[\overline{x}]$, add a
node $x^{\prime}=(\lambda_{Q}(x),x,[x.R_{q}]$) to $V_{\Sigma}$,
$V_{\Sigma}=V_{\Sigma}\cup x^{\prime}$. (c) If $x\in E_{Q}$ of
$Q_{s}[\overline{x}]$, add an edge $x^{\prime}=(\lambda_{Q}(x),x,[R_{q}]$) to
$E_{\Sigma}$, $E_{\Sigma}=E_{\Sigma}\cup x^{\prime}$.

  2. 2.

If $G_{\Sigma}$ is not empty: (a) Check if $Q_{s}[\overline{x}]\phi_{s}$
interacts with $G_{\Sigma}$. (b) If there are no interactions, then repeat
step 1 for $Q_{s}[\overline{x}]\phi_{s}$. (c) If there are vertices and edges
in $G_{\Sigma}$ that interact which $Q_{s}[\overline{x}]\phi_{s}$, for each
variable $x\in Q_{s}[\overline{x}]\phi_{s}$ that interacts with $G_{\Sigma}$
to a node or edge which the variable alias is $x^{\prime}$, rename the
variable $x$ to $x^{\prime}$ in $\phi_{s}$ then update the set
$[x^{\prime}.R_{q}]$ in $G_{\Sigma}$.

###### Theorem 2

A set $\Sigma$ is satisfiable if and only if every Chase step of the Chase
procedure over $G_{\Sigma}$ is consistent and the Chase terminates.

#### Proof Sketch

\- First, we show that given a set of consistent Chase steps, there exists a
graph $G$ that can be derived from $G_{\Sigma}$ and is a model of $\Sigma$.

We assume that the Chase terminates and prove that every Chase step should be
consistent for a set to be Satisfiable. By contradiction, assume that there
exists a Chase step $(\sigma_{i},h_{s_{i}}[\overline{x}])$ on $G_{\Sigma}$, in
which $\sigma_{i}\in\Sigma$ and $h_{s_{i}}[\overline{x}]$ is a match of the
source on $G_{\Sigma}$, that is not consistent, we try to prove that $\Sigma$
is satisfiable. If the Chase step $(\sigma_{i},h_{s_{i}}[\overline{x}])$ is
not consistent, according to the Chase procedure it means that (1) there is a
label conflict or (2) the enforced differential constraints $\phi_{t}$ of
$\sigma_{i}$ are not feasible with the range classes of the matched nodes or
edges in $G_{\Sigma}$. If there is a label conflict then there exists two
nodes/edges $x$ and $x^{\prime}$ in $G_{\Sigma}$,
$\lambda_{\Sigma}(x)\neq\lambda_{\Sigma}(x^{\prime})$ and consequently $x\neq
x^{\prime}$, therefore the set $\Sigma$ is not satisfiable, contradicting our
assumption. If the enforced differential constraints are not feasible then
there are no values that can satisfy all the enforced constraints therefore
the set $\Sigma$ is not satisfiable (see consistency on differential
constraints [12]), contradicting our assumption.

If $\Sigma$ is satisfiable and Chase terminates and every Chase step is
consistent, assuming that $G_{\Sigma}^{\prime}$ is the final graph after
applying the Chase steps, we show that there exists a graph $G$ that can be
derived from $G_{\Sigma}^{\prime}$ that is a model of $\Sigma$. For each
$u\in(V\cup E)$ in $G_{\Sigma}^{\prime}$:

  1. 1.

if $u\in V$, create a node $v$ with the same label as $u$ and add it to $G$.
Respectively, if $u\in E$, create an edge $e$ with the same label and connect
the same nodes as $u$ in $G_{\Sigma}$ and add it to $G$. Next, we populate $v$
or $e$ attributes;

  2. 2.

for each node or edge $x$ in $[u]_{R_{q}}$, update $x$ attribute range classes
with $[u.A]_{R_{q}}$. This means for every attribute $A$ in $x$ and $u$,
$[u.A]_{R_{q}}=[x.A]_{R_{q}}$;

  3. 3.

for each attribute $A$ range class $[u.A]_{R_{q}}$, assign a distinct constant
values $c$ to $u.A$ such that $c\models[u.A]_{R_{q}}$. That means, assign a
value $c$ that can satisfy all the enforced differential constraints that are
represented in $[u.A]_{R_{q}}$.

Next, it suffices to show that the graph $G$ derived from
$G_{\Sigma}^{\prime}$, $G\models\Sigma$. Assume by contradiction that there
exists a GGD $\sigma=Q_{s}[\overline{x}]\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}]\phi_{t}\in\Sigma$ such that
$\sigma\not\models G$, that is, exists a match
$h_{s}[\overline{x}]\models\phi_{s}$ of $\sigma$ in $G$ but there does not
exist a match of the target $h_{t}[\overline{x},\overline{y}]\phi_{t}$ of
$\sigma$ in $G$. Since $G_{\Sigma}$ is built according to the source graph
pattern of $\Sigma$, we can ensure that all GGDs in $\Sigma$ will be applied
at least once in $G_{\Sigma}$, if every Chase step is consistent and
terminates, it means that $G_{\Sigma}^{\prime}\models\Sigma$. Given the $G$
construction procedure, we can conclude that $G$ and $G_{\Sigma}^{\prime}$ are
isomorphic and consequently $G\models\Sigma$, contradicting our assumption
that there exists a GGD $\sigma$ such that $\sigma\not\models G$.

Now, assume by contradiction that the Chase does not terminate and the set
$\Sigma$ is satisfiable. We are also assuming that every Chase step is
consistent, as if a Chase step is inconsistent then the Chase procedure
terminates. Given this assumption, if the Chase does not terminate, then,
according to the procedure in Section 6, it means that there is always a GGD
$\sigma\in\Sigma$ than can be applied and the Chase step will either update or
generate new nodes or edges in $G_{\Sigma}$. In practice, it means that there
is always a match of the source of $\sigma$ in $G_{\Sigma}$ that is not
validated. As a consequence, given that it is possible to derive a model graph
$G$ from $G_{\Sigma}$, if we construct $G$ from $G_{\Sigma}$ at any point of
the non-terminating Chase procedure the built $G\not\models\Sigma$ and
therefore $\Sigma$ is not satisfiable, contradicting our assumption.

Assume by contradiction that $\Sigma$ is not satisfiable, the Chase terminates
and every Chase step on $G_{\Sigma}$ is consistent. Since $\Sigma$ is not
satisfiable it means that there does not exist a graph model $G$ such that
$G\models\Sigma$. If the model graph does not exist it also means that either
does not exist $G_{\Sigma}$ or it is not possible to derive a graph $G$ from
the canonical graph $G_{\Sigma}$. Considering that the Chase terminates, if it
is not possible to derive a graph $G$ from $G_{\Sigma}$, it is not possible to
satisfy all enforced differential constraints for all nodes or edges to be
created in $G$ from $G_{\Sigma}$, which means that there are range classes in
nodes or edges that are not feasible. From this, we can affirm that there
exists a Chase step that is not consistent, contradicting our assumption. If
$G_{\Sigma}$ does not exist, then it means that the set $\Sigma$ is empty, as
$G_{\Sigma}$ is initially built from the source graph patterns of the GGDs in
$\Sigma$. If the set $\Sigma$ is empty, then it is not possible to apply the
Chase procedure therefore there does not exists any Chase step, contradicting
our assumption.

###  7.3 The Satisfiability Problem for Weakly-Acyclic GGDs

As mentioned previously, the Chase for GGDs might not always terminate (see
Section 6.1). Given the relationship between tgds and GGDs, we can also affirm
that deciding if the Chase will terminate for a set of GGDs is also
undecidable. As presented, knowing if the Chase can terminate is key for
checking the satisfiability of a set of GGDs and therefore we can deduce that
the satisfiability problem for GGDs is also undecidable.

However, research on tgds has identified that if a set of tgds is weakly-
acyclic (see Subsection 6.1) then all Chase versions and all sequences of tgds
will terminate [31, 28]. We can adapt such results from tgds on GGDs, as a
consequence, if a set of GGDs is weakly-acyclic then the Chase procedure
proposed terminates.

###### Theorem 3

The satisfiability problem of weakly-acyclic GGDs is in coNP.

Before checking the satisfiability, we need to check if a set of GGDs is
weakly-acyclic to ensure the termination of the Chase procedure. To check if a
set of GGDs is weakly acyclic we adapt the proposed algorithm in PTIME by the
authors in [31] for checking if a set of tgds is weakly acyclic. The main
difference is that GGDs also have differential constraints, so for building
the dependency graph proposed in [31], each node refers to an entity, and the
set of differential constraints referring to that entity according to a set of
GGDs. The alterations needed on the dependency graph construction do not
increase the complexity of the algorithm, therefore, the complexity remains in
PTIME.

###### Lemma 1

The complexity of checking if a set of GGDs is weakly-acyclic is in PTIME.

#### Proof Sketch of Theorem 3

\- We can summarize the process described for checking satisfiability of a set
$\Sigma$ as an coNP algorithm (an algorithm that checks disqualifications in
polynomial time) in which the two main steps are: (1) Build a canonical graph
$G_{\Sigma}$ and, (2) given any GGD $\sigma\in\Sigma$, apply each existing
match $h_{s}[\overline{x}]$ of the source graph pattern as a Chase step
$chase(h_{s}[\overline{x}],\sigma)$ in $G_{\Sigma}$ and check if the Chase
step is consistent or not. If there exists a Chase step that is not
consistent, the algorithm rejects $\Sigma$ (according to Theorem 2).

To prove its complexity is in coNP, we analyse each step of the algorithm. To
build the canonical graph $G_{\Sigma}$, we need to check the interaction on
the source of the GGDs in $\Sigma$ (see interaction definition on Section 5).
The interaction on the source (or the target) of the two GGDs can be defined
as the maximal subgraph pattern in which the source graph patterns of these
GGDs have in common. The maximal subgraph problem is a problem studied and
proven to be NP-hard [39].

Assuming that a GGD $\sigma$ can be applied to $G_{\Sigma}$ (there exists a
match of the source graph pattern of $\sigma$ in $G_{\Sigma}$), at each Chase
step we enforce the target side of $\sigma$ either by generating new nodes and
edges and initializing its range classes (in case a match of the target does
not exist) or by updating the existing range classes of the matched nodes and
edges according to $\phi_{t}$ of $\sigma$.

A Chase step is consistent if for all existing matches of the source of
$\sigma$ and matches of the target of $\sigma$ (generated or not), the range
classes of the matched nodes and edges are feasible. Given a GGD $\sigma$ and
$G_{\Sigma}$, we can rewrite the problem of checking if Chase steps are
consistent as:

$\forall(h_{s}[\overline{x}]\wedge
h_{t}[\overline{x},\overline{y}](R_{q}(h_{t}[\overline{x},\overline{y}])))$
(1)

in which, abusing of the notation, $R_{q}(h_{t}[\overline{x},\overline{y}])$
refers to the range classes of the matched nodes and edges of
$h_{t}[\overline{x},\overline{y}]$. It is known that matching a graph pattern
to a graph $G$ is equivalent to evaluating a conjunctive query in $G$, which
is proven to be in NP [27] by a reduction to a 3-SAT problem. Checking if
range classes are infeasible is comparable to checking if two differential
constraints are feasible. According to [12], the complexity of checking if two
differential functions on the same attribute of a relation are feasible is in
P by a reduction to a 2-SAT problem. Given these results, we can reduce (1) to
a TAUTOLOGY problem. A TAUTOLOGY problem is defined as, given a Boolean
formula, determine if every possible value assignment to variables of this
formula results in a true statement [37]. The TAUTOLOGY problem is proven to
be in coNP, proving that the complexity of the satisfiability problem is in
coNP.

###  7.4 Implication

The implication problem for GGDs is defined as: assuming a finite set $\Sigma$
of GGDs and a GGD $\sigma=Q_{s}[\overline{x}],\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}]\phi_{t}$, does $\Sigma\models\sigma$?

The implication problem is to define whether the GGD $\sigma$ is a logical
consequence of the set $\Sigma$. We use implication to minimize dependencies
and optimize data quality rules [5]. Here, we assume that the GGD set $\Sigma$
and the GGD $\sigma$ are satisfiable, and the set $\Sigma$ is irreducible.
That means that there is no GGD $\sigma_{\alpha}\in\Sigma$ that can be implied
from the set $\\{\Sigma-\sigma_{\alpha}\\}$. Note that since we are assuming
that $\\{\Sigma\cup\sigma\\}$ are satisfiable, the Chase procedure for this
set of GGDs always terminates (see Section 7.2).

Figure 7: Implication Example in GGDs

Similar to the satisfiability problem, the implication needs to consider the
interaction between the GGD $\sigma$ and the GGDs in $\Sigma$. However, the
satisfiability problem only needs to verify if there are any conflicts
regarding the source variables on the target side of the GGDs. On the other
hand, to solve the implication problem, we need to verify if it is possible to
derive/imply $\sigma$ source and target constraints from the GGDs in $\Sigma$.

To solve the implication problem, we use the Chase procedure we proposed
earlier. Here, we build a graph named $G_{closure}$ and use it as a tool to
identify if the implication holds. In $G_{closure}$, similar to $G_{\Sigma}$
in Section 7.2, each node and edge of $G_{closure}$ is a triple
$(l,v,[v.R_{q}])$. We initialize $G_{closure}$ with the source graph pattern
of $\sigma$ using the same procedure proposed to build $G_{\Sigma}$. The main
idea here is to use the Chase method to enforce the GGDs of $\Sigma$ on
$G_{closure}$ and check if all possible matches of the target side of $\sigma$
are covered in $G_{closure}$. If this is true, then it means that the same
result of $\sigma$ is enforced by the GGDs in $\Sigma$.

We say that $\sigma$ is deducible from $G_{closure}$, if there exists a match
of $Q_{t}[\overline{x},\overline{y}]\phi_{t}$ of $\sigma$ in $G_{closure}$ in
which the range classes of the matched nodes/edges subsumes the differential
constraints in $\phi_{t}$. Observe that in $G_{closure}$ we do not set
attribute values but instead use range classes that express all the possible
values an attribute can be assigned to.

###### Theorem 4

$\Sigma\models\sigma$ if and only if there exists a sequence of consistent
Chase steps on Chase($G_{closure},\Sigma$), and
$Q_{t}[\overline{x},\overline{y}]\phi_{t}$ of $\sigma$ is deducible from
$G_{closure}$.

#### Proof Sketch

Assuming that $\Sigma\models\sigma$, to prove the above theorem we first
consider two cases and prove it by contradiction: (1) there does not exist a
sequence of consistent Chase steps and (2) there exists a sequence of
consistent Chase steps and $Q_{t}[\overline{x},\overline{y}]\phi_{t}$ is not
deducible from $G_{closure}$. If there does not exist a sequence of consistent
Chase steps and $\\{\sigma,\Sigma\\}$ is satisfiable (there is a sequence of
consistent Chase steps in $G_{\Sigma}$, see Section 7.2) then it means that
there are no $\sigma_{i}\in\Sigma,$ in which there a match of the source of
$\sigma_{i},h_{s_{i}}[\overline{x}]$ that can be applied as a Chase step in
$G_{closure}$. Therefore, $\forall\sigma_{i}\in\Sigma,\not\exists
h_{s_{i}}[\overline{x}]$ in $G_{closure}$ and $\Sigma\not\models\sigma$,
contradicting our first assumption.

Considering that there exists a sequence of consistent Chase steps, we prove
that if we can deduce the target of $\sigma$ from $G_{closure}$, that means
for any possible graph $G$ in which the set $\Sigma$ is valid, the set of
matches of the target of $\sigma$ are contained in $G_{closure}$. We prove it
by contradiction, so assuming that $\Sigma\models\sigma$ and there exists a
sequence of consistent Chase steps
$((\sigma_{0},h_{s_{0}}[\overline{x}]),...,(\sigma_{x},h_{s_{x}}[\overline{x}]))$
on $G_{closure})$ in which $(\sigma_{0},....,\sigma_{x})\in\Sigma$, we prove
that there exists a graph $G$ that $(\sigma_{0},....,\sigma_{x})\models G$ and
$\llbracket
Q_{t}[\overline{x},\overline{y}]\phi_{t}\rrbracket_{G}\not\sqsubseteq
G_{closure}$.

If $\Sigma\models\sigma$, and there exists a sequence of consistent Chase
steps, then $G_{closure}\models\\{\Sigma\cup\sigma\\}$ (see Section 7.2). That
means $G_{closure}$ contains at least one match of the source side of $\sigma$
and there exists a match $h_{t_{\sigma}}[\overline{x},\overline{y}]$ of the
target side of $\sigma$ in $G_{closure}$. Since $\Sigma\models\sigma$, then
according to the Chase procedure, the range classes of the nodes and edges in
the match $h_{t_{\sigma}}[\overline{x},\overline{y}]$ subsume $\phi_{t}$. This
subsumption means that every possible value in $\phi_{t}$ it is covered by the
range classes of the match $h_{t_{\sigma}}[\overline{x},\overline{y}]$ in
$G_{closure}$. Conclusively, for every graph $G$ that $\Sigma\models G$ any
matches of the target side of $\sigma$ in $G$ can be represented by the match
$h_{t_{\sigma}}[\overline{x},\overline{y}]$ in $G_{closure}$.

Assume that there exists a sequence of consistent Chase steps and the target
$Q_{t}[\overline{x},\overline{y}]\phi_{t}$ is deducible from $G_{closure}$ and
$\Sigma\not\models\sigma$, we prove by contradiction that this is not correct.
Given the Chase procedure and that there exists a sequence of consistent Chase
steps, we can affirm that GGDs from the set $\Sigma$ were applied to
$G_{closure}$ and $\sigma$ was not. Now, if the target of $\sigma$ is
deducible from $G_{closure}$ it means that for every match of the source of
$\sigma$ in $G_{closure}$ there exists a match of the target of $\sigma$ in
$G_{closure}$, if $\sigma$ was not applied during Chase we can confirm that
$\Sigma\models\sigma$, contradicting our assumption that
$\Sigma\not\models\sigma$.

Figure 8: Chase procedure on Figure 7

###### Example 9

Given the GGDs in Figure 7 in which $\alpha$ and $\beta$ are two constant
values, does $\Sigma=\\{\sigma_{4},\sigma_{5}\\}\models\sigma_{6}$? Observe
Figure 8 in which we apply the Chase procedure to solve this problem. For the
means of presentation, in the figure, we show only the range classes of
properties used during Chase.

To verify if $\\{\sigma_{4},\sigma_{5}\\}\models\sigma_{6}$, the first step is
to initialize $G_{closure}$ with the source side of $\sigma_{6}$, since the
$\phi_{s}=\\{\emptyset\\}$ in $\sigma_{6}$, we initialize all range classes
with $\emptyset$. The next step is to apply a GGD in
$\\{\sigma_{4},\sigma_{5}\\}$ to $G_{closure}$. In this case, both GGDs
$\sigma_{4}$ and $\sigma_{5}$ are applicable, so we can choose to apply
$\sigma_{4}$ first. Given that the source constraint
$\phi_{s}=\\{\delta_{year}(s.year,\alpha)>2\\}$ is subsumed by the range class
of student in $G_{closure}$, we create a $rcq$ for this constraint and add it
to the range class of student. Next, we check if there exists a match of the
target of $\sigma_{4}$. Since the target does not exist, we create a new edge
and a new node and initialize its range classes according to $\phi_{t}$ of
$\sigma_{4}$.

Next, we use the same process and apply $\sigma_{5}$, observe that the range
class of $s.year$ subsumes the source constraint of $\sigma_{5}$ because of
the $\emptyset$, making $\sigma_{5}$ possible to apply. Following the same
procedure as in $\sigma_{4}$, we create a $rcq$ for $\phi_{s}$ and add it to
the $s.year$ range class. Next, we check the target of $\sigma_{5}$ in
$G_{closure}$, which we can easily verify that there exists a match and that
the range class of the node labeled ”learning activity” is subsumed by the
$\phi_{t}$ in $\sigma_{5}$. Given the subsumption property, we update the
range class of the node learning activity with the constraint in $\phi_{t}$.
In this case, the Chase terminates as applying any GGDs in
$\\{\sigma_{4},\sigma_{5}\\}$ will not cause any updates on $G_{closure}$.
Given the final $G_{closure}$, we can easily verify that the answer to this
implication is true as it is possible to deduce $\sigma_{6}$ from
$G_{closure}$.

###### Example 10

In Figure 7, we used as an example a set of GGDs with the same source and
target graph patterns. Here, we show an example of when we do not have the
same graph patterns. Given the GGDs $\sigma_{2}$ and $\sigma_{3}$ in Figure 2,
we rewrite it with differential constraints
$\sigma_{2^{\prime}}=\phi_{t}=\\{\delta_{hours}(a.hours,\alpha)\leq 4\\}$ and
$\sigma_{3^{\prime}}=\phi_{s}=\\{\delta_{hours}(a.hours,\alpha)\leq
8\\},\phi_{t}=\\{\delta_{duration}(c.duration,\beta)\leq 1\\}$, does
$\\{\sigma_{2^{\prime}},\sigma_{3^{\prime}}\\}\models\sigma_{7}(\phi_{s}=\\{\emptyset\\},\phi_{t}=\\{\delta_{duration}(c.duration,\beta)\leq
2\\})$ (Figure 7)? Observe in Figure 9 the initial $G_{closure}$ and the final
$G_{closure}$ after the Chase procedure. From the final version of
$G_{closure}$ we can verify that
$\\{\sigma_{2^{\prime}},\sigma_{3^{\prime}}\\}\models\sigma_{7}$ is true.

Figure 9: Chase on Transitive GGDs

###### Theorem 5

The implication problem for GGDs is in coNP.

#### Proof Sketch

\- We can summarize the steps of the complexity algorithm as:

  1. 1.

Build $G_{closure}$.

  2. 2.

Execute the Chase procedure $Chase(\Sigma,G_{closure})$ until it terminates
and verify if each Chase step is consistent. If a Chase step is not
consistent, then return false and reject $\Sigma$.

  3. 3.

Verify if it is possible to deduce the target side of $\sigma$ from the
resulting $G_{closure}$. If yes, then return true. Otherwise, return false and
reject $\Sigma$.

To analyse the complexity of this Chase procedure, we analyse the complexity
of the each step. $G_{closure}$ is initialized by just the source graph
pattern of $\sigma$, which means that there is no need to check for
interaction in case $G_{closure}$ is not empty and consequently the
initialization of $G_{closure}$ is in PTIME. After initializing $G_{closure}$,
the next step is to apply $Chase(\Sigma,G_{closure})$ and check if each Chase
step is consistent or not. This step are the exact same steps as shown in the
proof of Theorem 3 and proved to be in coNP.

If there are only consistent steps, it suffices to check if the target of
$\sigma$ can be deduced from the resulting $G_{closure}$ after Chase
terminates (observe that we assume that $\\{\Sigma\cup\sigma\\}$ is
satisfiable and, therefore, the Chase procedure terminates for this set). This
procedure is comparable to checking if there exists a match of the target of
$\sigma$ in $G_{closure}$ which can be done in polynomial time. If it does not
exist, then the implication is false and $\Sigma$ is rejected. Therefore, the
implication problem is in coNP.

##  8 GGDs for Data Inconsistencies: An Experimental Study

In this section, we discuss and demonstrate the practical use and the
feasibility of GGDs to find data inconsistencies (matches of the source graph
pattern that are not validated). Finding inconsistent data is the first step
to identifying data in the graph that should be repaired.

Given a set of GGDs $\Sigma$, we define as inconsistent data according to
$\Sigma$ as: set of graph pattern matches of the source side of each GGD in
which the target does not hold.

In the following subsections, we give details on the implementation and
experiments setup (Subsection 8.1) and an analysis on the impact in execution
time according to different aspects of using GGDs.

###  8.1 Implementation and Experiment Set Up

From the definition of inconsistent data we can observe that this problem is
related to check if a set of GGDs, $\Sigma$, is violated or not. For this
reason, to identify inconsistent data, we modify the previously introduced
validation algorithm (Algorithm 1) to, instead of returning true or false if
the set is validated or not, return which matches of the source
($h_{s}(Q_{s}[\overline{x})\models\phi_{s}$) were not validated. Algorithm 2
presents the modified validation algorithm for identifying data
inconsistencies.

Algorithm 2 Inconsistent Data Identification according to GGDs

1:procedure DataInconsistency($\sigma=Q_{s}[\overline{x}]\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}]\phi_{t}$, Graph $G$)

2: Violated $\leftarrow\emptyset$ $\triangleright$ Set of Violated source
matches

3: Search for matches of the source graph pattern, $\llbracket
Q_{s}[\overline{x}]\rrbracket_{G}$

4: for each match $h_{s}[\overline{x}]\in\llbracket
Q_{s}[\overline{x}]\rrbracket_{G}$ do

5: if $h_{s}[\overline{x}]$ satisfies the source differential constraints
(ie., $h_{s}[\overline{x}]\models\phi_{s}$) then

6: Search for matches of the target graph pattern $\llbracket
Q_{t}[\overline{x},\overline{y}]\rrbracket_{G}$ where for a match
$h_{t}(\overline{x},\overline{y})$ for all $x\in\overline{x}$ there is
$h_{s}(x)=h_{t}(x)$.

7: if $\llbracket Q_{t}[\overline{x},\overline{y}]\rrbracket_{G}=\emptyset$
then

8: Violated $\leftarrow$ Violated $\cup$ $h_{s}[\overline{x}]$

9: if $\not\exists h_{t}[\overline{x},\overline{y}]\in\llbracket
Q_{t}[\overline{x},\overline{y}]\rrbracket_{G}\models\phi_{t}$ then

10: Violated $\leftarrow$ Violated $\cup$ $h_{s}[\overline{x}]$

11: return Violated $\triangleright$ If the GGD $\sigma$ is validated then the
Violated set is empty

Previous works proposed such algorithm in their own scenarios using a parallel
algorithm [6]. Following the same strategy, we implement our algorithm using
Spark framework111https://spark.apache.org/, more specifically, using the
capabilities of SparkSQL to query and handle large scale data.

Dataset | Number of Nodes | Number of Edges | Number of GGDs
---|---|---|---
DBPedia Athlete | 1.3M | 1.7M | 4
LinkedMDB | 2.2M | 11.2M | 6
LDBC SNB | 11M | 66M | 6
Table 1: Datasets used in our experiments

We used real-world datasets to verify the feasibility of using GGDs on real-
world data and a synthtetic dataset to verify the impact of different aspects
of GGDs on execution time. The LinkedMDB and the DBPedia datasets are real-
world RDF [40] datasets, to use it in our implementation, we transformed it
into property graphs. For DBPedia, we extracted a subset of nodes and
relationships that refer to sports athletes, events and teams. We named this
subset as DBPedia Athlete. The LDBC SNB (Social Network Benchmark)
dataset222https://github.com/ldbc/ldbc_snb_datagen_spark is a synthetic
dataset that can be generated with different scale factors. The scale factor
indicates the size of the dataset, the numbers in Table 1 are the total number
of edges and nodes according to scale factor (SF) = $3$. See Table 1 for
details about the datasets.

We manually defined the GGDs according to the schema of each graph. In the
case of LinkedMDB and DBPedia Athlete, besides the schema information of when
we transformed it into a property graph, we also used the results of the
RDFind algorithm. RDFind
[21]333https://hpi.de/naumann/projects/repeatability/data-profiling/cind-
discovery-on-rdf-data.html is an algorithm for finding conditional inclusion
dependencies on RDF data. As mentioned in Section 2 conditional inclusion
dependencies are a special case of tgds.

Given the differences of the RDF and the property graph model, we cannot
translate directly one CIND on RDF to a GGD on property graphs, instead, we
included the main information given by the CINDs into the graph pattern of a
GGD. Given an example CIND $(s,(p=rdf\wedge
o=gradStudent))\subseteq(s,p=underGradFrom)$, we show on Figure 10 how we used
the information of this CIND in a GGD.

Figure 10: Including constraint information from a CIND in RDF into a GGD

For the LDBC dataset we manually defined a set of 6 different GGDs, in which 3
of them are fully validated and, 3 of them are highly violated. For the
LinkedMDB and the DBPedia dataset, we defined a set of 6 and 4, respectively,
of different GGDs, each taking into consideration the RDFind algorithm
results. The set of GGDs defined for each dataset can be found on Appendix. We
defined as our input, GGDs in which the target graph pattern has at least one
common variable to the source graph pattern.

To implement the GGDs data inconsistencies algorithm, we used the G-Core
language interpreter444https://ldbcouncil.org/gcore-spark/ [41] to query graph
patterns using SparkSQL and implemented the algorithm in Scala using the Spark
framework. The G-Core language is used for querying the graph patterns, the
G-Core language interpreter is responsible for rewritting the G-Core queries
into SparkSQL queries. We use a relational representation of the property
graphs in which each table represents a label.

Given this setup, we implemented two versions of the validation for data
inconsistencies algorithm using SparkSQL555Our implementation is available at
https://github.com/smartdatalake/gcore-spark-ggd. We show both versions as a
simplified set of commands in SparkSQL dataframe API in Algorithms 3 and 4.

Algorithm 3 LeftAntiJoin-Validation

procedure DataInconsistency($\sigma=Q_{s}[\overline{x}]\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}]\phi_{t}\in\Sigma$) $\triangleright$ This
procedure is repeated for each GGD in the set $\Sigma$

source_df $\leftarrow\\{h(Q_{s}[\overline{x})\\}$ $\triangleright$ Search for
matches of the source graph pattern

source_df.filter($\phi_{s}$) $\triangleright$ Checks which matches of the
source graph pattern holds the constraints in $\phi_{s}$

target_df $\leftarrow\\{h(Q_{t}[\overline{x},\overline{y}]\\}$

target_df.filter($\phi_{t1}$) $\triangleright$ Set of matches of the target
graph pattern that holds the constraints in $\phi_{t}$ that are exclusively
constraints of variables that are present only in the target graph pattern

source_target_df $\leftarrow$ source_df INNER JOIN target_df ON $\overline{x}$

source_target_df.filter($\phi_{t2}$) $\triangleright$ All validated matches

violated_df $\leftarrow$ source_df LEFT ANTI JOIN source_target_df ON
$\overline{x}$

return violated

Algorithm 4 LeftOuterJoin-Validation

procedure DataInconsistency($\sigma=Q_{s}[\overline{x}]\phi_{s}\rightarrow
Q_{t}[\overline{x},\overline{y}]\phi_{t}\in\Sigma$) $\triangleright$ This
procedure is repeated for each GGD in the set $\Sigma$

source_df $\leftarrow\\{h(Q_{s}[\overline{x})\\}$ $\triangleright$ Search for
matches of the source graph pattern

target_df $\leftarrow\\{h(Q_{t}[\overline{x},\overline{y}]\\}$

source_target_df $\leftarrow$ source_df LEFT OUTER JOIN target_df ON
$\overline{x}$

source_target_df.filter($\phi_{s}$) $\triangleright$ All matches of the source
that should be validated

violated_df $\leftarrow$
source_target_df.filter($\overline{\phi_{t}}||(\not\exists\overline{y}$))

return violated

In the first version, we used “left anti joins” to check for data
inconsistencies and in the second version we used “left outer joins”. This
choice of operators was based on the works on validation over tgds of the
literature in the scenario of validating schema mapping [42, 43]. These works
use the EXISTS operator in SQL to verify if the schema mapping can be
validated, in our case we translate it to left-anti and left-outer joins since
in here we are dealing with (possibly) different graph patterns. While there
is room for optimization and improvement on the implementation, the goal is to
show how GGDs are feasible even when using an available query engine such as
SparkSQL.

For checking the differential constraints, we applied two strategies: (1) if
the differential constraint compares two attributes (properties) of two
different nodes or edges which are connected in the graph pattern, or, the
differential constraint compares an attribute (property) to a constant value,
then we check if the differential constraint holds on each graph pattern match
(linear scan of the graph pattern match table); (2) if the differential
constraints compare two attributes (properties) of two different nodes of
edges that are not connected. To avoid a Cartesian product, we include
similarity search and joins operators to speed up the process. In the
implementation, we used Dima’s system [44] operators and integrated them into
SparkSQL for both Jaccard and Edit distance. In this case, we use the
similarity join between the matches of each disconnected part of the graph
pattern.

Dataset | GGD | Source matches | Violated matches | LeftAnti | LeftOuter
---|---|---|---|---|---
LDBC | 1 | 3182834 | 3078209 | 5.66 | 6.38
LDBC | 2 | 270602 | 0 | 0.48 | 0.53
LDBC | 3 | 3835041 | 0 | 3.39 | 4.6
LDBC | 4 | 634081 | 0 | 1.21 | 4.93
LDBC | 5 | 10477317 | 9387084 | 73.41 | 205.73
LDBC | 6 | 27133 | 26265 | 1.76 | 3.33
LinkedMDB | 1 | 21966 | 3603 | 3.04 | 3.48
LinkedMDB | 2 | 15220 | 0 | 4.11 | 4.54
LinkedMDB | 3 | 98816 | 98812 | 2.94 | 3.31
LinkedMDB | 4 | 71734 | 71547 | 2.52 | 2.84
LinkedMDB | 5 | 1613873 | 329718 | 6.72 | 7.41
LinkedMDB | 6 | 196367 | 194841 | 4.18 | 4.48
DBPedia | 1 | 9495 | 9495 | 7.61 | 7.59
DBPedia | 2 | 2388 | 1089 | 5.42 | 5.41
DBPedia | 3 | 17 | 17 | 4.9 | 4.87
DBPedia | 4 | 389 | 386 | 4.63 | 4.55
Table 2: Number of source matches to be validated and number of violated
matches according to the GGDs of the tested dataset. The execution time shown
in LeftAnti and LeftOuter are in minutes.

###  8.2 Impact of the selectivity of each GGD

In this section, we analyse the selectivity of each GGD, this means how the
number of matches of the source and number violations can affect the execution
time. To do so, we executed each one of the GGDs of each one of the datasets
separately in both of the implementations we presented earlier. Table 2 shows
the results of this experiment.

From these results, we can observe that overall the greater the number of
source matches and the smaller the number of violations the more time it takes
to execute the validation algorithm. It also depends not only on the number of
matches but also on the graph pattern in itself. This is related to
conjunctive query evaluation mentioned in Section 7.1 (see also [43] for a
study of the main aspects that can affect the execution time of a SPARQL [45]
graph query).

We can also observe that in the case of DBPedia Athlete, which is the smallest
graph we used in these experiments, the difference in execution time between
the validation using the LeftAnti algorithm and the LeftOuter algorithm are
very similar, being the LeftOuter algorithm faster than than the LeftAnti.
However, if we compare the execution time of both algorithms in the LinkedMDB
dataset or the LDBC dataset, in both cases, the left outer algorithm is
slower. This difference is more pronounced when the number of source graph
patterns matched are higher (see GGD number 5 of LDBC and LinkedMDB in Table
2).

###  8.3 Impact of the differential constraints threshold

Next, we used three different GGDs to test their behavior according to the
increase of the threshold in the differential constraints. The three different
GGDs tested are in Figure 11 and its respective execution time are presented
in Figure 12. The GGDs (a) and (b) are GGDs in which there is a connection in
the graph pattern between the nodes/edges. In this case, the constraint
checking procedure is to check match by match of the graph pattern if the
differential constraint holds for that match. Observe in (a) and (b) the
execution time results according to the increase of the threshold for both of
these GGDs.

Figure 11: Tested GGDs according to the differential constraint threshold
Figure 12: Execution time of the GGDs in Figure 11 according to the
differential constraint threshold (Left Anti Join)

A special case of GGD is the GGDs represented by (c) in which the only
connection between the nodes in the graph pattern is the differential
constraint. In this case, when searching for the source graph pattern matches
alone would result in the execution of a cartesian product. To avoid this
expensive operation, we use a similarity join operator to search for the
source graph patterns. We first match each disconnected part of the graph
pattern separately and then use the similarity join operator to find the
matches of the source side.

Observe that the difference in execution time according to the threshold of
the cases (a) and (b) are very small compared to (c). This happens because,
since the constraint checking procedure is done match per match, the number of
times the constraint will be checked is the same, as the number of matches of
the graph pattern, independently of the threshold. This is aligned with the
complexity analysis of the validation algorithm in Section 7.1 in which the
graph pattern is the most expensive ”part” of matching the source or the
target. In this case, the increase in execution time is because of the number
of source matches that need to be validated, as the threshold increases the
number of source matches to be validated also increases. As an example, Table
3 shows the number of source matches to be validated according to GGD (a).

However, when there is a need for the similarity join operator, the increase
in execution time is more accentuated by the increase of the threshold
because, besides the consequent increase in the number of sources to be
validated, the cost of performing a similarity join increases as well (see
[46] for more details on string similarity join algorithms).

Source matches | Violated matches | Threshold (Edit distance)
---|---|---
27133 | 26265 | 0
50018 | 48952 | 2
187709 | 185247 | 4
493646 | 488217 | 6
650125 | 643051 | 8
688305 | 680805 | 10
Table 3: Number of Source Matches to be Validated and Number of Violated
Matches according to GGD (a) of Figure 11 for LDBC Dataset (scale factor = 3)

###  8.4 Impact of the size of the data

To analyze the scalability of the validation algorithm we analyzed how the
same set of GGDs affects time execution according to the increasing size of
data. We generated the LDBC Social Network dataset with different scale
factors to simulate the increasing size of data. The Table 4 contains
information about the approximate number of nodes and edges according to the
different scale factors.

Scale Factor | Number of Nodes | Number of Edges
---|---|---
0.1 | 500.000 | 2M
0.3 | 1M | 6M
1.0 | 4M | 22M
3.0 | 11M | 66M
Table 4: LDBC Size according to different Scale Factors

The results in Figure 13 shows that as the data size grows the execution time
also grows, as expected. We can see in special an substantial increase in the
execution time for both versions between the scale factor $0.3$ and $1$ as
both number of nodes and edges have almost quadruplicated.

Figure 13: Scalability of the validation according to the Scale Factor of LDBC

Lastly, we run the full validation on the set of GGDs in each one of the
datasets. The execution time for all of the datasets are in Table 5. In all of
the datasets, the full validation of the set of GGDs was completed in a
feasible time for both versions of implementation. For DBPedia Athlete and
LinkedMDB, the execution time was similar, while for LDBC the execution time
for the Left Outer algorithm was significantly worst, following the results
reported in Subsection 8.4. Given the expressivity power of GGDs and the
ability to use user-defined differential constraints a small set of GGDs, such
as the ones tested in these experiments, depending on the data, can be enough
to represent the interesting constraints for different practical applications.

Dataset | Number of GGDs | LeftAnti (in min.) | Outer (in min.)
---|---|---|---
DBPedia Athlete | 4 | 22.48 | 22.46
LinkedMDB | 6 | 25.75 | 25.77
LDBC | 6 | 78.25 | 222.37
Table 5: Execution time for full validation of the GGDs

###  8.5 Experimental Results Conclusion

In the experiments presented in this section, we showed that even though the
validation algorithm has high complexity (Section 7.1), we showed that using
GGDs for identifying data inconsistency is feasible. Thus, the algorithm can
be easily implemented using an available platform/framework.

There are, nevertheless, a lot of space for optimizing the algorithm
presented, for example, new techniques for graph pattern matching, similarity
searching (for the differential constraints), and the use of other types of
frameworks or architectures that are more suitable to the problem (improving
the Spark framework setup instead of running in a single machine, for
example). To understand the behavior and which aspects of GGDs can affect the
execution time (and should later be taken into consideration in algorithm
optimizations), we evaluated three main aspects: (1) how the number of source
graph pattern matches affects time, (2) how the threshold in the differential
constraint affects time, and (3) how the algorithm scales (according to this
implementation).

From the results, we could observe that the higher the number of source
matches to be evaluated the higher the execution time. This also correlates to
the differential constraints threshold as the bigger the threshold in the
differential the higher the number of source matches to evaluate. However, it
also depends on the cost of the source graph pattern evaluation, i.e., a GGD
that has a more costly source graph pattern takes more time to execute
compared to a less costly one even when the number the of source matches and
violated are the same. These two aspects (1) number of source matches and (2)
cost of the graph pattern evaluation should be taken into consideration when
proposing optimization techniques. We also verified that for the same set of
GGDs, the algorithm that uses left-anti joins scales better than the one that
uses left-outer joins, giving some indication on which operators/strategy fits
better in terms of implementation for a better scalable algorithm. In future
work, we plan take these results into consideration and propose an optimized
version of the evaluated algorithm.

##  9 Conclusion and Future Work

Motivated by practical applications in graph data management, we studied three
main reasoning problems for a new class of graph dependencies called Graph
Generating Dependencies (GGDs). GGDs are inspired by the tuple-generating
dependencies and the equality-generating dependencies from relational data,
where constraint satisfaction can generate new vertices and edges.

In this paper, we proposed algorithms for solving three fundamental reasoning
problems of GGDs, satisfiability, implication, and validation. To prove the
complexity of such algorithms we propose a Chase procedure for GGDs based on
the standard Chase for tgds and GEDs. Even though our results show that the
reasoning problems of GGDs have high complexity, in our experimental results
we verify how GGDs are feasible to be used in practice to identify data
inconsistencies. In our experimental results, we also analysed the impact of
the size of the data and the differential constraints on a set of GGDs. In
future work, we plan to study the discovery of GGDs and their applications in
graph data profiling and cleaning.

Acknowledgments. This project has received funding from the European Union’s
Horizon 2020 research and innovation programme under grant agreement No
825041.

## References

  * [1] P. Barceló, J. Pérez, J. Reutter, Schema mappings and data exchange for graph databases, in: Proceedings of the 16th International Conference on Database Theory, ICDT ’13, Association for Computing Machinery, New York, NY, USA, 2013, p. 189–200.  doi:10.1145/2448496.2448520.
  * [2] P. Bohannon, W. Fan, F. Geerts, X. Jia, A. Kementsietsidis, Conditional functional dependencies for data cleaning, in: 2007 IEEE 23rd International Conference on Data Engineering, 2007, pp. 746–755.  doi:10.1109/ICDE.2007.367920.
  * [3] W. Fan, F. Geerts, Foundations of data quality management, Synthesis Lectures on Data Management, Morgan & Claypool Publishers, 2012.
  * [4] W. Fan, Dependencies for graphs: Challenges and opportunities, J. Data and Information Quality 11 (2).  doi:10.1145/3310230.
  * [5] W. Fan, P. Lu, Dependencies for graphs, ACM Trans. Database Syst. 44 (2).  doi:10.1145/3287285.
  * [6] W. Fan, Y. Wu, J. Xu, Functional dependencies for graphs, in: Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, Association for Computing Machinery, New York, NY, USA, 2016, p. 1843–1857.  doi:10.1145/2882903.2915232.
  * [7] N. Francis, L. Libkin, Schema mappings for data graphs, in: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’17, Association for Computing Machinery, New York, NY, USA, 2017, p. 389–401.  doi:10.1145/3034786.3056113.
  * [8] I. F. Ilyas, X. Chu, Data Cleaning, Association for Computing Machinery, New York, NY, USA, 2019.
  * [9] A. Bonifati, G. Fletcher, H. Voigt, N. Yakovets, Querying Graphs, Morgan & Claypool Publishers, 2018.
  * [10] S. Kwashie, L. Liu, J. Liu, M. Stumptner, J. Li, L. Yang, Certus: An effective entity resolution approach with graph differential dependencies (gdds), Proc. VLDB Endow. 12 (6) (2019) 653–666.  doi:10.14778/3311880.3311883.
  * [11] L. C. Shimomura, G. Fletcher, N. Yakovets, Ggds: Graph generating dependencies, in: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, CIKM ’20, Association for Computing Machinery, New York, NY, USA, 2020, p. 2217–2220.  doi:10.1145/3340531.3412149.
  * [12] S. Song, L. Chen, Differential dependencies: Reasoning and discovery, ACM Trans. Database Syst. 36 (3).  doi:10.1145/2000824.2000826.
URL https://doi.org/10.1145/2000824.2000826

  * [13] W. Fan, F. Geerts, X. Jia, A. Kementsietsidis, Conditional functional dependencies for capturing data inconsistencies, ACM Trans. Database Syst. 33 (2).  doi:10.1145/1366102.1366103.
  * [14] S. Kwashie, J. Liu, J. Li, F. Ye, Mining differential dependencies: A subspace clustering approach, in: H. Wang, M. A. Sharaf (Eds.), Databases Theory and Applications, Springer International Publishing, Cham, 2014, pp. 50–61.
  * [15] S. Kwashie, J. Liu, J. Li, F. Ye, Efficient discovery of differential dependencies through association rules mining, in: M. A. Sharaf, M. A. Cheema, J. Qi (Eds.), Databases Theory and Applications, Springer International Publishing, Cham, 2015, pp. 3–15.
  * [16] S. Song, L. Chen, H. Cheng, Efficient determination of distance thresholds for differential dependencies, IEEE Transactions on Knowledge and Data Engineering 26 (9) (2014) 2179–2192.  doi:10.1109/TKDE.2013.84.
  * [17] C. Beeri, M. Y. Vardi, A proof procedure for data dependencies, J. ACM 31 (4) (1984) 718–741.  doi:10.1145/1634.1636.
  * [18] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: Semantics and query answering, in: D. Calvanese, M. Lenzerini, R. Motwani (Eds.), Database Theory — ICDT 2003, Springer Berlin Heidelberg, Berlin, Heidelberg, 2003, pp. 207–224.
  * [19] S. Ma, W. Fan, L. Bravo, Extending inclusion dependencies with conditions, Theoretical Computer Science 515 (2014) 64–95.  doi:https://doi.org/10.1016/j.tcs.2013.11.002.
  * [20] F. Dürsch, A. Stebner, F. Windheuser, M. Fischer, T. Friedrich, N. Strelow, T. Bleifuß, H. Harmouch, L. Jiang, T. Papenbrock, F. Naumann, Inclusion dependency discovery: An experimental evaluation of thirteen algorithms, in: Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. 219–228.  doi:10.1145/3357384.3357916.
  * [21] S. Kruse, A. Jentzsch, T. Papenbrock, Z. Kaoudi, J.-A. Quiané-Ruiz, F. Naumann, Rdfind: Scalable conditional inclusion dependency discovery in rdf datasets, in: Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, Association for Computing Machinery, New York, NY, USA, 2016, p. 953–967.  doi:10.1145/2882903.2915206.
  * [22] M. J. Maher, D. Srivastava, Chasing constrained tuple-generating dependencies, in: Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 1996, pp. 128–138.
  * [23] Y. Cheng, L. Chen, Y. Yuan, G. Wang, Rule-based graph repairing: Semantic and efficient repairing methods, in: 2018 IEEE 34th International Conference on Data Engineering (ICDE), 2018, pp. 773–784.  doi:10.1109/ICDE.2018.00075.
  * [24] W. Fan, X. Wang, Y. Wu, J. Xu, Association rules with graph patterns, Proc. VLDB Endow. 8 (12) (2015) 1502–1513.  doi:10.14778/2824032.2824048.
  * [25] M. Alipourlangouri, A. Mansfield, F. Chiang, Y. Wu, Temporal graph functional dependencies: Technical report (2022).  arXiv:2108.08719.
  * [26] M. S. H. Zada, B. Yuan, A. Anjum, M. A. Azad, W. A. Khan, S. Reiff-Marganiec, Large-scale data integration using graph probabilistic dependencies (gpds), in: 2020 IEEE/ACM International Conference on Big Data Computing, Applications and Technologies (BDCAT), 2020, pp. 27–36.  doi:10.1109/BDCAT50828.2020.00028.
  * [27] A. K. Chandra, P. M. Merlin, Optimal implementation of conjunctive queries in relational data bases, in: Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, STOC ’77, Association for Computing Machinery, New York, NY, USA, 1977, p. 77–90.  doi:10.1145/800105.803397.
  * [28] S. Greco, C. Molinaro, F. Spezzano, Incomplete data and data dependencies in relational databases, Synthesis Lectures on Data Management 4 (5) (2012) 1–123.
  * [29] M. Calautti, G. Gottlob, A. Pieris, Chase termination for guarded existential rules, in: Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’15, Association for Computing Machinery, New York, NY, USA, 2015, p. 91–103.  doi:10.1145/2745754.2745773.
  * [30] T. Gogacz, J. Marcinkowski, A. Pieris, All-instances restricted chase termination, in: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS’20, Association for Computing Machinery, New York, NY, USA, 2020, p. 245–258.  doi:10.1145/3375395.3387644.
  * [31] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: semantics and query answering, Theoretical Computer Science 336 (1) (2005) 89–124, database Theory.  doi:https://doi.org/10.1016/j.tcs.2004.10.033.
  * [32] C. Papadimitriou, Computational Complexity, Theoretical computer science, Addison-Wesley, 1994.
  * [33] R. Pichler, S. Skritek, The complexity of evaluating tuple generating dependencies, in: Proceedings of the 14th International Conference on Database Theory, ICDT ’11, Association for Computing Machinery, New York, NY, USA, 2011, p. 244–255.  doi:10.1145/1938551.1938583.
  * [34] P. Hell, J. Nešetřil, On the complexity of h-coloring, Journal of Combinatorial Theory, Series B 48 (1) (1990) 92 – 110.  doi:https://doi.org/10.1016/0095-8956(90)90132-J.
  * [35] L. M. Kirousis, P. G. Kolaitis, The complexity of minimal satisfiability problems, in: A. Ferreira, H. Reichel (Eds.), STACS 2001, Springer Berlin Heidelberg, Berlin, Heidelberg, 2001, pp. 407–418.
  * [36] T. Feder, M. Y. Vardi, The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory, SIAM Journal on Computing 28 (1) (1998) 57–104.  doi:10.1137/S0097539794266766.
  * [37] S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  * [38] A. Bonifati, W. Martens, T. Timm, An analytical study of large SPARQL query logs, VLDB J. 29 (2) (2020) 655–679.
  * [39] J. M. Lewis, On the complexity of the maximum subgraph problem, in: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, Association for Computing Machinery, New York, NY, USA, 1978, p. 265–274.  doi:10.1145/800133.804356.
  * [40] S. Decker, S. Melnik, F. van Harmelen, D. Fensel, M. Klein, J. Broekstra, M. Erdmann, I. Horrocks, The semantic web: the roles of xml and rdf, IEEE Internet Computing 4 (5) (2000) 63–73.  doi:10.1109/4236.877487.
  * [41] R. Angles, M. Arenas, P. Barcelo, P. Boncz, G. Fletcher, C. Gutierrez, T. Lindaaker, M. Paradies, S. Plantikow, J. Sequeda, O. van Rest, H. Voigt, G-core: A core for future graph query languages, in: Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, Association for Computing Machinery, New York, NY, USA, 2018, p. 1421–1432.  doi:10.1145/3183713.3190654.
  * [42] B. Alexe, B. ten Cate, P. G. Kolaitis, W.-C. Tan, Designing and refining schema mappings via data examples, in: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD ’11, Association for Computing Machinery, New York, NY, USA, 2011, p. 133–144.  doi:10.1145/1989323.1989338.
  * [43] A. Bonifati, G. Mecca, A. Pappalardo, S. Raunich, G. Summa, Schema mapping verification: The spicy way, in: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, EDBT ’08, Association for Computing Machinery, New York, NY, USA, 2008, p. 85–96.  doi:10.1145/1353343.1353358.
  * [44] J. Sun, Z. Shang, G. Li, D. Deng, Z. Bao, Balance-aware distributed string similarity-based query processing system, Proc. VLDB Endow. 12 (9) (2019) 961–974.  doi:10.14778/3329772.3329774.
  * [45] J. Pérez, M. Arenas, C. Gutierrez, Semantics and complexity of sparql, in: I. Cruz, S. Decker, D. Allemang, C. Preist, D. Schwabe, P. Mika, M. Uschold, L. M. Aroyo (Eds.), The Semantic Web - ISWC 2006, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006, pp. 30–43.
  * [46] Y. Jiang, G. Li, J. Feng, W.-S. Li, String similarity joins: An experimental evaluation, Proc. VLDB Endow. 7 (8) (2014) 625–636.  doi:10.14778/2732296.2732299.

##  Appendix A Input GGDs

This appendix contains the input GGDs that were manually defined for each one
of the datasets presented in the Section 8.1. The GGDs follows the same order
as presented in the results tables of Subsection 8.2.

Figure 14: Input GGDs: LDBC Dataset Figure 15: Input GGDs: LinkedMDB Dataset
Figure 16: Input GGDs: DBPedia Athlete