The ontology-based data access (OBDA) paradigm has successfully grown over the last decade as a powerful means to access data from possibly diverse and incomplete sources, using a domain ontology as a mediator. The ability to query generic graph-structured data is often highlighted as an advantage of OBDA, but in practice, existing solutions do not allow to access data in popular graph database management systems (DBMS) (e.g., Neo4j) that adopt the so-called 'property graph' data model and support dedicated query languages such as Cypher. Towards overcoming this major limitation, we propose a technique for ontology-mediated querying (OMQ) of property graphs. We tailor a suitable query language that supports path navigation in a form that can be naturally expressed in Cypher and other important graph query languages. It keeps the data complexity of query evaluation tractable even under trail semantics and is suficient for our motivating use case in the autonomous driving domain. We address the semantic gap between the traditional path semantics adopted by most works on graph databases, and the trail semantics used in Cypher, and identify cases where both semantics coincide. To our knowledge, OMQs with trail semantics had not been addressed before. We develop a rewriting algorithm for queries mediated by DL-Lite ontologies that enables query answering using plain Cypher. The experimental evaluation of our proof-of-concept prototype on a sample set of use case queries reveals that the approach is promising, and can be a stepping stone to making OBDA applicable to data stored in graph DBMS.
The ontology-based data access (OBDA) paradigm, also known as virtual knowledge graphs
(VKGs), has steadily grown over the last decade to establish itself as a powerful way to access
data from possibly diverse and incomplete sources. It has been successfully exploited in various
application domains [
The ability to integrate heterogeneous sources and query generic graph data is often
highlighted as an advantage of the OBDA paradigm, and while it can be successfully deployed to
query RDF graphs, no solutions so far allow directly querying data stored in popular graph
DBMS (GDBMS) that adopt the so-called property graph data model. This is a major limitation
since such graph databases have gained huge popularity this century in scores of domains
and they are widely deployed in practice. GDBMS support dedicated query languages for
graph-structured data. For example, Neo4j is one of the most popular GDBMS nowadays, and
its query language is Cypher [
The fundamental feature of all query languages for GDBMS is the presence of navigational
features for traversing paths flexibly [
Typically, OBDA systems take as input a so-called conjunctive query (CQ), which is essentially
the most widely used select-project-join fragment of relational algebra; in its logical form, it is
written as a positive existential conjunction of atoms that may share join variables [
The main goal of this paper is to provide such a rewriting approach for OMQs with OWL 2
QL ontologies, but using a graph query language that is supported by GDBMs, such as Cypher,
as both source query language, and as target for the rewriting. Navigational features have
been considered in the OMQ literature, where algorithms for rewriting navigational queries
in the presence of ontologies and tight complexity bounds for their evaluation are known
[11, 12], but the existing theory results have never made it to practice. These works consider
conjunctive 2-way regular path queries (C2RPQ), the generalisation of CQs with path navigation,
the language of choice for theoretical works on accessing graph databases. However, it is
well-known that practical graph GDBMS do not always support C2RPQs, and sometimes adopt
a diferent semantics. In particular, unlike C2RPQs, Cypher uses a trail semantics where no
edge of the graph can occur twice on a path, and imposes restrictions on the bidirectional
navigation of paths [
The main contributions of this paper can be summarised as follows: 1. We propose a class of queries that allows for path navigation in property graphs which is suficient for our motivating use case. Our query language is closely related to C2RPQs, but tailored to be expressible in Cypher, to support succinct query rewritings, and to have tractable data complexity even under trail semantics. 2. We consider both the traditional path semantics of C2RPQs and the trail semantics of Cypher; to our knowledge, OMQs with trail semantics had not been considered until now.
We show that for our query language, query answers under both semantics coincide. 3. We present a rewriting algorithm for our query language in the presence of OWL 2 QL ontologies. We provide conditions that guarantee that the queries rewritten by the algorithm can be expressed in Cypher, and evaluated directly over GDBMS. 4. We implemented a simple prototype of the approach and evaluated it on real-world use-case data. In particular, we considered queries designed for scenario-based safety assessment for autonomous vehicles and evaluated them over an industrial dataset. We obtained promising results that suggest that our work may be a stepping stone towards practicable OBDA over GDBMS.
In this section we recall the property graph data model. We also introduce DL-LiteR, which is the language of OWL 2 QL defined as a description logic [13].
We consider a vocabulary consisting of countably infinite and pairwise disjoint sets NI of individual names, NC of concept names and NR of role names, NE of relationship names and K of property keys. Moreover, we assume a fixed set of data type domains D1, . . . , D; each D consists of a value domain and a fixed set of binary predicates representing binary relations over . In our examples, we typically use integers and strings as data types. For integers, we use the usual comparison predicates ≤ , ≥ , ̸=, =, and for the strings datatype we use the binary relations equal (1, 2), substring (1, 2), and prefix(1, 2).
Property Graphs
Our definition of property graphs follows the one given in [
Let = ⟨, , src, tgt, , , ⟩ and ′ = ⟨ ′, ′, src′, tgt′, ′, ′, ′⟩ be property graphs.
each ∈ to some ℎ() ∈ ′ so that 1. for every ∈ , () ⊆ ′(ℎ()) and if (, ) is defined for some , then (, ) = ′(ℎ(), ); and 2. for every ∈ , () = ′(ℎ()), src() = src′(ℎ()), tgt() = tgt′(ℎ()), and if (, ) is defined for some , then ′(ℎ(), ) = (, ).
An ontology is a set of axioms that encapsulates terminological knowledge of our domain.
Here we write ontologies in the description logic called DL-LiteR [
1 ⊑ 2, 1 ⊑ ¬2, 1 ⊑ 2, 1 ⊑ ¬2.
property graphs that may extend and satisfy the axioms in .
⟨Δℐ , Δℐ, src, tgt, , , ⟩ where Δℐ ̸= ∅ and Δℐ ̸= ∅. We say that ℐ is a model of dataset if it contains as a subgraph. Note that we are thus making the standard name assumption.
ℐ ={ ∈ Δℐ | ∈ ()} ℐ ={(, ) | ∃ ∈ Δℐ : src() = , tgt() = , () = } Then the interpretation of all concepts and roles is defined as usual: (¬)ℐ = Δℐ ∖ ℐ (∃)ℐ = { | ∃ ∈ Δℐ : (, ) ∈ ℐ } (− )ℐ = {(, ) | (, ) ∈ ℐ } (¬)ℐ = (Δℐ × Δℐ ) ∖ ℐ
Canonical model When TBoxes are written in DL-LiteR, every consistent dataset can be extended into a model in a canonical way using a technique called the chase; this also applies in our setting. As usual, we start form and add nodes, edges and labels to satisfy all the positive axioms of , i.e., those that do not have ¬ on the right-hand-side.
First we set ℐ0 = . Then the following rules are exhaustively applied: • If ⊑ ∈ with ∈ NC, ∈ ℐ and ̸∈ ℐ , then ℐ+1 is obtained from ℐ by setting () := () ∪ {}. • If ⊑ ∃ ∈ , ∈ ℐ and ̸∈ (∃)ℐ , then ℐ+1 is obtained from ℐ by adding a fresh to Δℐ and a fresh to Δℐ . In case ∈ NR, we set src() := , tgt() := and () = for ℐ+1. Otherwise, we set src() := , tgt() := and () = − . • If 1 ⊑ ∈ with ∈ N±R , (, ) ∈ ℐ and (, ) ̸∈ ℐ , then ℐ+1 is obtained from ℐ 1 by adding a fresh element to Δℐ . In case ∈ NR, we set src() := , tgt() := and () = for ℐ+1. Otherwise, we set src() := , tgt() := and () = − . We assume fairness in the application of the rules i.e., every applicable rule is eventually applied.
general, the canonical model can be infinite. The following result is proved in the standard way. Lemma 1. Let be a DL-LiteR TBox and a dataset consistent with . Then ℐ , is a model of and , and every model of and can be homomorphically embedded into ℐ ,.
We now introduce our query language for property graphs, which allows for path navigation in the style of C2RPQs. For a detailed definition C2RPQs, we refer to [ 12]. C2RPQs are conjunctions of unary atoms of the form () and binary atoms of the form (, ), where is a concept name and a regular expression over the alphabet of (possibly inverse) roles. Cypher also supports regular paths, but when we restrict it to the fragment that can be written in logic as a conjunction of atoms analogous to C2RPQs, we find some important diferences. In particular, Cypher imposes directionality constraints when matching paths that efectively mean that a regular path that uses the Kleene star can contain either only role names, or only inverse role names. For example, a query such as () ← [1 ∪ 2− ]* (, ) can not be syntactically expressed in Cypher. Also, Cypher does not allow more than one ‘step’ in the scope of the Kleene star, thus a query such as () ← [1 · 2]* (, ) can not be syntactically expressed in Cypher.
Our query language restricts regular paths so that they are naturally expressible in Cypher. We also add some useful features to CQs that are typically not present in C2RPQs, but which are easy to support in Cypher. We extend unary atoms to take a disjunction of concepts rather than a single concept. As we will see below, this allows for rewritings that are exponentially more succinct in some cases. Additionally, our query language allows querying property values by means of test atoms. Recall that each datatype has a fixed set of binary predicates representing binary relations over the data domain. For example, the integers may come with the usual comparison predicates ≤ , ≥ , ̸=, =, and the strings datatype with binary relations equal, substring, prefix, etc. Property keys and data predicates are used in Boolean tests: x_position ≥ 450 ∨ (x_position ≥ 300 ∧ movingDirection = ‘right′). where we check that an object has a horizontal position of at least 450, or the position is at least 300 and the object is moving in the direction right.
Definition 1 (Navigational property-graph queries (NPGQs)). Let be a value in a datatype domain D, let ⊙ be a binary predicate in D, and let ∈ K. The expression ⊙ is called an atomic data test, and a Boolean combination of atomic data tests (built using ∧, ∨, and ¬) is called a data test. We define a navigational property-graph query (NPGQ) as an expression of the form (⃗) = ∃.(⃗, ⃗) where is a conjunction of atoms of the forms: () (, ) (1 ∪ · · · ∪ )() (1 ∪ · · · ∪ )(, ) (1 ∪ · · · ∪ )* (, ) where each is a concept name in NC, each a role name in N±R , is a data test, and , ∈ (⃗ ∪ ⃗ ∪ NI). The atoms of the first two forms are called test atoms, and the remaining atoms are relational atoms. We call an atom of the last form a star atom, and say that it is pure if it contains only role names, or only inverse role names, that is, if either {1, . . . , } ⊆ or {1− , . . . , − } ⊆ . An NPGQ is called pure if all its star atoms are pure.
To define the semantics of NPGQs, we first define paths and trails.
Definition 2. Consider a property graph = ⟨, , src, tgt, , , ⟩. We let ± = ∪ {− | ∈ }, and for every in ± , we let src(− ) = tgt(), tgt(− ) = src() and (− ) is the inverse role of (). A path from a node to a node in a property graph is a sequence 12 . . . of edges ∈ ± , where src(1) = , tgt() = and for each 1 ≤ < ,tgt() = src(+1). We use to denote the empty path, that is, the path with = 0 from a node to itself. A trail from to is a path 12 . . . from to where for each ̸= , we have that ̸∈ { , − } i.e., no edge occurs more than once. For of the form (1 ∪ · · · ∪ )* or (1 ∪ · · · ∪ ), we use ( ) to denote the set of paths 12 . . . such that {1, . . . , } ⊆ { 1 ∪ · · · ∪ }, where = (). Note that ∈ ( ) for every .
Note that every trail is a path, but not every path is a trail. Now we can define path and trail matches for NPGQs.
Definition 3. [Path and trail matches] Consider a property graph = ⟨, , src, tgt, , , ⟩. Let ∈ ∪ . A test ⊙ is said to be true at if (, ) is defined and belongs to the same data domain D as , and the relation denoted by ⊙ holds between (, ) and . The truth of data tests is interpreted as expected, and we write ∈ J K if is true at in graph ; we may omit the graph if it is clear from the context.
Let (⃗) be a query and a mapping from the individuals and variables occurring in to nodes of . We call a path match for in if contains all individuals occurring as terms in and: 1. () = for each ∈ NI; 2. for each atom (1 ∪ · · · ∪ )() in , {1, . . . , } ∩ ( ()) ̸= ∅; 3. for each atom () in , () ∈ J K; 4. for each atom (1 ∪ · · · ∪ )(, ) or (1 ∪ · · · ∪ )* (, ), there exists a path ∈ ( ) from () to (), where = 1 ∪ · · · ∪ or = (1 ∪ · · · ∪ )* , respectively; and 5. for each atom (, ), there exists ∈ with ∈ J K, () = (), () = (). If additionally the path in item 4 is a trail, we call a trail match. A tuple ⃗ ⊆ is a (trail) answer to a query (⃗) = ∃.(, ) in if there exists a (trail) match for ⃗ such that (⃗) = ⃗.
Since all trails are paths, the trail answers are a subset of the path answers. For C2RPQs and
many related languages, this containment is strict [
Proposition 1. Let be a property graph and an NPGQ. The answers to over under trail semantics are also path answers.
Proof (sketch). We show that every path match is also a trail match. Consider an arbitrary path match for in . To show that is also a trail match, we argue that for every star atom (1 ∪ 2 ∪ · · · ∪ )* (, ), there is a trail ′ witnessing item 4 in Definition 3, that is, ′ is a trail from () to () and ′ ∈ ( ), where = (1 ∪ 2 ∪ · · · ∪ )* . We know that such a path = 1 . . . exists, as is a path match, and if is not a trail then we can drop any repeated sequences in it to obtain a trail ′. Since ′ only uses edges from {1, . . . , }, it follows from = ( ) that ′ = ( ) also holds.
Answering C2RPQs under path semantics is in NL in data complexity [14], so by Proposition 1 we have: Proposition 2. The query answering problem for NPGQs is NL complete in data complexity, under both path and trail semantics.
This is good news, since under trail semantics C2RPQs are intractable in general [15]. We note that Proposition 2 can also be inferred (without Proposition 1) from the trichotomy in [15].
NPGQs inherit Cypher’s restrictions on directional navigation and they can be easily expressed. Due to space constraints, the Cypher translation is to be found in the full version of this paper.
As is usually done for OMQs, we adopt the certain answer semantics.
Definition 4 (Certain answer). Let be a dataset, a TBox, and (⃗) an NPGQ. A tuple ⃗ ⊆ is a (certain) answer to ((⃗), ) over if it is an answer in each model ℐ of and .
Note that previous works on OMQs had only considered path answers, which admit a natural certain answer semantics. We can adopt certain answers for the trail semantics thanks to Proposition 1, but this does not extend to other navigational query languages.
from Lemma 1, the preservation of path matches under homomorphisms, and Proposition 1. Lemma 2. Let be a dataset, a TBox, and (⃗) an NPGQ. A tuple ⃗ ⊆ is a (certain) answer to ((⃗), ) over if it is an answer in in the canonical model ℐ ,.
In this section, we a present a sound and complete rewriting algorithm for NPGQs. It transforms an NPGQ mediated by a DL-LiteR ontology into a plain NPGQ that can be evaluated over the data alone and that gives exactly the same set of answers.
right-to-left fashion to take into account every way in which a query atom could be implied. Since NPGQs allow for unions of concepts in unary atoms, we can avoid one of the most common causes for exponential growth of the rewritten queries in PerfectRef. For instance, in the presence of a TBox that contains 1 ⊑ 2, 1 ⊑ 2 a query that contains the atoms 2(), 2() can be rewritten replacing them with (1 ∪ 2)(), (1 ∪ 2)(), rather than considering all combinations of (), ().
For the treatment of the regular expressions, we exploit the fact that the query only needs to navigate in the anonymous part of the canonical model in one direction. That is, for every atom (, ) in and every match , we can safely assume that is a trail and no node in the canonical model is visited more than once. This ‘unidirectionality’ of paths spares us from needing the sophisticated techniques for treating 2-way paths that are usual for navigational queries in the presence of ontologies (e.g., the so-called loop computation [12]). Instead, we only introduce three novel rewriting rules, which allow us to reason about the way in which the paths witnessing star atoms may overlap, and whose application can be a prerequisite to the application of the usual rewriting rules to the star atoms.
Let be an atom. If it is of the form (1 ∪ 2 ∪ . . . )(), we denote by concepts( ) the set of all concept names {1, . . . , } that occur in it, and if it is of the form (1 ∪ 2 ∪ . . . )(, ), then roles( ) ⊆ ± denote the roles occurring in it. For a union of roles = 1 ∪ · · · ∪ , we define − = 1− ∪ · · · ∪ − . We view queries as sets of atoms and, for convenience, we use ∈ to mean that either ∈ , or = (, ) and − (, ) ∈ . Recall that a query variable is unbound if it occurs exactly once in the query and it is not an answer variable. As usual, we denote unbound variables by ‘_’, but each occurrence is a fresh variable, and must be denoted by a unique name if it becomes bound.
For a TBox , we call ⊆ ± -saturated if 1 ∈ whenever 2 ∈ and either 1 ⊑ 2 ∈ or 1− ⊑ 2− ∈ . The -saturation of , sat (), is the smallest -saturated set containing . Similarly, a set of concept names -saturated if ∈ and ′ ⊑ ∈ imply ′ ∈ , and the -saturation of , denoted sat ( ), is the smallest -saturated set containing . We call an atom -saturated if concepts ( ) or roles ( ) (for unary or binary , respectively) is -saturated. If it is clear from the context, we may omit and just talk about saturated atoms.
Our novel query rewriting algorithm, applies exhaustively the following transformations. Definition 5. Consider a DL-LiteR TBox and an NPGQ . We define the following rules: 1. Saturation: saturate (, ) denotes the result of replacing each atom in by its -saturation. 2. Axiom application: By apply (, ) we denote the result of applying an axiom to using the rules in Table 1. Note that this may add an unbound variable to the query. 3. Reduction: reduce(, 1, 2) is the result of applying the most general unifier of 1 and 2. 4. Concatenation: Let 1 ∈ and 2 ∈ be atoms such that roles ( 2) ⊆ roles ( 1), 1 is a star atom, and 1, 2 share a common term. Then we obtain concatenate(, 1, 2) as follows: If 1 has terms (, ) and 2 has terms (, ), then the terms of 1 in are replaced by (, ). This amounts to placing the atom 2 right before 1. If 1 has terms (, ) and 2 has terms (, ), then the terms of 1 in are replaced by (, ). This amounts to placing the atom 2 right after 1. 5. Merging: Let 1 ∈ and 2 ∈ be atoms with roles ( 1) ∩ roles ( 2) ̸= ∅ and such that both atoms have terms (, ) (in that order). Then merge(, 1, 2) is obtained by replacing in both atoms by • [roles ( 1) ∩ roles ( 2)* ](, ) if both 1 and 2 are star atoms, and • [roles ( 1) ∩ roles ( 2)](, ) otherwise. 6. Dropping: Let ∈ be of the form (1 ∪ · · · ∪ )* (, _) or (1 ∪ · · · ∪ )* (_, ) and such that occurs in another atom in case it is an answer variable. Then drop(, ) = ∖ . We use Rewrite (, ) to describe the set of queries that are produced by applying all of the above rules exhaustively, and accumulating all transformed new queries.
Example 1. Suppose we are given a TBox = {∃− ⊑ ∃} and also a query 1, defined as 1() ← ( ∪ ∪ )* (, ), (, ), − (, ). To illustrate the query transformations, we state three example queries, produced via successive application of these transformations. 2() ← 3() ← 4() ← ( ∪ ∪ )* (, ), − (, ), − (, ) ( ∪ ∪ )* (, ), (, ), − (, ) (, ), (, ) from apply (1, ∃− ⊑ ∃) from concatenate(2, ( ∪ ∪ )* (, ), (, )) from merge(3, (, ), ( ∪ ∪ )* (, )) Note that in the creation of 3 we make use of the fact that (, ) ∈ 2, which follows from − (, ) ∈ 2, and analogously we have that (, ) ∈ 3, which follows from − (, ) ∈ 3.
Note that the rewriting focuses on the atoms without data tests. Since DL-LiteR ontologies cannot assert property key values for existentially quantified objects, atoms with data tests can only be matched in the canonical model to nodes and edges that exist already in the input dataset. Hence these atoms remain untouched in the rewritten query, except for possible applications of the reduce step, which could bind variables shared with test atoms.
The rewriting algorithm we have presented is sound and complete.
Theorem 1. Let be an NPGQ, a DL-LiteR TBox and a property graph. Then ⃗ is a certain answer to over ( , ) if ⃗ is an answer to ′ in for some ′ ∈ Rewrite(, ).
The pseudo-code of the query rewriting algorithm will be in the full version of this paper. Termination and Complexity The query rewriting procedure terminates. In a nutshell, all transformations make the query smaller except for the axiom application, which can introduce fresh variables, but a bound on the latter can be shown using essentially the same arguments as for the standard PerfectRef. The rewriting does not depend on the data and hence it only needs constant time for any given and . From this and Proposition 2, we get: Theorem 2. The query answering problem for NPGQs mediated by DL-LiteR ontologies is NL complete in data complexity, under both path and trail semantics.
Evaluating OMQs in Cypher Even if the original input query is pure, the rewriting can add (non)-inverse roles to star atoms and result in a NPGQ that is not pure. We introduce a suficient condition for the purity to be preserved during the rewriting, which guarantees that we can evaluate ontology-mediated NPGQs using Cypher.
Definition 6 (NPGQ compliance). Let be an NPGQ. A TBox is -compliant if there is no star atom whose saturation contains both role names and inverse role names. That is, for every atom of the form * (, ′) ∈ , either sat () ⊆ , or {− | ∈ sat ()} ⊆ .
Proposition 3. If is a pure NPGQ and it is -compliant, then every ′ ∈ Rewrite(, ) is a pure NPGQ.
This work was largely motivated by a use case from the automated driving industry, specifically scenario-based safety assessment models for autonomous vehicles, where driving scenarios for safety testing are retrieved from real-world data. There are two large open datasets used for such purposes: the nuScenes [16] and Lyft [17] datasets. A company in the autonomous driving industry stores both datasets in the same Neo4j graph database. The data is organized in scenes, which contain a number of samples that are temporally ordered, and the state of objects in a scene can change within an unknown time frame. Hence, we need to navigate the temporal graph of a scene to answer queries about objects that change in time. The two datasets are similar, but use diferent vocabularies. For example, one dataset labels instances with Bus, while the other labels them either RigidBus or BendyBus. We used a DL-LiteR ontology to define a unified vocabulary for querying. It contains, for example, axioms such as BendyBus ⊑ Bus and
ifve representative queries. All but one of them needed navigation along paths of unbounded length, but could be easily expressed as NPGQs. The navigation used only temporal relations in the data such as NEXT, and the compliance between queries and TBox was trivial. The queries vary from a simple query with only one atom (Q1) to queries which contain binary atoms with Kleene star (Q2-Q4). As an example, we provide one of the queries, Q5, here in full: 5() ← pedestrian(), OF(, ), HAS(, ), pedestrian_stationary(), NEXT(, ),
NEXT* (, ), HAS(, ), pedestrian_moving()
We developed a prototype implementation of our rewriting technique and tested it on a sample dataset provided by the mentioned company, as a Neo4j database with metadata of the nuScenes and Lyft datasets. The source code for our implementation has been made publicly available1. The dataset consists of 91,891 nodes and 254,555 distinct relations. In order to test the potential feasibility of our approach, we rewrote the five queries and evaluated them over the data as Cypher queries. The results of the evaluation are seen in Table 2, on the right.
We were also curious about the impact of atoms with concept unions (such as [ ∪ ]()) for handling the subclass hierarchy. We compared our rewriting, which uses this union, with a naive version that just extends the classical PerfectRef with the additional rules for navigational atoms (called PerfectRef* in the table). The sizes of the rewritings produced by both approaches and their evaluation time are shown in Table 2. The very significant improvements suggest that some features of Cypher may be useful for query rewriting even for plain CQs, and they could be leveraged for more eficient OMQ evaluation with less optimisation efort.
Ontologies are useful for querying incomplete data. We have extended the ontology-mediated querying paradigm to property graphs, using as both input query language and as target of the rewritings a navigational query language which is expressible in Cypher. For answering queries, we have developed a novel rewriting algorithm based on PerfectRef. Finally, we have demonstrated the usefulness of exploiting Cypher for compact rewritings on a concrete use case. We plan to continue working on rewriting techniques for more expressive graph query languages, helping pave the way to enabling OBDA to support real graph databases.
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. It was also partially supported by the Austrian Science Fund (FWF) project P30360 and P30873. [11] M. Bienvenu, D. Calvanese, M. Ortiz, M. Simkus, Nested regular path queries in description logics, in: KR, AAAI Press, 2014. [12] M. Bienvenu, M. Ortiz, M. Simkus, Regular path queries in lightweight description logics:
Complexity and algorithms, J. Artif. Intell. Res. 53 (2015) 315–374. [13] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge
University Press, 2017. [14] M. P. Consens, A. O. Mendelzon, Graphlog: a visual formalism for real life recursion, in:
PODS, ACM Press, 1990, pp. 404–416. [15] W. Martens, M. Niewerth, T. Trautner, A Trichotomy for Regular Trail Queries, in: C. Paul, M. Bläser (Eds.), 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 7:1–7:16. URL: https://doi.org/10. 4230/LIPIcs.STACS.2020.7. doi:10.4230/LIPIcs.STACS.2020.7. [16] H. Caesar, V. Bankiti, A. H. Lang, S. Vora, V. E. Liong, Q. Xu, A. Krishnan, Y. Pan, G. Baldan, O. Beijbom, nuscenes: A multimodal dataset for autonomous driving, in: 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, Computer Vision Foundation / IEEE, 2020, pp. 11618–11628. URL: https://openaccess.thecvf.com/content_CVPR_2020/html/Caesar_ nuScenes_A_Multimodal_Dataset_for_Autonomous_Driving_CVPR_2020_paper.html. doi:10.1109/CVPR42600.2020.01164. [17] J. Houston, G. Zuidhof, L. Bergamini, Y. Ye, L. Chen, A. Jain, S. Omari, V. Iglovikov, P. Ondruska, One thousand and one hours: Self-driving motion prediction dataset, in: J. Kober, F. Ramos, C. J. Tomlin (Eds.), 4th Conference on Robot Learning, CoRL 2020, 16-18 November 2020, Virtual Event / Cambridge, MA, USA, volume 155 of Proceedings of Machine Learning Research, PMLR, 2020, pp. 409–418. URL: https://proceedings.mlr.press/ v155/houston21a.html.