# From Shapes to Shapes: Inferring SHACL Shapes for Results of SPARQL
CONSTRUCT Queries (Extended Version)

Philipp Seifer  0000-0002-7421-2060 University of KoblenzKoblenzGermany
<EMAIL_ADDRESS>,  Daniel Hernández  0000-0002-7896-0875 University of
StuttgartStuttgartGermany<EMAIL_ADDRESS>,  Ralf Lämmel
0000-0001-9946-4363 University of KoblenzKoblenzGermany<EMAIL_ADDRESS>and  Steffen Staab  0000-0002-0780-4154 University of
StuttgartStuttgartGermany University of SouthamptonSouthamptonUK
<EMAIL_ADDRESS>
###### Abstract.

SPARQL CONSTRUCT queries allow for the specification of data processing
pipelines that transform given input graphs into new output graphs. It is now
common to constrain graphs through SHACL shapes allowing users to understand
which data they can expect and which not. However, it becomes challenging to
understand what graph data can be expected at the end of a data processing
pipeline without knowing the particular input data: Shape constraints on the
input graph may affect the output graph, but may no longer apply literally,
and new shapes may be imposed by the query template. In this paper, we study
the derivation of shape constraints that hold on all possible output graphs of
a given SPARQL CONSTRUCT query. We assume that the SPARQL CONSTRUCT query is
fixed, e.g., being part of a program, whereas the input graphs adhere to input
shape constraints but may otherwise vary over time and, thus, are mostly
unknown. We study a fragment of SPARQL CONSTRUCT queries (SCCQ) and a fragment
of SHACL (Simple SHACL). We formally define the problem of deriving the most
restrictive set of Simple SHACL shapes that constrain the results from
evaluating a SCCQ over any input graph restricted by a given set of Simple
SHACL shapes. We propose and implement an algorithm that statically analyses
input SHACL shapes and CONSTRUCT queries and prove its soundness and
complexity.

SHACL; semantic queries; SPARQL CONSTRUCT; data pipelines

††ccs: Information systems Graph-based database models††ccs: Information
systems Resource Description Framework (RDF)††ccs: Information systems Query
languages††ccs: Information systems Extraction, transformation and loading

##  1\. Introduction

Shape description languages like SHACL (Knublauch and Kontokostas, 2017) or
ProGS (Seifer et al., 2021) can play two different, but equally important
roles. _Normatively_ they impose schematic constraints on the evoluion of a
graph, such that a triple store may automatically reject illegitimate
configurations. Used _informatively_ , they aid software developers in
understanding graphs, or inform downstream applications, e.g., (Leinberger et
al., 2019).

Graph query languages like SPARQL CONSTRUCT or G-CORE (Angles et al., 2018)
allow for the composition of queries into data processing pipelines. To
execute a given pipeline, the developer must understand what it may output,
regardless of its inputs. Even if the possible inputs are well-described using
a shape language like SHACL, it becomes very challenging to understand which
shapes apply after one or several querying steps: SHACL constraints that apply
on the input graph may or may no longer apply, e. g., existential
quantification may become inapplicable because the corresponding relationship
might not be part of the WHERE clause, and new constraints may or may not be
imposed by the CONSTRUCT template. The developer may hold misconceptions about
the structure of the result graph, which might even seem to be endorsed by one
particular graph instance, but can lead to errors (e. g., when processing
query results within a program) for other valid instances of input graphs.

In this paper, we define the problem of computing a set of SHACL shapes
characterizing the possible output graphs of a SPARQL CONSTRUCT query based on
(1) the set of shapes applicable to input graphs, and (2) the graph patterns
and the template of the query. We present an algorithm for constructing a
sound upper approximation by statically analyzing shapes and query, relying on
an encoding in description logics, and _without_ referring to any specific
input graph. Thus, our approach allows for investigating data processing
pipelines regardless of what (valid) data will be encountered.

#### Outline

The paper is structured as follows. Section 2 introduces foundations,
including the fragment of SPARQL queries, SHACL shapes, and description logics
we rely upon. In Section 3 we formalize our validation problem. Throughout
Section 4, Section 5, and Section 6 we break the validation problem down into
subproblems, and present algorithms for solving them. We discuss related work
in Section 7 and conclude in Section 8. For an overview of the appendix, which
includes full proofs, extended examples, an overview of our
implementation111https://github.com/softlang/s2s including a feasibility
experiment thereof, as well as details on how the approach can be generalized
to a larger fragment of SHACL, see Appendix A.

##  2\. Foundations

We interpret all RDF classes, instances, and properties as description logic
concepts, individuals, and roles, respectively. For clarity, we always use
description logic terminology, e.g., we will refer to “concept” rather than
“RDF class”. We assume that $\mathbf{C}\subset\bar{\mathbf{C}}$,
$\mathbf{I}\subset\bar{\mathbf{I}}$, $\mathbf{R}\subset\bar{\mathbf{R}}$, and
$\mathbf{V}\subset\bar{\mathbf{V}}$ are _finite_ subsets of the four infinite,
pairwise disjoint sets $\bar{\mathbf{C}}$, $\bar{\mathbf{R}}$,
$\bar{\mathbf{I}}$, and $\bar{\mathbf{V}}$. We assume these finite sets to be
given as (sufficiently large) inputs to our problem in order to simplify
definitions. This is not a restriction as their size is arbitrary. We use
$A,B,E\in\mathbf{C}$ for description logic _concept names_ ,
$a,b,e\in\mathbf{I}$ for description logic _individual names_ ,
$p,r\in\mathbf{R}$ for description logic _role names_ , and
$w,x,y,z\in\mathbf{V}$ as SPARQL variables.

###  2.1. The Description Logic $\mathcal{ALCHOI}$

We use the description logic $\mathcal{ALCHOI}$ to define the semantics of RDF
graphs and SHACL shapes following the formalism by Bogaerts et al. (2022). We
next present the standard $\mathcal{ALCHOI}$ syntax and semantics defined in
Baader et al. (2003).

###### Definition 0 ($\mathcal{ALCHOI}$ concept descriptions).

$\mathcal{ALCHOI}$ _concept descriptions_ are defined by the following grammar

$\displaystyle C$ $\displaystyle\Coloneqq\top\mid\bot\mid A\mid\neg
C\mid\\{a\\}\mid C\sqcap C\mid C\sqcup C\mid\exists\rho.C\mid\forall\rho.C$
$\displaystyle\rho$ $\displaystyle\Coloneqq p\mid p^{-}$

where the symbols $\top$ and $\bot$ are two special concept names, and $A$,
$a$, and $p$ stand for concept names, individual names, and role names,
respectively. Given two concept descriptions $C$ and $D$, two individual names
$a,b\in\mathbf{I}$, and two role descriptions $\rho_{1},\rho_{2}$ (as defined
above), $C\sqsubseteq D$ and $\rho_{1}\sqsubseteq\rho_{2}$ are _axioms_ ,
$a{:}C$ is a _concept assertion_ and $(a,b){:}p$ is a _role assertion_. We
write $C\equiv D$ as an abbreviation for two axioms $C\sqsubseteq D$ and
$D\sqsubseteq C$, and likewise for $\rho_{1}\equiv\rho_{2}$.

An $\mathcal{ALCHOI}$ _knowledge base_ $\mathcal{K}$ is a pair
$(\mathcal{T},\mathcal{A})$ where $\mathcal{T}$ is a finite set of axioms and
$\mathcal{A}$ is a finite set of assertions. In a slight abuse of notation,
given an ABox $\mathcal{A}$, we write $\mathcal{A}$ to refer to the knowledge
base $(\emptyset,\mathcal{A})$, and given a TBox $\mathcal{T}$ we write
$\mathcal{T}$ to refer to $(\mathcal{T},\emptyset)$. An _interpretation_
$\mathcal{I}$ is a pair $(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$
consisting of a set $\Delta^{\mathcal{I}}$, called the _domain_ , and a
function $\cdot^{\mathcal{I}}$ such that we have for each individual name
$a\in\mathbf{I}$, an element $a^{\mathcal{I}}\in\Delta^{\mathcal{I}}$; for
each concept name $A\in\mathbf{C}$, a subset
$A^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}$; and for each role name
$p\in\mathbf{R}$, a relation
$p^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$.

The function $\cdot^{\mathcal{I}}$ is extended to concept descriptions as
follows: $\bot^{\mathcal{I}}=\emptyset$,
$\top^{\mathcal{I}}=\Delta^{\mathcal{I}}$,
$\\{a\\}^{\mathcal{I}}=\\{a^{\mathcal{I}}\\}$, $(C\sqcap
D)^{\mathcal{I}}=C^{\mathcal{I}}\cap D^{\mathcal{I}}$, $(C\sqcup
D)^{\mathcal{I}}=C^{\mathcal{I}}\cup D^{\mathcal{I}}$, $(\neg
C)^{\mathcal{I}}=\top^{\mathcal{I}}\setminus C^{\mathcal{I}}$,

$\displaystyle(\exists p.C)^{\mathcal{I}}$
$\displaystyle=\\{d\in\Delta^{\mathcal{I}}\mid(d,e)\in p^{\mathcal{I}}\
\text{with}\ e\in C^{\mathcal{I}}\\},$ $\displaystyle(\exists
p^{-}.C)^{\mathcal{I}}$ $\displaystyle=\\{d\in\Delta^{\mathcal{I}}\mid(e,d)\in
p^{\mathcal{I}}\ \text{with}\ e\in C^{\mathcal{I}}\\},$ $\displaystyle(\forall
p.C)^{\mathcal{I}}$ $\displaystyle=\\{d\in\Delta^{\mathcal{I}}\mid\text{for
all }e\in\Delta^{\mathcal{I}},$ $\displaystyle\qquad\qquad\qquad\text{if
}(d,e)\in p^{\mathcal{I}}\text{ then }e\in C^{\mathcal{I}}\\},$
$\displaystyle(\forall p^{-}.C)^{\mathcal{I}}$
$\displaystyle=\\{d\in\Delta^{\mathcal{I}}\mid\text{for all
}e\in\Delta^{\mathcal{I}},$ $\displaystyle\qquad\qquad\qquad\text{if }(e,d)\in
p^{\mathcal{I}}\text{ then }e\in C^{\mathcal{I}}\\}.$

An interpretation $\mathcal{I}$ is a _model_ of a knowledge base
$\mathcal{K}=(\mathcal{T},\mathcal{A})$ if and only if
$C^{\mathcal{I}}\subseteq D^{\mathcal{I}}$ for every axiom $C\sqsubseteq D$ in
$\mathcal{T}$, $p^{\mathcal{I}}\subseteq r^{\mathcal{I}}$ for every axiom
$p\sqsubseteq r$ in $\mathcal{T}$, $a^{\mathcal{I}}\in C^{\mathcal{I}}$ for
every assertion $a{:}C$ in $\mathcal{A}$, and
$(a^{\mathcal{I}},b^{\mathcal{I}})\in p^{\mathcal{I}}$ for every assertion
$(a,b){:}p$ in $\mathcal{A}$. Given two knowledge bases $\mathcal{K}_{1}$ and
$\mathcal{K}_{2}$, $\mathcal{K}_{1}$ _entails_ $\mathcal{K}_{2}$, denoted
$\mathcal{K}_{1}\models\mathcal{K}_{2}$, if and only if every model
$\mathcal{I}$ of $\mathcal{K}_{1}$ is also a model of $\mathcal{K}_{2}$.

###  2.2. Simple RDF Graphs

According to the RDF specification (Cyganiak et al., 2014), an RDF graph is a
finite set of triples whose elements belong to three pairwise disjoint sets:
IRIs, blank nodes, and literals. For convenience, we assume the fragment of
RDF graphs, called _Simple RDF graphs_ , that only considers triples whose
elements are IRIs. Furthermore, we assume that IRIs are partitioned in the
four sets $\mathbf{C}$, $\mathbf{I}$, $\mathbf{R}$, and
$\\{\text{rdf:type}\\}$, and that an RDF triple has either the form $(a,p,b)$
or $(a,\text{rdf:type},A)$ where $a,b\in\mathbf{I}$, $A\in\mathbf{C}$, and
$p\in\mathbf{R}$. We interpret each triple $(a,p,b)$ as an assertion
$(a,b){:}p$, and each triple $(a,\text{rdf:type},A)$ as an assertion $a{:}A$.
With these assumptions we define Simple RDF graphs, and introduce running
examples in Figure 1.

###### Definition 0 (Simple RDF Graph Syntax).

A _Simple RDF graph_ (or just _graph_) is an $\mathcal{ALCHOI}$ ABox $G$ where
the concept description of each concept assertion in $G$ is a concept name
$A\in\mathbf{C}$.

Bogaerts et al. (2022) highlight that RDF graphs have two different semantics,
depending on the inference task we want to perform: If the task is _deduction_
, the semantics of a graph is given by an ABox, and following the no-unique-
name, no-domain-closure and open-world assumptions. If the task is
_validation_ , the semantics is given by a model. Instead of relying on a
model-theoretic semantics for validation, our approach benefits from a proof-
theoretic semantics. As Reiter (1982) suggests, the model-theoretic semantics
of databases can be defined in proof theoretic terms: A database can be seen
as a set of formulas instead of a model, where queries are formulae to be
proven, and satisfaction of constraints is defined in terms of consistency. We
can therefore extend the deduction semantics of Simple RDF graphs with axioms
that encode these assumptions, which are based on the proof-theoretic
semantics for relational databases by Reiter (1982).

Proposition 5 below implies the equivalence of the Bogaerts et al. (2022)
model-theoretic SHACL semantics (Definition 3) and our proof theoretic SHACL
semantics (Definition 4).

###### Definition 0 (Graph Interpretation (Bogaerts et al., 2022)).

The _canonical interpretation_ of a Simple RDF graph $G$ is the interpretation
$\mathcal{I}_{G}$ such that $\Delta^{\mathcal{I}_{G}}=\mathbf{I}$; for each
$a\in\mathbf{I}$, $a^{\mathcal{I}_{G}}=a$; for every concept name
$A\in\mathbf{C}$, $A^{\mathcal{I}_{G}}=\\{a\mid a{:}A\in G\\}$; and for every
role name $r\in\mathbf{R}$, $r^{\mathcal{I}_{G}}=\\{(a,b)\mid(a,b){:}r\in
G\\}$. A graph $G$ is _model-valid_ according to a set $\Sigma$ of
$\mathcal{ALCHOI}$ axioms if and only if $\mathcal{I}_{G}$ is a model of
$\Sigma$.

###### Definition 0 (Simple RDF Graph Validation Semantics).

The axioms of a Simple RDF graph $G$, denoted $\mathcal{T}_{G}$, are the TBox
consisting of the following $\mathcal{ALCHOI}$ axioms:

  1. (1)

_Domain Closure Assumption (DCA)_ :
$\top\equiv\bigsqcup_{a\in\mathbf{I}}\\{a\\}$.

  2. (2)

_Unique Name Assumption (UNA)_ : $\\{a\\}\sqcap\\{b\\}\equiv\bot$, for each
pair of distinct individual names $a,b\in\mathbf{I}$.

  3. (3)

_Closed-World Assumption (CWA)_ :

     * •

$A\equiv\bigsqcup_{a{:}A\in G}\\{a\\}$, for each concept name
$A\in\mathbf{C}$,

     * •

$\exists p.\\{a\\}\equiv\bigsqcup_{(b,a){:}p\in G}\\{b\\}$, and

     * •

$\exists p^{-}.\\{a\\}\equiv\bigsqcup_{(a,b){:}p\in G}\\{b\\}$, for each role
name $p\in\mathbf{R}$ and each individual name $a\in\mathbf{I}$.

$(\mathcal{T}_{G},G)$ is the _validation knowledge base_ of $G$. A graph $G$
is _proof-valid_ according to a set $\Sigma$ of $\mathcal{ALCHOI}$ axioms if
and only if $\Sigma$ is consistent with the validation knowledge base of $G$
(i.e., the knowledge base $(\mathcal{T}_{G}\cup\Sigma,G)$ admits a model).

######  Proposition 0.

For a graph $G$ and set of $\mathcal{ALCHOI}$ axioms $\Sigma$, the following
statements are equivalent: (i) $G$ is model-valid according to $\Sigma$, (ii)
$G$ is proof-valid according to $\Sigma$, and (iii) $G$ is proof-valid
according to $\\{\varphi\\}$ for every $\varphi\in\Sigma$.

$a$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$$b$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$
(a) $G_{1}$

$a$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$$b$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$$e$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$
(b) $G_{2}$

Figure 1. Two example graphs, where we visualize rdf:type edges as floating
labels next to nodes (e.g.,
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}\,\,a$
for
$a{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$).

###  2.3. Simple SHACL Shapes

Following the idea that a SHACL schema is a description logic TBox (Bogaerts
et al., 2022), a SHACL shape is an axiom of the form $\psi\sqsubseteq\phi$
where $\psi$ and $\phi$ are concept descriptions, called the _target query_
and the _shape constraint_ , respectively. We restrict $\mathcal{ALCHOI}$
axioms to an essential subset for the sake of simplification, as defined
below. We lift this restriction in the extended version.

###### Definition 0 (Simple SHACL Syntax).

A _Simple SHACL shape_ (or just a _shape_) is an $\mathcal{ALCHOI}$ axiom
$\psi\sqsubseteq\phi$ such that the concept expressions $\psi$ and $\phi$ are
defined by:

$\displaystyle\psi\Coloneqq A\mid\exists\rho.\top\qquad\qquad\phi\Coloneqq
A\mid\exists\rho.A\mid\forall\rho.A$

A _Simple SHACL schema_ $\mathcal{S}$ is an $\mathcal{ALCHOI}$ TBox that
consists of a finite set of Simple SHACL shapes.

Given that shapes are defined in terms of $\mathcal{ALCHOI}$ axioms, their
semantics is defined in terms of the semantics of $\mathcal{ALCHOI}$ axioms
over the validation knowledge base of a graph.

###### Definition 0 (Simple SHACL Semantics).

A graph $G$ is _valid_ for a set $S$ of Simple SHACL shapes, denoted
$\operatorname{valid}(G,S)$, if and only if $G$ is proof-valid according to
$S$.

###### Example 0.

Consider the set of shapes $S_{1}=\\{s_{1},s_{2},s_{3}\\}$ where
$s_{1}={\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$,
$s_{2}=\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}.\top\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$
and
$s_{3}={\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$.
Shape
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$,
for example, targets all individuals that are instances of
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$,
and requires that there exists at least one edge
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$
to a
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$.
Both graphs in Figure 1 are _valid_ with respect to $S_{1}$.

###  2.4. Simple Conjunctive CONSTRUCT Queries

This section defines the SPARQL fragment we consider, called _Simple
Conjunctive CONSTRUCT Queries_ (SCCQ, or just _queries_). This fragment
follows the semantics proposed by Kostylev et al. (Kostylev et al., 2015) and
is restricted to basic graph patterns generated by adding variables for
individual names on Simple RDF graphs.

###### Definition 0 (SCCQ Syntax).

An _atomic pattern_ $t$ is defined by the following grammar:

$t\Coloneqq a{:}A\mid
x{:}A\mid(a,b){:}p\mid(x,a){:}p\mid(a,x){:}p\mid(x,y){:}p$

where $A$ stands for concept names, $a$ and $b$ for individual names, $p$ for
role names, and $x$ and $y$ for variables. A finite set of atomic patterns is
a _simple graph pattern_. Given a simple graph pattern $P$, we write
$\operatorname{var}(P)$ and $\operatorname{ind}(P)$ to denote the respective
sets of variables and individual names occurring in pattern $P$. Given two
simple graph patterns $P$ and $H$, where
$\operatorname{var}(H)\subseteq\operatorname{var}(P)$, the expression
$H\leftarrow P$ is a SCCQ, where $H$ and $P$ are called the _template_ and the
_pattern_ of the query, respectively.

A _valuation_ of a simple graph pattern $P$ is a function
$\mu:\mathbf{V}\cup\mathbf{I}\to\mathbf{I}$ such that $\mu(a)=a$ for every
$a\in\mathbf{I}$. In a slight abuse of notation, given two elements
$u,v\in\mathbf{V}\cup\mathbf{I}$ and a simple graph pattern $P$, we write
$\mu(u{:}A)=\mu(u){:}A$, $\mu((u,v){:}p)=(\mu(u),\mu(v)){:}p$, and
$\mu(P)=\\{\mu(t)\mid t\in P\\}$. Intuitively, a valuation substitutes
variables in a pattern by individual names. The semantics of SCCQ is defined
below.

###### Definition 0 (SCCQ Semantics).

The result of evaluating a SCCQ $H\leftarrow P$ over a Simple RDF graph $G$ is
the Simple RDF graph, denoted $\llbracket H\leftarrow P\rrbracket_{G}$,
defined as follows:

$\llbracket H\leftarrow P\rrbracket_{G}=\bigcup_{\mu(P)\subseteq G}\mu(H).$

Intuitively, the pattern $P$ retrieves valuations $\mu$ such that $\mu(P)$ is
a subgraph of $G$, which are used to generate the output graph by replacing
variables in the template.

###### Example 0.

Let $q_{1}=H\leftarrow P=$

$\\{\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},\textit{z}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},(\textit{y},\textit{z}){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}\\}\leftarrow\\{(\textit{w},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},(\textit{x},\textit{z}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{z}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$

For evaluation over the first example graph, $\llbracket
q_{1}\rrbracket_{G_{1}}$, we need to find valuations $\mu$ where
$\mu(P)\subseteq G_{1}$. This holds for $\mu$ where $\mu(\textit{w})=a$,
$\mu(\textit{x})=a$, $\mu(\textit{y})=b$, and $\mu(\textit{z})=b$. Hence, the
result is the graph $\llbracket H\leftarrow
P\rrbracket_{G_{1}}=\mu(H)=\\{b{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},b{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},(b,b){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}\\}$.
Similarly, evaluation $\llbracket
q_{1}\rrbracket_{G_{2}}=\\{b{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},b{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},e{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},(b,b){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p},(b,e){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}\\}$.

##  3\. Formal Problem Statement

We aim to construct shapes characterizing the possible result graphs of a
query where the input is constrained by shapes as well.

###### Definition 0 (Input and Output Graph).

A graph $G_{\mathrm{in}}$ is an _input graph_ with respect to a finite set of
shapes $\mathcal{S}_{\mathrm{in}}$ if
$\operatorname{valid}(G_{\mathrm{in}},\mathcal{S}_{\mathrm{in}})$. A graph
$G_{\mathrm{out}}$ is an _output graph_ for a query $q$ and a finite set of
shapes $\mathcal{S}_{\mathrm{in}}$ if there exists an input graph
$G_{\mathrm{in}}$ such that $G_{\mathrm{out}}=\llbracket
q\rrbracket_{G_{\mathrm{in}}}$.

###### Definition 0 (Vocabulary).

A _vocabulary_ is the set of concept and role names that occur in a concept
description $C$, shape $s$, graph $G$, or template of a query $q$, denoted
$\operatorname{voc}(C)$, $\operatorname{voc}(s)$, $\operatorname{voc}(G)$, or
$\operatorname{voc}(q)$, respectively.

###### Definition 0 (Relevancy).

Shape $s=\psi\sqsubseteq\phi$ is _relevant_ for query $q$ if there exists a
graph $G_{+}$ with $\operatorname{voc}(G_{+})\subseteq\operatorname{voc}(q)$
such that $\operatorname{valid}(G_{+},\\{s\\})$ and
$(\mathcal{T}_{G_{+}},G_{+})\not\models\psi\sqsubseteq\bot$, and a graph
$G_{-}$ with $\operatorname{voc}(G_{-})\subseteq\operatorname{voc}(q)$ such
that not $\operatorname{valid}(G_{-},\\{s\\})$.

Problem OutputShapes formalizes the set of shapes that best characterize the
possible output graphs of a SCCQ. The first restriction on the solution
ensures only relevant shapes are in the output, i.e., shapes that validate
some graphs in the vocabulary $\operatorname{voc}(q)$, but not all of them
(Definition 3). This excludes, for example, shapes with targets outside the
vocabulary (which are thereby vacuously satisfied), or shapes with constraints
requiring concept or role names outside the vocabulary, which can never be
satisfied. The second restriction states that $\mathcal{S}_{\text{out-opt}}$
defines an upper bound for the set of output graphs, while the third requires
this upper bound to be minimal. Later in this paper, we will present a sound,
but not complete, algorithm for solving this problem, i.e., an algorithm that
satisfies the first two, but not the last condition.

Problem OutputShapes $:$
$(\mathcal{S}_{\mathrm{in}},q)\mapsto\mathcal{S}_{\text{out-opt}}$

0: A finite set of shapes $\mathcal{S}_{\mathrm{in}}$ and a SCCQ $q$.

0: A set of shapes $\mathcal{S}_{\text{out-opt}}$ such that:1. every
$s\in\mathcal{S}_{\text{out-opt}}$ is relevant for $q$,2. for every $G$ with
$\operatorname{valid}(G,\mathcal{S}_{\mathrm{in}})$ and
$G_{\mathrm{out}}=\llbracket q\rrbracket_{G}$,
$\operatorname{valid}(G_{\mathrm{out}},\mathcal{S}_{\text{out-opt}})$,3. the
set of graphs $G$ such that $\operatorname{valid}(G,\mathcal{S}_{\text{out-
opt}})$ is minimal.

###### Example 0.

Consider $q_{1}$ (Example 11) and $S_{1}$ (Example 8). The shapes
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\in
S_{1\textrm{-out}}$ constrain the results of evaluating $q_{1}$ on _any_ graph
that is valid with respect to $S_{1}$, e.g., the example graphs in Figure 1.
Shape
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\in
S_{1\textrm{-out}}$ follows directly from the query template, whereas shape
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}$
is only contained in $S_{1\textrm{-out}}$ because
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$
holds on all input graphs and we can thus infer that all bindings for y are
also bindings for z.

Simple SHACL shapes are not sufficiently expressive to rule out _all_
impossible output graphs of a query. For example, we know for $q_{1}$ and
$S_{1}$ that each instance of
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}$
has a
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}$
edge to itself. Simple SHACL shapes cannot express reflexivity, so graphs
without reflexive
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}$
cannot be ruled out.

##  4\. Computing Candidate OutputShapes

We break down Problem OutputShapes into two subproblems: The generation of a
finite set of candidate shapes $\mathcal{S}_{\text{can}}$ – a superset of the
solution – and the filtering of this set (Problem IsOutputShape).

Problem 2 IsOutputShape $:$
$(\mathcal{S}_{\mathrm{in}},q,s)\mapsto\\{\textsc{yes},\textsc{na}\\}$

0: A finite set of shapes $\mathcal{S}_{\mathrm{in}}$, a SCCQ $q=H\leftarrow
P$, and a shape $s$ that is relevant for this query $q$.

0: Does $\operatorname{valid}(\llbracket
q\rrbracket_{G_{\mathrm{in}}},\\{s\\})$ hold for every graph $G_{\mathrm{in}}$
where $\operatorname{valid}(G_{\mathrm{in}},\mathcal{S}_{\mathrm{in}})$?

Algorithm 1 outlines this approach, by referring to Problem IsOutputShape. In
Section 6, we will define a sound, but not complete, algorithm solving this
problem (Algorithm 2). Thus, Algorithm 1 is a sound approximation of problem
OutputShapes satisfying its first two, but not the third condition
(minimality). In the following we use $\mathcal{S}_{\text{out}}$ to refer to
such an approximation of $\mathcal{S}_{\text{out-opt}}$.

Algorithm 1 OutputShapes $:$
$(\mathcal{S}_{\mathrm{in}},q)\mapsto\mathcal{S}_{\text{out}}$

0: A finite set of shapes $\mathcal{S}_{\mathrm{in}}$ and a SCCQ $q$.

0: The set of output shapes $\mathcal{S}_{\text{out}}$.

1: $\mathcal{S}_{\text{out}}\leftarrow\emptyset$,
$\mathcal{S}_{\text{can}}\leftarrow$ the finite set of shapes over
$\operatorname{voc}(q)$

2: for all $s\in\mathcal{S}_{\text{can}}$ do

3: if $\textsc{IsOutputShape}(\mathcal{S}_{\mathrm{in}},q,s)=\textsc{YES}$
then

4: $\mathcal{S}_{\text{out}}\leftarrow\mathcal{S}_{\text{out}}\;\cup\\{s\\}$

5: return $\mathcal{S}_{\text{out}}$

In order to obtain a finite set of candidates $\mathcal{S}_{\text{can}}$,
Proposition 1 allows us to discard shapes that do not describe output graphs
and limit thus the search space of Algorithm 1 to the shapes that are built
from the vocabulary of the query.

######  Proposition 0.

If a shape $s=\psi\sqsubseteq\phi$ is relevant for a SCCQ $q$, then $s$
satisfies one of the following two conditions: (i)
$\operatorname{voc}(s)\subseteq\operatorname{voc}(q)$, or (ii)
$\operatorname{voc}(\psi)\subseteq\operatorname{voc}(q)$ and $\phi$ is either
$\forall p.A$ or $\forall p^{-}.A$ where $p\in\operatorname{voc}(q)$ and
$A\notin\operatorname{voc}(q)$.

In order to cover all relevant shapes that satisfy condition (i), we can
include the finite combinations of elements in the vocabulary of the query.
Condition (ii) requires special care: Each role name
$p\in\operatorname{voc}(q)$ defines a family of shapes of the form
$\psi\sqsubseteq\forall p.A$ or $\psi\sqsubseteq\forall p^{-}.A$, where
$A\notin\operatorname{voc}(q)$. To explore this family, it suffices to
consider a representative by including in the set of candidate shape
constraints for each role name $p\in\operatorname{voc}(q)$ the two concept
descriptions $\forall p.A$ and $\forall p^{-}.A$, such that
$A\not\in\operatorname{voc}(q)$.

The search space is therefore bounded by the vocabulary of the query, which is
relatively small. In the extended version we show that there are
$(n+2m)(n+4nm+2m)-n$ candidate shapes if $\operatorname{voc}(q)$ contains $n$
concept names and $m$ role names.

##  5\. Axiomatizations Over Executions

A query $q=H\leftarrow P$ works on any input graph $G_{\mathrm{in}}$ defined
by $\mathcal{S}_{\mathrm{in}}$ (Definition 1) and returns a result graph
$G_{\mathrm{out}}$ in two steps: By matching $P$ with $G_{\mathrm{in}}$,
determining valuations $\mu$ where $\mu(P)\subseteq G_{\mathrm{in}}$, and then
by replacing variables in $H$ with these valuations producing
$G_{\mathrm{out}}$. As a result, multiple occurrences of the same concept
names do not have the same extensions: As an example, consider the query
$\\{\textit{x}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{A}},\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{A}},\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{E}}\\}\leftarrow\\{\textit{x}{:}{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{A}},\textit{x}{:}{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{B}},\textit{y}{:}{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{E}}\\}$
and the input shape
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$,
where we mark different occurrences of the same names with zero, one, or two
dots. The extension of
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{A}}$
includes only individuals matched by the query pattern, which requires
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{B}}$
as well. Thus,
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{A}}$
may be subsumed by and may be unequal to
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$.
Similarly,
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{A}}$
now also includes all bindings of variable y, unlike
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$
or
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{A}}$.

We now want to axiomatize how all possible $G_{\mathrm{in}}$ are connected
with their corresponding $G_{\mathrm{out}}$. Virtually putting these
axiomatizations together creates an _extended graph_ that holds axioms from
these two steps allowing us to prove statements about $G_{\mathrm{out}}$. We
distinguish inputs and step outcomes by a syntactic trick that rewrites input
symbols $A,p$ into _fresh_ symbols $\dot{A},\dot{p}$ after the first step, and
into $\ddot{A},\ddot{p}$ after the second step. We also write, e.g.,
$\dot{G}$, meaning substitution of all symbols $A,p$ in graph $G$ with
$\dot{A},\dot{p}$.

These rewritten symbols allow us to encode assertions that are valid for only
specific states of query execution. Variable bindings, on the other hand, hold
throughout: We codify a variable binding $\mu(x)=a$ as a concept assertion
$a{:}V_{x}$, where $V_{x}$ is a fresh concept name. Note, that we assume that
all concept names and role names with dots, as well as concept names for
variable concepts, exist as fresh names in $\mathbf{C}$ and $\mathbf{R}$.
Example 2 illustrates the construction of such an extended graph, which is
defined in Definition 1.

###### Definition 0 (Extended Graph).

Given an input graph $G_{\mathrm{in}}$ and a query $H\leftarrow P$, the
following graphs are defined with correspondences to the query execution
steps:

  1. (1)

The _intermediate graph_ $G_{\mathrm{med}}\coloneqq\bigcup_{\mu(P)\subseteq
G_{\mathrm{in}}}\mu(P)$.

  2. (2)

The _variable concept graph_ $G_{\mathbf{V}}$ containing an assertion
$a{:}V_{x}$ if and only if there exists a valuation $\mu$ such that
$\mu(P)\subseteq G_{\mathrm{in}}$ and $\mu(x)=a$.

  3. (3)

The _output graph_ $G_{\mathrm{out}}\coloneqq\llbracket
q\rrbracket_{G_{\mathrm{in}}}$.

  4. (4)

The _extended graph_ $G_{\mathrm{ext}}\coloneqq
G_{\mathrm{in}}\cup\dot{G}_{\mathrm{med}}\cup
G_{\mathbf{V}}\cup\ddot{G}_{\mathrm{out}}$.

###### Example 0.

Consider $q_{1}$ (Example 11), $S_{1}$ (Example 8), and the graph $G_{1}$
(Figure 1) as one possible input graph for $q_{1}$. The respective extended
graph and its components are given in Figure 2. Note, that these graphs
satisfy different axioms (in different namespaces), e.g.,
$\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}^{-}.\top\sqsubseteq{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{E}}$
is valid in $\dot{G}_{\mathrm{med}}$ but
$\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}^{-}.\top\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$
is not valid in $G_{\mathrm{in}}$. A range of axioms are valid for
$G_{\mathrm{ext}}$, such as
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{E}}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$
or
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\sqsubseteq{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}$.
Indeed, these axioms are valid on _every_ extended graph of $q_{1}$, as long
as $\operatorname{valid}(G_{\mathrm{in}},S_{1})$, e.g.,
$G_{\mathrm{in}}=G_{1}$ or $G_{\mathrm{in}}=G_{2}$ (Figure 1).

$a$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A},{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}},{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}$$b$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{B}},{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{B}},{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}},$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E},{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{E}},{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{E}},{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p}}$

$a$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$$b$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$
(a) $G_{\mathrm{in}}$

$a$$b$${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{B}},{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{E}}$${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}$$p,r$
(b) $\dot{G}_{\mathrm{med}}$

$a$${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}},{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}$$b$${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}},{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}$
(c) $G_{\mathbf{V}}$

$b$${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{B}},{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{E}}$${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p}}$
(d) $\ddot{G}_{\mathrm{out}}$

Figure 2. On the left the graph $G_{\mathrm{ext}}$ as the union of
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}G_{\mathrm{in}}}$
(2(a)),
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{G}_{\mathrm{med}}}$
(2(b)),
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}G_{\mathbf{V}}}$
(2(c)), and
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{G}_{\mathrm{out}}}$
(2(d)).

Assertions added per step are sound, but not sufficient to fully characterize
what happens at each query execution step. Therefore, axioms we can find to
characterize the relationships between $G_{\mathrm{in}}$ and
$G_{\mathrm{out}}$ will be sound but incomplete. In the following sections, we
will introduce additional axioms per step to extend possible inferences and
thus determine a tighter description by output shapes.

Proposition 3 shows that axioms valid on any of the graphs $G_{\mathrm{in}}$,
$G_{\mathrm{med}}$, $G_{\mathbf{V}}$ and $G_{\mathrm{out}}$ are valid on the
extended graph when applying syntactic rewriting, and vice versa.

######  Proposition 0.

Given a graph $G_{\mathrm{in}}$ and a query $q$, let the graphs
$G_{\mathrm{med}}$, $G_{\mathrm{out}}$, and $G_{\mathrm{ext}}$ be defined
according to Definition 1. For every axiom $\varphi$ that does not include
names with dots (e.g., $\dot{A}$, $\ddot{A}$, $\dot{p}$, $\ddot{p}$), the
following equivalences hold:

  1. (1)

$\operatorname{valid}(G_{\mathrm{in}},\\{\varphi\\})$ if and only if
$\operatorname{valid}(G_{\mathrm{ext}},\\{\varphi\\})$.

  2. (2)

$\operatorname{valid}(G_{\mathrm{med}},\\{\varphi\\})$ if and only if
$\operatorname{valid}(G_{\mathrm{ext}},\\{\dot{\varphi}\\})$.

  3. (3)

$\operatorname{valid}(G_{\mathrm{out}},\\{\varphi\\})$ if and only if
$\operatorname{valid}(G_{\mathrm{ext}},\\{\ddot{\varphi}\\})$.

##  6\. Checking Whether IsOutputShape

Algorithm 2 (IsOutputShape) checks for a given shape $s$ if the rewritten
shape $\ddot{s}$ is entailed by a set of axioms $\Sigma$ valid for every
extended graph $G_{\mathrm{ext}}$ and derived from $q$ and
$\mathcal{S}_{\mathrm{in}}$ (YES). If this entailment can not be proven, the
algorithm returns no answer (NA). In the remainder of this section, we
construct $\Sigma$: We start by inferring the assumptions of the validation
knowledge base of $G_{\mathrm{ext}}$ based on the atoms of the input query
($\Sigma_{\mathrm{vkb}}$). Next, we identify subsumptions between query
variables in different components of the input query by establishing a mapping
between them ($\Sigma_{\mathrm{map}}$). Finally, we include subsumptions
between role names by considering the query variables constraining them
($\Sigma_{\mathrm{prop}}$). In the extended version we prove that Problem
IsOutputShape is NP-hard.

Corollary 1 establishes the formal foundation for IsOutputShape based on
Proposition 3.

######  Corollary 0.

Let $q$ be a SCCQ, $\Sigma$ a set of $\mathcal{ALCHOI}$ axioms such that
$\operatorname{valid}(G_{\mathrm{ext}},\Sigma)$ for every extended graph
$G_{\mathrm{ext}}$ of $q$, and $s$ a shape including no names with dots. If
$\Sigma\models\ddot{s}$, then $\operatorname{valid}(G_{\mathrm{out}},\\{s\\})$
for every output graph $G_{\mathrm{out}}$ of $q$ .

Algorithm 2 IsOutputShape $:$
$(\mathcal{S}_{\mathrm{in}},q,s)\mapsto\\{\textsc{yes},\textsc{na}\\}$

0: A finite set of shapes $\mathcal{S}_{\mathrm{in}}$, a SCCQ $q=H\leftarrow
P$, and a shape $s$ that is relevant for this query $q$.

0: Does $\operatorname{valid}(\llbracket
q\rrbracket_{G_{\mathrm{in}}},\\{s\\})$ hold for every graph $G_{\mathrm{in}}$
where $\operatorname{valid}(G_{\mathrm{in}},\mathcal{S}_{\mathrm{in}})$?

1: $\Sigma_{\mathrm{in}}\leftarrow\mathcal{S}_{\mathrm{in}}$

2:
$\Sigma_{\mathrm{vkb}}\leftarrow\operatorname{UNA}(q)\cup\operatorname{CWA}(q)$_(
Section 6.1)_ .

3:
$\Sigma_{\mathrm{map}}\leftarrow\operatorname{MA}_{\mathcal{S}_{\mathrm{in}}}(P)$_(
Section 6.2 and 6.3)_ .

4: $\Sigma_{\mathrm{prop}}\leftarrow\operatorname{RS}(q)$_( Section 6.4)_ .

5:
$\Sigma\leftarrow\Sigma_{\mathrm{in}}\cup\Sigma_{\mathrm{vkb}}\cup\Sigma_{\mathrm{map}}\cup\Sigma_{\mathrm{prop}}$

6: return if $\Sigma\models\ddot{s}$ then yes else na

###  6.1. Axiomatizations from the Validation KB

We first utilize the assumptions of the validation knowledge base (see
Definition 4) to infer axioms from a query $q$ that are valid on _any_
extended graph of $q$. Since we do not know all individual names in the
extended graphs, we limit the UNA-encoding to individual names that appear in
the query (Definition 2), which are in any non-empty extended graph per
definition (see Definition 1).

###### Definition 0 (UNA-encoding).

The _UNA-encoding_ of a query $q$, denoted $\operatorname{UNA}(q)$, is the set
of $\mathcal{ALCHOI}$ axioms of the form $\\{a\\}\sqcap\\{b\\}\equiv\bot$ for
every pair of distinct individual names $a,b$ in $q$.

######  Proposition 0.

For every extended graph $G_{\mathrm{ext}}$ of a SCCQ $q$, it holds that
$\operatorname{valid}(G_{\mathrm{ext}},\operatorname{UNA}(q))$.

We do not infer any axioms based on the DCA because a SCCQ does not determine
the set of individual names $\mathbf{I}$. Concerning the CWA, a query imposes
restrictions on concept names that appear in the query pattern (e.g.,
$\dot{A}$), the query template (e.g., $\ddot{A}$), variables (e.g. $V_{x}$),
and individual names (e.g., $\\{a\\}$). All other concept names are irrelevant
(see Proposition 1).

We define the following utility concepts $\operatorname{C}_{u}$ (Definition 4)
for referring to the nominal concept _or_ variable concept for an individual
name _or_ variable $u$, and $\operatorname{vcg}(q)$, referring to the variable
connectivity graph of a query $q$.

###### Definition 0.

For each individual name or variable $u$, $\operatorname{C}_{u}$ is $\\{a\\}$
if $u$ is an individual name $a$, or $\operatorname{C}_{u}$ is $V_{x}$ if $u$
is a variable $x$.

###### Definition 0 (Variable Connectivity Graph).

The _variable connectivity graph_ of query pattern $P$, denoted
$\operatorname{vcg}(P)$, is the graph whose nodes are the atoms in $P$, and
which has an undirected edge $\\{t_{1},t_{2}\\}$ if and only if atoms $t_{1}$
and $t_{2}$ share a variable.

A SCCQ imposes restrictions on concept names in extended graphs, by definition
of $G_{\mathrm{med}}$, $G_{\mathrm{out}}$, and $G_{\mathbf{V}}$. For example,
each atom $x{:}A\in P$ implies $V_{x}\sqsubseteq\dot{A}$, since concept
$V_{x}$ is defined from all individual names referred to by $x$, which
according to the evaluation semantics of SCCQ result from filtering $A$. More
generally, all atoms $x{:}A$ and $(x,y){:}p$ in $P$ (Example 2) restrict the
instances of variable concept $V_{x}$. These observations can be combined over
all atoms in a query, leading to Definition 6.

###### Definition 0 (CWA-encoding).

The _CWA-encoding_ for a SCCQ $q=(H\leftarrow P)$, denoted
$\operatorname{CWA}(q)$, is the minimal set of $\mathcal{ALCHOI}$ axioms
including:

1\. For each concept name $A$ in $P$, $\dot{A}\equiv
A\sqcap\bigsqcup_{u{:}A\in P}\operatorname{C}_{u}$.

2\. For each concept name $A$ in $H$, $\ddot{A}\equiv\bigsqcup_{u{:}A\in
H}\operatorname{C}_{u}$.

3\. For each variable $x$ in $\operatorname{var}(q)$ the axiom

$\displaystyle V_{x}\sqsubseteq\textstyle$ $\displaystyle{\bigsqcap_{x{:}A\in
P}}A\sqcap{\bigsqcap_{(x,u){:}p\in P}}\exists
p.\operatorname{C}_{u}\sqcap{\bigsqcap_{(u,x){:}p\in P}}\exists
p^{-}.\operatorname{C}_{u},$

and if $\operatorname{vcg}(P)$ is acyclic w.r.t $x$, then also the axiom

$\displaystyle V_{x}\sqsupseteq\textstyle$ $\displaystyle{\bigsqcap_{x{:}A\in
P}}A\sqcap{\bigsqcap_{(x,u){:}p\in P}}\exists
p.\operatorname{C}_{u}\sqcap{\bigsqcap_{(u,x){:}p\in P}}\exists
p^{-}.\operatorname{C}_{u}.$

4\. For each role name $p$ in pattern $P$ the axioms

$\displaystyle\exists\dot{p}.\operatorname{C}_{v}$
$\displaystyle\equiv\textstyle\bigsqcup_{(u,v){:}p\in P}\operatorname{C}_{u},$
$\displaystyle\exists\dot{p}.\top$
$\displaystyle\equiv{\bigsqcup_{(u,v){:}p\in
P}}\operatorname{C}_{u}\sqcap\exists\dot{p}.\operatorname{C}_{v},$
$\displaystyle\exists\dot{p}^{-}.\operatorname{C}_{u}$
$\displaystyle\equiv\textstyle\bigsqcup_{(u,v){:}p\in P}\operatorname{C}_{v},$
$\displaystyle\exists\dot{p}^{-}.\top$
$\displaystyle\equiv{\bigsqcup_{(u,v){:}p\in
P}}\operatorname{C}_{v}\sqcap\exists\dot{p}^{-}.\operatorname{C}_{u}.$

5\. For each role name $p$ in template $H$ the axioms

$\displaystyle\exists\ddot{p}.\operatorname{C}_{v}$
$\displaystyle\equiv\textstyle\bigsqcup_{(u,v){:}p\in H}\operatorname{C}_{u},$
$\displaystyle\exists\ddot{p}.\top$
$\displaystyle\equiv{\bigsqcup_{(u,v){:}p\in
H}}\operatorname{C}_{u}\sqcap\exists\ddot{p}.\operatorname{C}_{v},$
$\displaystyle\exists\ddot{p}^{-}.\operatorname{C}_{u}$
$\displaystyle\equiv\textstyle\bigsqcup_{(u,v){:}p\in H}\operatorname{C}_{v},$
$\displaystyle\exists\ddot{p}^{-}.\top$
$\displaystyle\equiv{\bigsqcup_{(u,v){:}p\in
P}}\operatorname{C}_{v}\sqcap\exists\ddot{p}^{-}.\operatorname{C}_{u}.$

Observe, that unlike in the definition for concepts $\dot{A}$ (Definition 6,
1.), the definition for concepts $\ddot{A}$ (Definition 6, 2.) does not
include $A$, since elements of $\dot{A}$ are the result of filtering $A$,
whereas $\ddot{A}$ is newly constructed for the query template $H$. We first
demonstrate the general meaning of these axioms in Example 7.

###### Example 0.

Consider again the query
$q_{1}=\\{\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},\textit{z}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},(\textit{y},\textit{z}){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}\\}\leftarrow\\{(\textit{w},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},(\textit{x},\textit{z}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{z}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$
(Example 11). Then, $\operatorname{CWA}(q_{1})$ consists of the following
axioms:

  1. (1)

$\\{{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{B}}\equiv{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\sqcap{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}},$
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{E}}\equiv{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\sqcap{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\\}$,
because, e.g., concept
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{B}}$
in the extended graph is defined by filtering
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$
with variable
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}$,
based on the query pattern
$\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$
in $q_{1}$.

  2. (2)

$\\{{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{B}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}},$
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{E}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\\}$,
because, e.g., concept
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{B}}$
in the extended graph is defined by
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}$,
since it only occurs in the single construct pattern
$\textit{z}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}$.
If there were multiple occurences, it would be defined by the union of all
variables, instead.

  3. (3)

$\\{{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}},$
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}},$
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}}\sqcap{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},$
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\sqcap{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$,
because variable concepts are defined by constraints to the variable in the
query pattern. For example,
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}$
is constrained by patterns
$(\textit{w},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$
and
$\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$
in $q_{1}$, and thus bound by
$\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}}\sqcap{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$.
This is a crucial step, since concept and role names in the extended graph are
defined in terms of these variable concepts. The inverse cases are included,
because $\operatorname{vcg}(P)$ is acyclic:
$\\{{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}}\sqsupseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}},$
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\sqsupseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}},$
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\sqsupseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}}\sqcap{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},$
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\sqsupseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\sqcap{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$
(cf. Example 8).

  4. (4)

$\\{\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}},$
$\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}},$
$\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}.\top\equiv({\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}}\sqcap\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}})\sqcup({\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\sqcap\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}})\\}$,
because, e.g., role name
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}$
in the extended graph is defined by the variables concepts that it occurs
with. Similarly, the following axioms for inverse role names are included:
$\\{\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p^{-}}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}},$
$\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p^{-}}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}},$
$\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p^{-}}}.\top\equiv({\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\sqcap\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p^{-}}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{w}})\sqcup({\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\sqcap\exists{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p^{-}}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}})\\}$.

  5. (5)

$\\{\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}},$
$\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p}}.\top\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\sqcap\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\\}$
and
$\\{\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p^{-}}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}},$
$\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p^{-}}}.\top\equiv{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}\sqcap\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p^{-}}}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\\}$,
with analogous reasoning as the previous case.

Note the additional condition in the second part of Definition 6 (3.) where we
require $\operatorname{vcg}(q)$ to be acyclic. In the following example
(Example 8), we will motivate why this condition is required and then define
Lemma 9 with respect to this case.

###### Example 0.

Consider the pattern
$P=\\{(x,y){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r},(y,z){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r},(x,z){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}\\}$
of a query $q=H\leftarrow P$, and the graph $G$ in Figure 3.

$a_{1}$$a_{2}$$a_{3}$$a_{4}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}$
Figure 3. Input graph $G$ for Example 8.

Note, that $\operatorname{vcg}(P)$ is cyclic, since
$((x,y){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r},(y,z){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r})$,
$((y,z){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r},(x,z){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p})$
as well as
$((x,z){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},(x,y){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r})$
each share variables.

Evaluating $q$ on $G$ results in mappings $\mu_{1}=\\{x\mapsto a_{1},y\mapsto
a_{2},z\mapsto a_{3}\\}$ and $\mu_{2}=\\{x\mapsto a_{3},y\mapsto
a_{2},z\mapsto a_{1}\\}$. Thus, the variable concepts are defined as
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}=\\{a_{1},a_{3}\\}$,
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}=\\{a_{2}\\}$
and
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}=\\{a_{3},a_{1}\\}$.
Note, that $y\mapsto a_{4}$ is not in any result mapping for query $q$ on
graph $G$ (and
$a_{4}\not\in{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}$).
However,
$\\{a_{4}\\}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}^{-}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\sqcap\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}$.
Therefore,
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\not\sqsupseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}^{-}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{x}}\sqcap\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}r}.{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}$,
so we can not include this axiom.

Intuitively, an acyclic graph $\operatorname{vcg}(P)$ allows for separating
the pattern $P$ (given, as an example, variable $x$ and concept name $A$) into
patterns $P_{l}$, $\\{x:A\\}$, and $P_{r}$, where $P_{l}$ shares at most
variable $x$ with $P_{r}$. In these cases, the implicit dependencies between
bindings for variables that cause issues as demonstrated for $x$ and $z$ in
Example 8 do not occur.

######  Lemma 0.

Let $q=H\leftarrow P$ be a query such that $\operatorname{vcg}(P)$ is acyclic.
Let $G$ be a graph, and let $x$ be a variable corring in $P$. Then

$V_{x}\sqsupseteq\textstyle{\bigsqcap_{x{:}A\in
P}}A\sqcap{\bigsqcap_{(x,u){:}p\in P}}\exists
p.\operatorname{C}_{u}\sqcap{\bigsqcap_{(u,x){:}p\in P}}\exists
p^{-}.\operatorname{C}_{u}.$

Given Lemma 9, the following proposition holds.

######  Proposition 0.

For every extended graph $G_{\mathrm{ext}}$ of a SCCQ $q$, it holds that
$\operatorname{valid}(G_{\mathrm{ext}},\operatorname{CWA}(q))$, if either $q$
does not include any individual names, or the output graph is guaranteed to be
non-empty.

Note the additional condition in Proposition 10: If the output graph is empty
and the query includes individual names, then $G_{\mathrm{ext}}$ may not be
valid with respect to $\operatorname{CWA}(q)$, since the constructed axioms
may include individual names that are not guaranteed to exist. This could be
remedied by not allowing individual names in queries; however, since Simple
SHACL shapes do not allow individual names, these axioms do not impact
soundness of the method.

###  6.2. Axiomatizations for Query Subpatterns

We refer to a pattern $P^{\prime}\subseteq P$ as a _component_ of the pattern
$P$, if $\operatorname{vcg}(P^{\prime})$ (see also Definition 5) is a
connected subgraph of $\operatorname{vcg}(P)$ and there exists no
$P^{\prime\prime}$ such that $P^{\prime}\subset P^{\prime\prime}$ and
$\operatorname{vcg}(P^{\prime\prime})$ is a connected subgraph of
$\operatorname{vcg}(P)$.

###### Example 0.

Query $q_{1}$ (Example 11) has components
$\\{(\textit{w},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\\}$
and
$\\{(\textit{x},\textit{z}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{z}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$.
The CWA encoding (Example 7) does not entail
${\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{y}}\sqsubseteq{\color[rgb]{0.26171875,0.38671875,0.84765625}\definecolor[named]{pgfstrokecolor}{rgb}{0.26171875,0.38671875,0.84765625}V_{z}}$,
even though this axiom is both valid in all extended graphs, and required for
inferring, e.g., the result shape
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}$.

Example 11 shows that the $\operatorname{CWA}$ encoding alone is not
sufficient for inferring all subsumptions between variable concepts. If we
could find a homomorphism between two components of the query pattern, we
would know that the valuations of one component are a subset of the valuations
of the other component (modulo variable names), and thus infer subsumptions
between variable concepts.

###### Definition 0 (Component Map).

For components $P_{1}$ and $P_{2}$ of $P$, every function
$h:\operatorname{var}(P_{1})\to\mathbf{I}\cup\mathbf{V}$ such that
$h(P_{1})\subseteq P_{2}$ is called a _component map_ on $P$, where we write
$h(P_{1})$ to mean substitution of each variable $x$ in $P_{1}$ by $h(x)$.

###### Definition 0 (Component Map Axioms).

The set of axioms inferred from a component map $h$ on $P$, denoted
$\operatorname{MA}_{h}(P)$, contains axiom $\operatorname{C}_{h(x)}\sqsubseteq
V_{x}$ for every variable $x$ in the domain of $h$. The union of all sets
$\operatorname{MA}_{h}(P)$ of a graph pattern $P$ is called
$\operatorname{MA}(P)$.

###### Example 0.

Consider two components $P_{1}=\\{(x,y){:}p\\}$ and
$P_{2}=\\{(z,z){:}p,z{:}A\\}$. Then we can define the mapping $h(x)=z$ and
$h(y)=z$, such that $h(P_{1})\subseteq P_{2}$. Therefore, we can construct the
axioms $V_{z}\sqsubseteq V_{x}$ and $V_{z}\sqsubseteq V_{y}$ valid on
$G_{\mathrm{ext}}$.

######  Proposition 0.

For every extended graph $G_{\mathrm{ext}}$ of a SCCQ $q=H\leftarrow P$, it
holds that $\operatorname{valid}(G_{\mathrm{ext}},\operatorname{MA}(P))$.

###  6.3. Extending Query Patterns via Constraints

The basic mapping $\operatorname{MA}(P)$ is not sufficient for inferring
certain crucial variable concept subsumptions, as Example 16 shows.

###### Example 0.

Consider components
$P_{1}=\\{(\textit{x},\textit{z}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{z}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$
and
$P_{2}=\\{(\textit{w},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\\}$
of query $q_{1}$ (Example 11). Here, we can not find a mapping $h$ satisfying
Definition 12. However, we know based on $S_{1}$ that
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$
(Example 8). We can utilize this knowledge to extend component $P_{2}$, adding
the pattern
$\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}$
which does not alter the queries results. Now we can find the mapping
$h(\textit{x})=\textit{w},h(\textit{z})=\textit{y}$ such that
$h(P_{1})\subseteq P_{2}$.

Intuitively, by extending a component as illustrated in Example 16, we reveal
a subsumption relationship that was implicit in the input shapes. For the same
reason, the extended component is not more restrictive than the original one.
We now show how this approach can be generalized.

###### Definition 0 (Target Variables).

A variable $x$ is _target variable_ for a shape $\psi\sqsubseteq\phi$ in an
atomic pattern $t$ if and only if either

  1. (1)

$t=x{:}A$ and $\psi=A$,

  2. (2)

$t=(x,y){:}p$ and $\psi=\exists p.\top$, or

  3. (3)

$t=(y,x){:}p$ and $\psi=\exists p^{-}.\top$.

###### Definition 0 (Extension).

The _extension_ $\operatorname{Ext}(x,\phi)$ of a variable $x$ with respect to
a shape constraint $\phi$ and component $P_{i}$ is the set of atoms defined
below, where $x_{0}$ is a fresh variable.

$\displaystyle\operatorname{Ext}(x,A)$ $\displaystyle=\\{x{:}A\\},$
$\displaystyle\operatorname{Ext}(x,\exists p^{-}.A)$
$\displaystyle=\\{(x_{0},x){:}p,x_{0}{:}A\\},$
$\displaystyle\operatorname{Ext}(x,\forall p.A)$
$\displaystyle=\\{y{:}A\mid(x,y){:}p\in P_{i}\\},$
$\displaystyle\operatorname{Ext}(x,\exists p.A)$
$\displaystyle=\\{(x,x_{0}){:}p,x_{0}{:}A\\},\ \text{and}$
$\displaystyle\operatorname{Ext}(x,\forall p^{-}.A)$
$\displaystyle=\\{y{:}A\mid(y,x){:}p\in P_{i}\\}.$

Since new atoms are added to the pattern, they can be targets of input shapes,
too. The recursive extension is bound by the maximum degree and diameter of
the connectivity graph $\operatorname{vcg}(P)$ of the query pattern $P$
(Definition 5).

###### Definition 0 (Bound extension).

Let $P_{i}$ be a component of a query pattern $P$, $x$ be a variable in
$\operatorname{var}(P_{i})$, $\mathcal{S}_{\mathrm{in}}$ be a finite set of
shapes, and $P_{i}^{x}$ be a pattern that results from adding iteratively
atoms $\operatorname{Ext}(u,s)$ to $P_{i}$, where
$s\in\mathcal{S}_{\mathrm{in}}$, $u$ is a target variable for $s$, and either
$u=x$ or $u\notin\operatorname{var}(P_{i})$. Then, $P_{i}^{x}$ is a _bound
$x$-extension_ of $P_{i}$ using $\mathcal{S}_{\mathrm{in}}$ if and only if the
followings conditions are satisfied:

  1. (1)

the maximum degree of $\operatorname{vcg}(P_{i}^{x})$ is not bigger than the
maximum degree of $\operatorname{vcg}(P)$,

  2. (2)

the diameter of graph $\operatorname{vcg}(P_{i}^{x}\setminus P_{i})$ is not
longer than the maximum diameter of the components of $\operatorname{vcg}(P)$.

###### Definition 0 (Maximum Extension).

Given a component $P_{i}$ of pattern $P$, a variable
$x\in\operatorname{var}(P_{i})$, and a finite set of Simple SHACL shapes
$\mathcal{S}_{\mathrm{in}}$,
$\operatorname{MaxExt}_{x}(P_{i},\mathcal{S}_{\mathrm{in}})$ is the maximum
bound $x$-extension for $P_{i}$ using $\mathcal{S}_{\mathrm{in}}$. The
_maximum extension_ for $P_{i}$ using $\mathcal{S}_{\mathrm{in}}$, denoted
$\operatorname{MaxExt}(P_{i},\mathcal{S}_{\mathrm{in}})$, is the pattern
$\bigcup_{x\in\operatorname{var}(P_{i})}\operatorname{MaxExt}_{x}(P_{i},\mathcal{S}_{\mathrm{in}})$.

Intuitively, Definition 19 and Definition 20 ensure that an extended component
is finite, but still allows for all possible mappings with another component:
Since we are only interested in finding axioms involving names in
$G_{\mathrm{ext}}$, we must use at least one such name in the mapping. Since
the other mapping component is a subset of $P$, the mapping can then, in the
worst case, only extend with respect to the maximum degree and diameter of
$P$.

The maximum extension thus allows for finding all axioms of interest via
component maps $h$ from $P_{1}$ to
$\operatorname{MaxExt}(P_{2},\mathcal{S}_{\mathrm{in}})$, where $P_{1}$ and
$P_{2}$ are components of $P$.

###### Definition 0 (Extended Component Map Axioms).

The set of _extended component map axioms_ of a pattern $P$, and a set of
shapes $\mathcal{S}_{\mathrm{in}}$, denoted
$\operatorname{MA}_{\mathcal{S}_{\mathrm{in}}}(P)$ is the set that includes an
axiom $\operatorname{C}_{u}\sqsubseteq V_{x}$ if and only if there is a pair
of components $P_{1}$ and $P_{2}$ of $P$, and a component map $h$ from $P_{1}$
to $\operatorname{MaxExt}(P_{2},\mathcal{S}_{\mathrm{in}})$ such that $h(x)=u$
and $u$ is a variable or an individual name occurring in $P_{2}$.

######  Proposition 0.

For every extended graph $G_{\mathrm{ext}}$ of a SCCQ $q=H\leftarrow P$ and
set of input shapes $\mathcal{S}_{\mathrm{in}}$, it holds that
$\operatorname{valid}(G_{\mathrm{ext}},\operatorname{MA}_{\mathcal{S}_{\mathrm{in}}}(P))$.

###  6.4. Axiomatizations for Role Hierachies

Not only variable concepts form hierarchies that are not entailed by the
axioms included this far. We finally infer axioms representing additional role
hierarchies, that are determined from the query (Definition 23).

###### Definition 0 (Role Hierarchy Axioms).

The _role hierarchy axioms_ of a query $q=(H\leftarrow P)$ are the set of
axioms, denoted $\operatorname{RS}(q)$, that include:

  1. (1)

for each role name $p\in P$, the axiom $\dot{p}\sqsubseteq p$,

  2. (2)

for each role name $p\in P$, the axiom $p\sqsubseteq\dot{p}$, if all atoms
with role name $p$ occurring in $P$ have the form $(x,y){:}p$ where variables
$x$ and $y$ occur in no other atom in $P$ and $x\neq y$,

  3. (3)

for each pair of role names $p,r$ with $(x,y){:}p\in P$ and either
$(x,y){:}r\in H$ or $(y,x){:}r\in H$

    1. (a)

the axiom $\dot{p}\sqsubseteq\ddot{r}$ (if $(x,y){:}r\in H$) or the axiom
$\dot{p}\sqsubseteq\ddot{r}^{-}$ (if $(y,x){:}r\in H$), if $P$ does not
contain any other atoms with role name $p$, and

    2. (b)

the axiom $\ddot{r}\sqsubseteq\dot{p}$ (if $(x,y){:}r\in H$) or the axiom
$\ddot{r}^{-}\sqsubseteq\dot{p}$ (if $(y,x){:}r\in H$), if $H$ does not
contain any other atoms with role name $r$.

Trivially, for any role name $p\in P$, the axiom $\dot{p}\sqsubseteq p$ holds,
since, by definition, $G_{\mathrm{med}}\subseteq G_{\mathrm{in}}$. The inverse
axiom $p\sqsubseteq\dot{p}$ holds, if the role name is unconstrained in
pattern $P$. Role hierarchy axioms between $p\in P$ and $r\in H$, that is
axioms $\ddot{r}\sqsubseteq\dot{p}$ and $\dot{p}\sqsubseteq\ddot{r}$, hold, if
there are no further restrictions on $r$ and $p$, respectively.

###### Example 0.

Consider the input shape
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}\sqsubseteq\exists
p.{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$
and the query
$q_{2}=\\{(\textit{x},\textit{y}){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p},\textit{z}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A}\\}\leftarrow\\{(\textit{x},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{z}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}\\}$.
The axioms presented prior to Definition 23 do not entail the shape
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{A}}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{A}}$,
even though
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A}$
should apply to the output graph: After all, we simply copy all instances of
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$
and the entirety of
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$.
If we include, however, axioms
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}\sqsubseteq{\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}$
and
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\dot{p}}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}$,
the new set of axioms does indeed entail
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{A}}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{p}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}\ddot{A}}$,
as expected. We can include these axioms – in this case – since we simply copy
$p$ in its entirety, or, formally, the variables in the only atomic pattern
including the role name $p$ are not further constrained.

######  Proposition 0.

For every extended graph $G_{\mathrm{ext}}$ of a SCCQ $q$, it holds that
$\operatorname{valid}(G_{\mathrm{ext}},\operatorname{RS}(q))$.

##  7\. Related Work

The problem of automatically inferring SHACL (or ShEx (Prud’hommeaux et al.,
2014)) shapes from various inputs has been studied before. Most commonly it
has been considered in the context of constructing shapes from concrete
instance data, based on summaries of statistical information over graphs
(Spahiu et al., 2018; Fernández-Álvarez et al., 2022; Rabbani et al., 2023),
or more involved machine learning techniques (Mihindukulasooriya et al., 2018;
Omran et al., 2023; Groz et al., 2022). Some approaches combine such methods
with tools for manual exploration and adaptation of inferred schemata (Boneva
et al., 2019). Our approach, on the other hand, allows the construction of
valid shapes from only input shapes and a given query, without the need to
consider (or indeed provide) any concrete instance data.

Our work is based in the correspondence of SHACL and description logics,
inspired by Bogaerts et al. (2022). This correspondence has been investigated
before. Astrea (Cimmino et al., 2020) produces SHACL shapes from OWL
ontologies by providing a mapping relating patterns of ontology constructs
(i.e., language constructs including a specific usage context) with equivalent
patterns of SHACL constructs validating them. Similarly, Pandit et al. (2018)
explore the usage of ontology design patterns for the generation of SHACL
shapes.

Inference of constraints, as well as SHACL shapes, from other data formalisms
has been studied as well. Calvanese et al. (2014) and Sequeda et al. (2012)
consider inference of RDFS and OWL, respectively, from direct mappings (Arenas
et al., 2012) between relational data and RDF. Similarly, Thapa and Giese
(2021) consider inferences of SHACL shapes from direct mappings, while
RML2SHACL (Delva et al., 2021) allows the translation of RML rules to SHACL
shapes. These approaches differ from our approach, in that the input is
restricted to a direct mapping or RML mapping from relational data, whereas in
our case, the input is defined by an arbitrary query pattern imposing
additional constraints, as well as constraints explicitly given as input
shapes.

More generally, the inference of constraints over views of relational
databases has been studied in the past (Klug and Price, 1982; Fan et al.,
2008; Stonebraker, 1975; Jacobs et al., 1982). While these approaches are
similar to our work, they face severe problems: In (Jacobs et al., 1982),
general first-order formulas are considered as constaints. Even though these
are more expressive than our constraints, the presented approach is not
feasible in practice. As a result, other approaches restrict constraints, most
commonly to functional or join dependencies, e.g., (Klug and Price, 1982; Fan
et al., 2008). These approaches can be considered complementary to our
approach, since our approach lacks cardinalities, which are required to
express functional dependencies in SHACL; on the other hand, functional
dependencies can not express crucial typing constraints for knowledge graphs
that are supported by our approach.

Finally, Thapa and Giese (2022) consider mappings of relational data to RDF.
In particular, the work focuses on including SQL integrity constraints (keys,
uniqueness and not-null constraints) in the translation to SHACL constraints,
allowing for a limited number of property constraints mapped from integrity
constraints.

##  8\. Concluding Remarks

We have presented an algorithm for constructing a set of shapes characterizing
the possible output graphs of CONSTRUCT queries, where the input graphs of
these queries can be constrained by a set of shapes as well. The shapes are
expressed in a subset of SHACL, whereas the queries are expressed in a subset
of SPARQL. This enables the inference of shapes over result graphs of data
processing pipelines (i.e., compositions of CONSTRUCT queries), which can be
used both for validation purposes when working with these result graphs, and
informatively, aiding developers directly.

The algorithm decides for the finite set of candidate shapes, whether they are
entailed by a set of description-logic axioms valid on the union of graphs
involved in the query operation. We prove soundness of this algorithm, and
provide an implementation.

#### Limitations

(1) The output shapes computed by our approach are sound, but incomplete.
Consider the problem
$q_{3}=\\{(x,y){:}p,z{:}A\\}\leftarrow\\{(x,y){:}p,z{:}A,(z,w){:}p\\}$ and
$\mathcal{S}_{\mathrm{in}}=\\{A\sqsubseteq\exists p.A\\}$, where the input
shape would apply to the output, but we can not infer it. This and similar
problems could perhaps be remedied by extending the inference of role hierachy
axioms to also consider input shapes.

(2) Our approach is limited to a subset of SHACL and SPARQL. In the extended
version, we show how to extend the approach to arbitrary $\mathcal{ALCHOI}$
constraints. Intuitively, this extension is possible because the propositions
presented in this paper are not restricted to Simple SHACL (consider, in
particular, Proposition 3).

#### Future Work

In order to extend the approach to queries involving generic patterns (e.g.,
$(x,y){:}z$ or $x{:}z$), an expansion to non-generic queries may be possible,
since all relevant role and concept names are known from template and input
shapes.

While the application of our approach to entire data processing pipelines is
straightforward, there are interesting empirical questions regarding the
properties of results shapes, e.g., depending on the nature of input shapes or
number of processing steps left as future work.

###### Acknowledgements.

This work was partially funded by the Deutsche Forschungsgemeinschaft (DFG)
under COFFEE – STA 572_15-2, and the DFG Germany’s Excellence Strategy – EXC
2120/1 – 390831618.

## References

  * (1)
  * Angles et al. (2018) Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter A. Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan F. Sequeda, Oskar van Rest, and Hannes Voigt. 2018.  G-CORE: A Core for Future Graph Query Languages. In _Proc. of SIGMOD_. ACM, 1421–1432.  https://doi.org/10.1145/3183713.3190654
  * Arenas et al. (2012) Marcelo Arenas, Alexandre Bertails, Eric Prud’hommeaux, Juan Sequeda, et al. 2012\.  A Direct Mapping of Relational Data to RDF.  Retrieved 12.02.2024 from https://www.w3.org/TR/rdb-direct-mapping/
  * at University of Oxford (2008) KRR Group at University of Oxford. 2008.  HermiT OWL Reasoner.  Retrieved 12.10.2023 from http://www.hermit-reasoner.com/
  * Baader et al. (2003) Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider (Eds.). 2003.  _The Description Logic Handbook: Theory, Implementation, and Applications_.  Cambridge University Press.
  * Bielefeldt et al. (2018) Adrian Bielefeldt, Julius Gonsior, and Markus Krötzsch. 2018.  Practical Linked Data Access via SPARQL: The Case of Wikidata. In _Workshop on Linked Data on the Web co-located with The Web Conference 2018, LDOW@WWW 2018_ _(CEUR Workshop Proceedings, Vol. 2073)_. CEUR-WS.org.  https://ceur-ws.org/Vol-2073/article-03.pdf
  * Bogaerts et al. (2022) Bart Bogaerts, Maxime Jakubowski, and Jan Van den Bussche. 2022.  SHACL: A Description Logic in Disguise. In _Proc. of Logic Programming and Nonmonotonic Reasoning_ _(LNCS, Vol. 13416)_. Springer, 75–88.  https://doi.org/10.1007/978-3-031-15707-3_7
  * Boneva et al. (2019) Iovka Boneva, Jérémie Dusart, Daniel Fernández-Álvarez, and José Emilio Labra Gayo. 2019.  Shape Designer for ShEx and SHACL constraints. In _Proc. of the ISWC 2019 Satellite Tracks co-located with ISWC 2019_ _(CEUR Workshop Proceedings, Vol. 2456)_. CEUR-WS.org, 269–272.  https://ceur-ws.org/Vol-2456/paper70.pdf
  * Bonifati et al. (2020) Angela Bonifati, Wim Martens, and Thomas Timm. 2020.  An analytical study of large SPARQL query logs.  _VLDB J._ 29, 2-3 (2020), 655–679.  https://doi.org/10.1007/s00778-019-00558-9
  * Calvanese et al. (2014) Diego Calvanese, Wolfgang Fischl, Reinhard Pichler, Emanuel Sallinger, and Mantas Simkus. 2014.  Capturing Relational Schemas and Functional Dependencies in RDFS. In _Proc. of the AAAI Conference on Artificial Intelligence_. AAAI Press, 1003–1011.  https://doi.org/10.1609/AAAI.V28I1.8867
  * Cimmino et al. (2020) Andrea Cimmino, Alba Fernández-Izquierdo, and Raúl García-Castro. 2020.  Astrea: Automatic Generation of SHACL Shapes from Ontologies. In _Proc. of ESWC_ _(LNCS, Vol. 12123)_. Springer, 497–513.  https://doi.org/10.1007/978-3-030-49461-2_29
  * Cyganiak et al. (2014) Richard Cyganiak, David Wood, Markus Lanthaler, Graham Klyne, Jeremy J. Carroll, and Brian McBride. 2014.  RDF Concepts and Abstract Syntax.  Retrieved 12.02.2024 from https://www.w3.org/TR/rdf11-concepts/
  * Delva et al. (2021) Thomas Delva, Birte De Smedt, Sitt Min Oo, Dylan Van Assche, Sven Lieber, and Anastasia Dimou. 2021.  RML2SHACL: RDF Generation Taking Shape. In _Proc. of Knowledge Capture Conference_. ACM, 153–160.  https://doi.org/10.1145/3460210.3493562
  * Fan et al. (2008) Wenfei Fan, Shuai Ma, Yanli Hu, Jie Liu, and Yinghui Wu. 2008.  Propagating functional dependencies with conditions.  _Proc. VLDB Endow._ 1, 1 (2008), 391–407.  https://doi.org/10.14778/1453856.1453901
  * Fernández-Álvarez et al. (2022) Daniel Fernández-Álvarez, José Emilio Labra Gayo, and Daniel Gayo-Avello. 2022.  Automatic extraction of shapes using sheXer.  _Knowledge-Based Systems_ 238 (2022), 107975.  https://doi.org/10.1016/J.KNOSYS.2021.107975
  * Groz et al. (2022) Benoît Groz, Aurélien Lemay, Slawek Staworko, and Piotr Wieczorek. 2022.  Inference of Shape Graphs for Graph Databases. In _ICDT_ _(LIPIcs, Vol. 220)_. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14:1–14:20.  https://doi.org/10.4230/LIPICS.ICDT.2022.14
  * Gutierrez et al. (2011) Claudio Gutierrez, Carlos A. Hurtado, Alberto O. Mendelzon, and Jorge Pérez. 2011.  Foundations of Semantic Web databases.  _J. Comput. Syst. Sci._ 77, 3 (2011), 520–541.
  * Jacobs et al. (1982) Barry E. Jacobs, Alan R. Aronson, and Anthony C. Klug. 1982.  On Interpretations of Relational Languages and Solutions to the Implied Constraint Problem.  _ACM Trans. Database Syst._ 7, 2 (1982), 291–315.  https://doi.org/10.1145/319702.319730
  * Klug and Price (1982) Anthony C. Klug and Rod Price. 1982.  Determining View Dependencies Using Tableaux.  _ACM Trans. Database Syst._ 7, 3 (1982), 361–380.  https://doi.org/10.1145/319732.319738
  * Knublauch and Kontokostas (2017) Holger Knublauch and Dimitris Kontokostas. 2017.  Shapes Constraint Language (SHACL).  Retrieved 12.02.2024 from https://www.w3.org/TR/shacl/
  * Kostylev et al. (2015) Egor V. Kostylev, Juan L. Reutter, and Martín Ugarte. 2015.  CONSTRUCT Queries in SPARQL. In _Proc. of International Conference on Database Theory, ICDT_ _(LIPIcs, Vol. 31)_. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 212–229.  https://doi.org/10.4230/LIPIcs.ICDT.2015.212
  * Leinberger et al. (2019) Martin Leinberger, Philipp Seifer, Claudia Schon, Ralf Lämmel, and Steffen Staab. 2019.  Type Checking Program Code Using SHACL. In _Proc. of ISWC_ _(LNCS, Vol. 11778)_. Springer, 399–417.  https://doi.org/10.1007/978-3-030-30793-6_23
  * Mihindukulasooriya et al. (2018) Nandana Mihindukulasooriya, Mohammad Rifat Ahmmad Rashid, Giuseppe Rizzo, Raúl García-Castro, Óscar Corcho, and Marco Torchiano. 2018.  RDF Shape Induction Using Knowledge Base Profiling. In _Prov. of the Symposium on Applied Computing_. ACM, 1952–1959.  https://doi.org/10.1145/3167132.3167341
  * Omran et al. (2023) Pouya Ghiasnezhad Omran, Kerry Taylor, Sergio José Rodríguez Méndez, and Armin Haller. 2023.  Learning SHACL shapes from knowledge graphs.  _Semantic Web_ 14, 1 (2023), 101–121.  https://doi.org/10.3233/SW-223063
  * Pandit et al. (2018) Harshvardhan J. Pandit, Declan O’Sullivan, and Dave Lewis. 2018.  Using Ontology Design Patterns To Define SHACL Shapes. In _Proc. of the Workshop on Ontology Design and Patterns (WOP 2018) co-located with ISWC 2018_ _(CEUR Workshop Proceedings, Vol. 2195)_. CEUR-WS.org, 67–71.  https://ceur-ws.org/Vol-2195/research_paper_3.pdf
  * Prud’hommeaux et al. (2014) Eric Prud’hommeaux, José Emilio Labra Gayo, and Harold R. Solbrig. 2014.  Shape expressions: an RDF validation and transformation language. In _Proc. of the International Conference on Semantic Systems, SEMANTiCS_. ACM, 32–40.  https://doi.org/10.1145/2660517.2660523
  * Rabbani et al. (2023) Kashif Rabbani, Matteo Lissandrini, and Katja Hose. 2023.  Extraction of Validating Shapes from very large Knowledge Graphs.  _Proc. VLDB Endow._ 16, 5 (2023), 1023–1032.  https://doi.org/10.14778/3579075.3579078
  * Reiter (1982) Raymond Reiter. 1982.  Towards a Logical Reconstruction of Relational Database Theory. In _On Conceptual Modelling (Intervale)_ _(Topics in Information Systems)_. Springer, 191–233.
  * Seifer et al. (2024) Philipp Seifer, Daniel Hernández, Ralf Lämmel, and Steffen Staab. 2024.  Code for From Shapes to Shapes.  https://doi.org/10.18419/darus-3977
  * Seifer et al. (2021) Philipp Seifer, Ralf Lämmel, and Steffen Staab. 2021.  ProGS: Property Graph Shapes Language. In _Proc. of ISWC_ _(LNCS, Vol. 12922)_. Springer, 392–409.  https://doi.org/10.1007/978-3-030-88361-4_23
  * Sequeda et al. (2012) Juan F. Sequeda, Marcelo Arenas, and Daniel P. Miranker. 2012.  On directly mapping relational databases to RDF and OWL. In _WWW_. ACM, 649–658.  https://doi.org/10.1145/2187836.2187924
  * Spahiu et al. (2018) Blerina Spahiu, Andrea Maurino, and Matteo Palmonari. 2018.  Towards Improving the Quality of Knowledge Graphs with Data-driven Ontology Patterns and SHACL. In _Proc. of the Workshop on Ontology Design and Patterns (WOP 2018) co-located with ISWC 2018_ _(CEUR Workshop Proceedings, Vol. 2195)_. CEUR-WS.org, 52–66.  https://ceur-ws.org/Vol-2195/research_paper_2.pdf
  * Stonebraker (1975) Michael Stonebraker. 1975.  Implementation of Integrity Constraints and Views by Query Modification. In _Proc. of SIGMOD_. ACM, 65–78.  https://doi.org/10.1145/500080.500091
  * Thapa and Giese (2021) Ratan Bahadur Thapa and Martin Giese. 2021.  A Source-to-Target Constraint Rewriting for Direct Mapping. In _Proc. of ISWC_ _(LNCS, Vol. 12922)_. Springer, 21–38.  https://doi.org/10.1007/978-3-030-88361-4_2
  * Thapa and Giese (2022) Ratan Bahadur Thapa and Martin Giese. 2022.  Mapping Relational Database Constraints to SHACL. In _Proc. of ISWC_ _(LNCS, Vol. 13489)_. Springer, 214–230.  https://doi.org/10.1007/978-3-031-19433-7_13

##  Appendix A Structure of the Appendix

This appendix is structured as follows. In Appendix B we give details about
our implementation, and a feasibility experiment investigating runtime
performance. Appendix C gives extended versions of the running examples used
throughout the paper. Appendix D contains the full proofs for all propositions
from the main paper. Finally, Appendix E details how the method from the main
paper can be extended for more general types of SHACL shapes, and Appendix F
gives proofs related to these extensions.

##  Appendix B Implementation Runtime Evaluation

###  B.1. Implementation Overview

We implemented Algorithm 1, relying on a straightforward translation of
Algorithm 2 to Scala for validation with respect to a single candidate shape,
and a generator for candidates based on the syntax of Simple SHACL. For
reasoning tasks, our implementation supports any OWL
API333https://github.com/owlcs/owlapi reasoner. In particular, we rely on the
HermiT (at University of Oxford, 2008) reasoner as a default.

Our implementation features tools for generative exploration regarding query
and vocabulary size, a setup for performance evaluation and results (see also
the remainder of this section), a test suite, and the examples from this paper
in mechanized form. To this end, the implementation features a command-line
application for parsing and inferring result shapes for examples (e.g., those
supplied in the project repository), taking SCCQ and (Simple) SHACL shapes as
input, both in DL and JSON-LD syntax. The implementation also features a
library for applying the shapes-to-shapes method, supporting both Simple SHACL
and $\mathcal{ALCHOI}$-based shapes as input, and returning inferred axioms in
internal datastructures that can then be utilized in a wider range of
reasoning tasks. Additionally, we also include a tutorial giving a more
intuitive and hands-on introduction to our method. The implementation (Seifer
et al., 2024) is available under a free software license on
GitHub444https://github.com/softlang/s2s.

###  B.2. Evaluation: Feasibility

We show feasibility of our method and implementation through the following
evaluation of runtime performance. This evaluation is based on randomly
generated problems (i.e., sets of input shapes as well as queries). Thus, the
experiment discussed here shows basic feasibility of our method with synthetic
data, though results on real-world data may differ.

As performance depends largely on the reasoning task (see also below), results
can differ based on the reasoner implementation used. Multiple reasoners are
available with our implementation, and their respective optimization
strategies may differ. Some reasoner implementations or optimization
strategies are not deterministic; Thus, as a simple optimization, our
implementation can abort runs with a set timeout and retry computing results,
in order to avoid unlucky models for non-deterministic reasoner optimization
strategies (this is reported in the results).

#### Experimental Setup

We refer to the project setup (in particular, the specification in build.sbt)
with respect to versions of the respective software, et. al. Beyond that, we
run experiments with Microsoft JDK build openjdk 17.0.7 2023-04-18 LTS on
Windows 10 Pro (Version 10.0.19045), on commodity hardware (Intel i5-6600K @
3.5GHz, 16GB RAM).

We define the following three sample configurations and give the number of
atomic patterns per query (for template and pattern each) as well as the
number of input shapes:

  * •

SMALL 1-2 templates and patterns, 1-2 shapes.

  * •

MEDIUM 5-7 templates and patterns, 5-7 shapes.

  * •

LARGE 11-13 templates and patterns, 11-13 shapes

As a basis for these scenarios, we refer to the following real-world query
datasets (logs), where most queries (more than $90\%$) have fewer than 6 or 7
patterns (Bielefeldt et al., 2018; Bonifati et al., 2020), relating to our
MEDIUM configuration. More than half include only on pattern, relating to our
SMALL configuration. Our LARGE configuration covers outliers of very large
queries (less than $1\%$ of real-world queries).

For all samples, we draw fresh variables (per pattern) with a probability of
$0.5$ and fresh concepts or role names with a probability of $0.8$, and sample
property versus concept atomic patterns with a ratio of $0.3$. We provide the
full details on all parameters used for sampling with the implementation
source code.

Note, that we generate shapes from the _vocabulary of the query_. Thus, the
number of input shapes given here is not comparable to the size of usual sets
of SHACL shapes in real-world datasets. That is, the sets of 1.5/6/12 shapes
constrain the relatively small vocabulary of an input query rather tightly. We
do not know of any empirical data on the average number of shapes in the query
(pattern) vocabulary, i.e., that apply to a particular query, thus we estimate
the numbers as given above.

We run and measure $5.000$ samples each for the three given configurations,
using a fixed seed for the random generator, and measure execution time for a
single run of the algorithm per sample, after first running $100$ additional
samples as warmup. This experiment uses the HermiT(at University of Oxford,
2008) reasoner.

#### Results of the Experiment

A summary of results is given in Table 1. The full output with input shapes,
input queries, fine-grained execution metrics, as well as output shapes is
included with the project source code as a CSV file and a summary report. Both
the full output as well as the summary can be generated by executing the
profile main method (see the implementation documentation for details on how
to re-run the experiment as-is, or modify it across various dimensions).

Table 1. Results (average and median execution time in milliseconds without timeouts, the number of timeouts (limit: 10 minutes), as well as percentage of processing time spent on reasoning) for SMALL, MEDIUM and LARGE configurations. Configuration | Average | Median | T/O | Reasoning
---|---|---|---|---
SMALL | 3 | 0 | 0 | 38,42%
MEDIUM | 40 | 20 | 0 | 87,11%
LARGE | 693 | 243 | 20 | 97,66%

#### Interpretation

We show in this experiment the basic feasibility of our method, with average
and median execution times for even very large samples of less than one
second. For the largest samples, few ($0.4\%$) samples time out, with a set
timeout of 10 minutes. We hypothesize that this is due to the reasoner
sometimes choosing an unlucky model, where reasoning takes a very long time;
though this could also perhaps be caused by bugs in the reasoner
implementation. Indeed, the majority of time is spent on reasoning for larger
configuration (see Table 1) and by detailed inspection of the full log, this
holds true for timeouts as well.

##  Appendix C Extended Examples

In this section, we extend upon the running examples. We first provide
additional details on the running example incorporated in the body of the
paper, including the example using concrete SHACL and SPARQL syntax. Next, we
extend upon the running example by giving additional example queries.

#### Implementation

All examples from the main paper and from this section are also provided in
mechanized form with the implementation. To this end, the implementation
contains .shacl (as well .json) and .sparql files, where example shapes are
included in formal description logics and JSON-LD syntax, and SCCQ queries in
concrete SPARQL syntax. We refer to the documentation (README.md) for more
details on running example instances, and obtaining different kinds of
outputs.

#### Running Example: Full Set of Shapes $\mathcal{S}_{\text{out}}$

The full set of output shapes from Example 4 is given below. Note, that some
shapes (such as tautologies and shapes trivially entailed by other shapes) are
omitted.

###### Example 0.

Full output shapes for
$q_{1}=\\{\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},\textit{z}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},(\textit{y},\textit{z}){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}\\}\leftarrow\\{(\textit{w},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},(\textit{x},\textit{z}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{z}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$
(Example 11) and the set of input shapes $S_{1}=\\{A\sqsubseteq\exists
p.B,\exists r.\top\sqsubseteq B,B\sqsubseteq E\\}$ (Example 8), as first
introduced in Example 4.

$\displaystyle S_{1\textrm{-out}}=\\{$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E}\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.\top\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.\top\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.\top\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.\top\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.\top\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.\top\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq\forall{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p^{-}}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},$
$\displaystyle\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.\top\sqsubseteq\exists{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}.{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\
\\}$

#### Running Example: Concrete Syntax

We next give the running example (e.g., Example 1) in concrete SPARQL and
SHACL (Turtle) syntax. We assume the default prefix : for the example domain
(unspecified), and prefix sh: for SHACL (i.e., bound to
http://www.w3.org/ns/shacl#).

⬇

:s1 a sh:NodeShape ;

sh:targetClass :A ;

sh:property [

sh:path :p ;

sh:qualifiedMinCount 1 ;

sh:qualifiedValueShape [

sh:class :B

]

] .

:s2 a sh:NodeShape ;

sh:targetSubjectsOf :r ;

sh:class :B .

:s3 a sh:NodeShape ;

sh:targetClass :B ;

sh:class :E .

Figure 4. Shapes $s_{1}$ ($A\sqsubseteq\exists p.B$), $s_{2}$ ($\exists
r.\top\sqsubseteq B$), and $s_{3}$ ($B\sqsubseteq E$) using a concrete SHACL
syntax (Turtle).

⬇

CONSTRUCT {

?y a :E .

?y :p ?z .

?z a :B

} WHERE {

?w :p ?y .

?y a :B .

?x :p ?z .

?z a :E

}

Figure 5. Example query
$q_{1}=\\{\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}E},\textit{z}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},(\textit{y},\textit{z}){:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}p}\\}\leftarrow\\{(\textit{w},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},(\textit{x},\textit{z}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{z}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}E}\\}$
in concrete SPARQL syntax.

#### Additional Examples

We now give additional examples problem instances, that is, queries and sets
of input shapes, and (a subset of) the corresponding output shapes. For the
full output, as well as all intermediate components, i.e., the inferred
axioms, we refer to the implementation, which renders full internal details
via the \--debug flag. All examples are included with the implementation.

###### Example 0.

With input
$q_{4}=\\{\textit{x}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A},\\}\leftarrow\\{\textit{x}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},\\}$
and
$S_{4}=\\{{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\\}$,
we obtain the set
$\\{{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A}\\}$
as output.

Query $q_{4}$ is a simple example, demonstrating how our method maintains
subsumption relationships through renaming of concepts, in this simple case
swapping the names $A$ and $B$. A core mechanism allowing this is the
subsumption between the variable concept for query variables ?x and ?y
entailed by our inferred axioms, which holds on all extended graphs for
$q_{4}$ and $S_{4}$.

###### Example 0.

With input
$q_{5}=\\{\textit{x}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B},\textit{y}{:}{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A},\\}\leftarrow\\{\textit{x}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A},(\textit{x},\textit{y}){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B},\\}$
and
$S_{5}=\\{{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A},{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\sqsubseteq\exists{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p}.{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\\}$,
we obtain the set
$\\{{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A}\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}\\}$
as output.

Here, we continue with another example with the same, simple template as in
the previous example. This simple template serves to demonstrate the
consequences of variable concept subsumption between the variables ?y and ?x
directly, as the output shape
${\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}A}\sqsubseteq{\color[rgb]{0.90234375,0.09765625,0.29296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.09765625,0.29296875}B}$.
This subsumption relationship results from the mapping step discussed in
Section 6: Since we know for all bindings of y in the query, that both the
pattern
$\textit{y}{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$
is always satisfied (since
${\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}\sqsubseteq{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}A}$)
and the same for
$(\textit{y},z){:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}p},z{:}{\color[rgb]{0.9609375,0.51171875,0.19140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.9609375,0.51171875,0.19140625}B}$
(for some fresh variable $z$, since