Despite the many advantages that ontology-based data access (OBDA) has brought to a range of application domains, state-of-the-art OBDA systems still do not support popular graph database management systems such as Neo4j. Algorithms for query rewriting focus on languages like conjunctive queries and their unions, which are fragments of first-order logic and were developed for relational data. Such query languages are poorly suited for querying graph data. Moreover, they also limit the expressiveness of the ontology languages that admit rewritings, restricting them to those where the data complexity of reasoning is not higher than it is in first-order logic. In this paper, we propose a technique for rewriting a family of navigational queries for a suitably restricted fragment of ℰℒℋℐ that extends DL-Lite and that is NL-complete in data complexity. We implemented a proof-of-concept prototype that rewrites into Cypher queries, and tested it on a real-world cognitive neuroscience use case with promising results.
standard for extending C2RPQs, are NL complete in data complexity (under the so-called walk semantics). This means that we are not bound to DL-Lite and can attempt query rewriting for richer ontology languages, provided that they have NL data complexity.
Contributions This extended abstract summarizes the following results, described in [
TBoxes, that have axioms of the form (NF1) ⊑ , For our algorithm we consider ℰ ℒℋℐ⊥ (NF2) ∃. ⊑ , (NF3) ⊑ ∃., (NF4) ⊑ , (NF5) ∃− .⊤ ⊑ , or (NF6) ⊑ ∃− .⊤.
In Navigational Conjunctive Queries (NCQs), atoms take the form (︀ 1 ∪ · · · ∪ )︀ () or
︀( 1 ∪ · · · ∪ )︀ (, ) or (︀ 1 ∪ · · · ∪ )︀ * (, ), with a concept name and each a restricted
regular path expression := | − | * | (− )* . As a first step towards our query rewriting
TBoxes.
algorithm, we introduce the so-called concept dependency graph for ℰ ℒℋℐ⊥
Concept Dependency Graph As the name suggests the concept dependency graph (CDG)
depicts the dependencies of concepts of a given TBox. The nodes of the CDG represent concepts
and for axioms in form of (NF1), e.g., ⊑ we add an edge pointing from to with the
empty label . In case of an existential restriction on the left-hand side as in (NF2) or (NF5)
we additionally label this edge with the role name. In order to make the construction of the
CDG complete for TBox reasoning we extend it with additional edges and witnessing nodes
for axioms with existential quantifiers on the right-hand side, i.e., (NF3) and (NF6). Having
all these edges in place it is possible to check for TBox entailments. More precisely, it holds
that |= ∃1 . . . ∃. ⊑ if and only if there is a path from to with a sequence of edge
labels 1, . . . , (possibly interleaved with -labeled edges) such that ⊑* for 1 ≤ ≤ .
Note that, in particular, this means that |= ⊑ if there is a path from to with labels
only. We illustrate these properties of the CDG in the example below. For a formal definition of
concept dependency graphs see [
Example 1. For the TBox = {2 ⊑ 1, ∃.1 ⊑ 1, ∃3.1 ⊑ 3, 3 ⊑ 2, ∃1.2 ⊑ 1, ∃2− .⊤ ⊑ 3, ⊑ 2, ∃2.3 ⊑ 2, 1 ⊑ ∃2.3} the CDG is as in Figure 1. The presence of paths in the CDG corresponds to concept inclusions that hold in . We illustrate this on an ABox = {1(1, 2), 2(2, 3), 3(3, 4), 1(4, 5), 2(5)}. Since there is the path 3 2 3 1 start 3 2 12 1 1 2
r 1 3 2
⊤ ⊤ 3 2− 2 1 1
1 2 3 3 ∃2 ∃2.
3 2 3 2−
⊤ 112233112 in the CDG of it follows for 1 that , |= 1(1). However, as we mentioned before, we can use the CDG to check for TBox entailments, i.e, from the path 112233112 we can infer that |= ∃1∃2∃3∃1.2 ⊑ 1. The construction of the entailment from with a concept name on CDG is complete, in the sense that for every ℰ ℒℋℐ⊥ the right-hand side there exists a corresponding path in the CDG of .
Extracting regular path expressions. Given a CDG and a concept in , we construct an NFA A () that accepts the propagating paths in which start at node and end in another concept while passing over only roles or , as illustrated in Example 2. We then use an of-the-shelf technique to transform this NFA into a regular expression, and finally we eliminate all occurrences of from this regular expression.
Example 2. For the CDG from Example 1, we can see its 1-path-generating NFA in Figure 2.
paths ending in 1 paths ending in 2 paths ending in 3 The extracted RPE is: (︀ (⏞(1 ∪ (123))* 1) ∪ ⏞(1+(231+)* 2) ∪ (⏞1+2(31+2)* 3) ︀) .
⏟ ⏟ ⏟
Rewriting Atomic Queries Into Regular Path Expressions We replace each in a given
input of the form (︀ 1 ∪ · · · ∪ )︀ () with the regular expression described above. Then we
replace each role in the regular path expression with a union over all roles such that ⊑* .
Rewriting NCQs into UC2RPQs Given a NCQ (⃗) and an ℰ ℒℋℐ⊥ TBox , we
exhaustively apply the so-called clipping function, inspired by [7]. It relies on a well-known property
of ℰ ℒℋℐ: for each and there is a universal, forest-shaped model ℐ that can be used for
answering all C2RPQs. Intuitively, we consider each possible set of variables that may be
mapped to the same ‘anonymous’ object of maximal depth in a tree structure of ℐ. We know
that each such is introduced to satisfy an existential axiom ⊑ ∃., that is, it has a parent
that satisfies , and is created as an -child of that is . Exploiting this, we can ‘remove’
from the query the parts that are guaranteed to be locally satisfied using ’s -child . This idea
has been applied to variants of (U)CQs [7], where each application must only remove the query
atoms that are locally satisfied. But in navigational queries we must consider also how path
expressions can be partially satisfied, and modify the expressions in the atoms accordingly. E.g.,
given () = (* ∪ * )(, ), () and = { ⊑ ∃.}, a possible application of clipping
returns ′() = * (, ), (). Note that * ∪ * is replaced by * , reflecting the fact that an *
path to an can always be extended to an * path to a in the models of , but this does not
apply to the * paths. We show in [
By clipping exhaustively, iterating over all sets of variables in and all axioms in of the form ⊑ ∃. and ⊑ ∃− .⊤, and taking each result as a disjunct in a union of NCQs, we obtain a query that has the same answers as the original NCQ, but whose variables are mapped to ABox individuals only. We can then apply the rewriting of atomic queries into regular path expressions described above, and obtain a sound and complete rewriting of NCQs mediated by ontologies into UC2RPQs . ℰ ℒℋℐ⊥
TBox (in OWL We implemented a proof-of-concept prototype [8] that, given an ℰ ℒℋℐ⊥ syntax), rewrites NCQs into UC2RPQs and translates them into Cypher. We execute the experiments on a machine running Ubuntu 22.04.4 with an Intel Core i7-6700HQ CPU clocked at 2.60 GHz and 8 GB RAM; with Neo4j 5.18.1 running on it. As TBox (OWL ontology) we use the Cognitive Task Ontology (COGITO) [9], which includes about 9000 axioms describing 4700 concepts used for annotating experimental data [10]. For example, the axiom ReadingTask ⊑ (∃has.Read ⊓ ∃has.Language-item) defines a reading task by referring to the Hierarchical Event Descriptors (HEDs) Read and Language-item [11]. COGITO includes axioms that are not in since they use conjunction on the left side (e.g., the converse of the ReadingTask axiom ℰ ℒℋℐ⊥ above). Hence, to make our experimental evaluation more faithful to COGITO, we consider two ontologies: (1) in 1 we drop the axioms with conjunction on the left-hand side, and (2) in 2 we replace these conjunctions by disjunctions. We are currently working on inferring the exact answers over COGITO from these over- and under-approximations. We chose a real-world dataset from the domain of cognitive neuroscience [12], stored in a Neo4j database and consisting of 15 512 nodes and 78 113 relationships. For our experiments, we manually created 8 queries, structurally similar to those in [12], and applied our rewriting technique. The rewritten queries were evaluated using Cypher.1 We report our results in Table 1.
We presented an algorithm for rewriting NCQs into UC2RPQs over a lightweight ontology that extends DL-Lite with some of the expressive features of ℰ ℒℋ while keeping the data complexity of reasoning in NL. One of our goals is to make progress towards a practicable algorithm, and our prototype implementation, which rewrites the queries into Cypher, suggests that we may be on track. It shows promising results on a real-world dataset from cognitive neuroscience.
This work was partially supported by the Federal State of Salzburg under grant number 20102F2101143-FPR (Digital Neuroscience Initiative) and the Austrian Federal Ministry of Education, Science and Research (BMBWF) under grant number 2920 (Austrian NeuroCloud). This work was also partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. 1The selected queries happen to be insensitive to the trail semantics (implemented in Cypher) vs. the walk semantics. [6] N. Dragovic, Querying Property Graphs with Ontologies, Master’s thesis, TU Wien, 2022. [7] T. Eiter, M. Ortiz, M. Simkus, T. Tran, G. Xiao, Query rewriting for Horn-SHIQ plus rules, in: J. Hofmann, B. Selman (Eds.), Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, AAAI Press, 2012, pp. 726–733. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4931. [8] N. Dragovic, B. Löhnert, Ontology-mediated querying for property graphs, 2022. URL: https://gitlab.com/ccns/neurocog/neurodataops/anc/software/owl2cypher, accessed: 202405-24. [9] B. Löhnert, B. Engler, F. Hutzler, Cognitive task ontology (COGITO), 2024. URL: https: //gitlab.com/ccns/neurocog/neurodataops/anc/classification/cogito/, accessed: 2024-05-24. [10] R. A. Poldrack, A. Kittur, D. J. Kalar, E. Miller, C. Seppa, Y. Gil, D. S. Parker, F. W. Sabb, R. M.
Bilder, The cognitive atlas: Toward a knowledge foundation for cognitive neuroscience, Frontiers Neuroinformatics 5 (2011) 17. doi:10.3389/fninf.2011.00017. [11] K. Robbins, D. Truong, S. Appelhof, A. Delorme, S. Makeig, Capturing the nature of events and event context using hierarchical event descriptors (hed), NeuroImage 245 (2021) 118766. [12] A. Ravenschlag, M. Denissen, B. Löhnert, M. Pawlik, N. A. Himmelstoß, F. Hutzler, Efective queries for mega-analysis in cognitive neuroscience, in: G. Fletcher, V. Kantere (Eds.), Proceedings of the Workshops of the EDBT/ICDT 2023 Joint Conference, Ioannina, Greece, March, 28, 2023, volume 3379 of CEUR Workshop Proceedings, CEUR-WS.org, 2023. URL: https://ceur-ws.org/Vol-3379/CoMoNoS_2023_id252_Mateusz_Pawlik.pdf.