summarizes our previous work.
Some graph query languages are composable (i. e., they construct new graphs as results) and thereby
allow for the fruitful composition of queries into data processing pipelines. Examples for such languages
are SPARQL (in particular, its CONSTRUCT [
When graphs existing in the context of such composable query languages are validated using
constraints specified in a shape description language such as SHACL [
Problem Description In our recent paper [
Formally, we define the problem OutputShapes with signature (in, ) ↦→ out-max, where is a query and in and out-max are two sets of shapes, called the input and output shapes. The set out-max is the maximum set of shapes such that for every graph in that satisfies the input shapes – we write valid(in, in) – the graph resulting from evaluating on in, denoted JKin , satisfies the output shapes, i. e., valid(JKin , out-max).
Running Example Consider a problem OutputShapes with a query 1 and a set of shapes 1 as input. Let 1 = {y:, z:, (y, z):} ← { (w, y):, y:, (x, z):, z:}. Given a graph in, query 1 finds bindings for variable y that are , and bindings for variable z that are , both with incoming edges with role name in in. Then, the query constructs the output graph, out = J1Kin , consisting only of these bindings for z and y, with inverted concept annotations and -edges between them. Note, that we color-code the namespace of the input versus output graphs, since the extensions of the involved concept and role names are not the same.
Let 1 = {1, 2, 3} where 1 = ⊑ ∃., 2 = ∃.⊤ ⊑ and 3 = ⊑ . The graphs 1 (a) and 2 (b) in Figure 1 are valid with respect to 1. Graphs J1K1 (c) and J1K2 (d) in Figure 1 are the respective output graphs for 1 over 1 and 2, respectively.
Some expected output shapes are ⊑ ∃. and ⊑ . The first shape follows directly from the query template. Each node labelled has an outgoing edge to a node labelled . The second shape ⊑ is valid because ⊑ holds on all input graphs: As a result, we can infer that all bindings for y are also bindings for z, such that ⊑ follows from the query template.
Proposed Algorithm In this paper, we summarize the algorithm we presented in [
To this end, we split the problem into two subproblems: First, the problem of deciding whether any given shape must be included in the output, and secondly the problem of generating a set of candidate shapes. The second problem turns out to be rather trivial, as the set of candidates is finite: We consider a subset of SHACL that is (syntactically) finite for a finite vocabulary, and show that all relevant candidates are indeed from the finite vocabulary of the query. In our extended version, we show that this also holds for a much larger subset of SHACL.
Thus, we focus on the first problem in Section 2 and Section 3.
As hinted earlier, diferent occurrences of the same concept name do not have the same extensions: A query matches on input graphs, determines valuations (as subsets of the input), and constructs new graphs. We distinguish between the inputs, intermediate bindings, as well as the constructed output by rewriting input symbols , into fresh symbols ˙, ˙ after the first step, and into ¨, ¨ after the second step. 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 () = as a concept assertion :, where is a fresh concept name.
In order to axiomatize how (all possible) input graphs are connected to (all possible) output graphs, we define a (virtual) extended graph ext, that unifies the diferent steps, and therefore allows us to reason about them: ext := in ∪ ˙med ∪ V ∪ ¨out, where med is ⋃︀ ( )⊆ in ( ) (i.e., the union of all graphs ( ) resulting from replacing every variable in with ()), out is JKin , and V is the graph containing an assertion : if and only if there exists a valuation such that ( ) ⊆ in , ˙ ¨ and () = . Figure 2 shows the extended graph and its components for the running example query 1, and the graph 1 in Figure 1 .
Proposition 1. Given a graph in and a query , let the graphs ext, med, and out be the extended graph and its components. For every axiom that does not include names with dots (e. g., names ˙, ¨, ˙, or ¨), the following equivalences hold: valid(in, { }) if and only if valid(ext, { }), valid(med, { }) if and only if valid(ext, { ˙ }), and valid(out, { }) if and only if valid(ext, {¨}).
Given the notion of extended graphs, we can prove Proposition 1 (see [
Let us now consider what axioms can be inferred, by inspecting the running example. First, we can notice that the input shapes in are valid on all input graphs, by definition. Thus, we include them in our knowledge base Σ.
Some axioms of the validation knowledge base (unique name, closed world and domain closure assumptions) can be approximated by investigating the query . The unique name assumption is limited to individual names that occur in the query; in the running example there are none. Since a query does not determine the set of individual names, no axioms related to the domain closure assumption can be inferred. On the other hand, a query does restrict concept names that appear in the query with respect to the closed world assumption (CWA).
For the running example, we can thus infer {˙ ≡ ⊓ , ˙ ≡ ⊓ }, because e. g., concept ˙ in the extended graph is defined by filtering with variable , based on the query pattern y: in 1. We can also infer axioms { ≡ ∃ ., ≡ ∃ ., ≡ ∃ . ⊓ , ≡ ∃ . ⊓ } since variable concepts are defined by constraints to the variable in the query pattern. For example, is constrained by patterns (w, y): and y: in 1, and thus bound by ∃. ⊓. This is a crucial step, since concept and role names in the extended graph are defined in terms of these variable concepts: {¨ ≡ , ¨ ≡ } since e. g., concept ¨ in the extended graph is defined by , as it only occurs in the single construct pattern z:. With similar reasoning, {∃˙. ≡ , ∃˙. ≡ , ∃˙.⊤ ≡ ( ⊓ ∃˙.) ⊔ ( ⊓ ∃˙.)} as well as {∃¨. ≡ , ∃¨.⊤ ≡ ⊓ ∃¨.} (and their inverse counterparts) can be constructed with respect to role names.
Query 1 has two components 1 = {(w, y):, y:} and 2 = {(x, z):, z:} not sharing variables. The CWA encoding does not entail ⊑ , even though this axiom is both valid in all extended graphs, and required for inferring, e. g., the result shape ⊑ . In another step of the algorithm, we infer these additional subsumptions by constructing variable mappings ℎ between query components, that are potentially extended with input shapes. In this case, we know based on input shape 1 that ⊑ . We can utilize this knowledge to extend component (w, y):, y:, adding the pattern y: which does not alter the queries results. Then, we can find the mapping ℎ(x) = w, ℎ(z) = y such that ℎ(2) ⊆ 1, which implies ⊑ and ⊑ .
We presented an algorithm for inferring a set of shapes that validate the possible output graphs of a CONSTRUCT query, where input graphs of this query can be constrained by a set of shapes as well. 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.
Our approach difers from related work (e.g., [
Acknowledgments This work was partially funded by Deutsche Forschungsgemeinschaft (DFG) under SPP 1921 – 318363223, and the DFG Germany’s Excellence Strategy – EXC 2120/1 – 390831618. [12] N. Mihindukulasooriya, M. R. A. Rashid, G. Rizzo, R. García-Castro, Ó. Corcho, M. Torchiano, RDF shape induction using knowledge base profiling, in: Prov. of the Symposium on Applied Computing, ACM, 2018, pp. 1952–1959. doi:10.1145/3167132.3167341. [13] P. G. Omran, K. Taylor, S. J. R. Méndez, A. Haller, Learning SHACL shapes from knowledge graphs,
Semantic Web 14 (2023) 101–121. doi:10.3233/SW-223063. [14] B. Groz, A. Lemay, S. Staworko, P. Wieczorek, Inference of shape graphs for graph databases, in: ICDT, volume 220 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 14:1–14:20. doi:10.4230/LIPICS.ICDT.2022.14. [15] A. C. Klug, R. Price, Determining view dependencies using tableaux, ACM Trans. Database Syst. 7 (1982) 361–380. doi:10.1145/319732.319738. [16] W. Fan, S. Ma, Y. Hu, J. Liu, Y. Wu, Propagating functional dependencies with conditions, Proceedings VLDB Endow. 1 (2008) 391–407. doi:10.14778/1453856.1453901. [17] M. Stonebraker, Implementation of integrity constraints and views by query modification, in:
Proceedings of SIGMOD, ACM, 1975, pp. 65–78. doi:10.1145/500080.500091. [18] B. E. Jacobs, A. R. Aronson, A. C. Klug, On interpretations of relational languages and solutions to the implied constraint problem, ACM Trans. Database Syst. 7 (1982) 291–315. doi:10.1145/ 319702.319730. [19] R. B. Thapa, M. Giese, Mapping relational database constraints to SHACL, in: Proceedings of ISWC, volume 13489 of LNCS, Springer, 2022, pp. 214–230. doi:10.1007/978-3-031-19433-7_13. [20] R. B. Thapa, M. Giese, A source-to-target constraint rewriting for direct mapping, in: Proceedings of
ISWC, volume 12922 of LNCS, Springer, 2021, pp. 21–38. doi:10.1007/978-3-030-88361-4_2. [21] T. Delva, B. D. Smedt, S. M. Oo, D. V. Assche, S. Lieber, A. Dimou, RML2SHACL: RDF generation taking shape, in: Proceedings of Knowledge Capture Conference, ACM, 2021, pp. 153–160. doi:10.1145/3460210.3493562. [22] P. Seifer, D. Hernández, R. Lämmel, S. Staab, Code for from shapes to shapes, 2024. doi:10.18419/ darus-3977.