OTTR is a template language for the Semantic Web data and knowledge representation languages RDF and OWL. OTTR sees use as a key technology in the Semantic Web systems and already gained popularity both in academia and industry. OTTR is also in active development, which is, however, limited by the fact that little is known about its theoretical aspects. In this extended abstract we begin to close this gap by laying the foundations of OTTR. To this end, we first introduce a mathematical formalisation of the language in terms of its syntax and semantics. Then, we report bounds for the size of OTTR expansion-that is, of the data encoded by templates. Finally, we overview our study of the data and combined complexity of an important decision problem associated with the language and its fragments.
set of template instances which may use template parameters as arguments. Base templates are used to directly represent structures in the base language (e.g., RDF). A set of instances can be translated to the base language by means of (template) expansion, which recursively replaces instances with their corresponding template replicas until only instances of base templates are left. To have a feeling for OTTR, let us consider a dataset with two templates, with names ex:Person and o-rdf:Type, taking two parameters each: ex:Person[?person, ?name] :: {
o-rdf:Type(?person, foaf:Person), ottr:Triple(?person, foaf:name, ?name) } .
o-rdf:Type[?instance, ?class] :: { ottr:Triple(?instance, rdf:type, ?class) } .
Note that ex:Person relies on o-rdf:Type and another template, ottr:Triple, which is a base template whose instances represent RDF triples. The dataset also has an instance ex:Person(:Bob, "Bobby Jackson"), which expands in two steps to two RDF triples: (:Bob, rdf:type, foaf:Person) and (:Bob, foaf:name, "Bobby Jackson"). This example illustrates only the basic OTTR functionality. However, OTTR has more advanced features, including special treatment for possibly nested lists and sophisticated list expansion, which we illustrate later.
An OTTR specification, as well as its serialisation formats, are available as technical reports [
While OTTR has been gaining in popularity, its development is limited by the fact that it lacks a mathematical formalisation and that little is known about its theoretical properties. In this extended abstract, we report that we begin to close this gap and lay down the foundations of OTTR. In particular, we first introduce a mathematical formalisation of a core of the OTTR language, including its key advanced features, thus enabling its formal studies; we then report several upper bounds on the size of the result of OTTR expansion, giving an indication of how concisely OTTR can encode ontologies; ifnally, we overview our study combined and data computational complexity of OTTR expansion and establish fine-grained borders between OTTR fragments, separating those that can be easily evaluated from those that are more dificult.
The key features covered in our formalisation are optional parameters, default values, and list expansion
modes (the latter of which is the most interesting and demanding from the theoretical point of view), and
we introduce them in this section by means of examples. Note, however, that OTTR specifications [
We begin with our first two features. As illustrated by the following example, parameters marked as optional with symbol ? allow a special term none to be used as an argument for these parameters. Meanwhile, for non-optional parameters, if none is given as an argument in some instance, then the entire instance is ignored during expansion. A parameter may also have a default value, specified as a predefined constant. When none is given as an argument for a parameter with a default value, it is replaced by the default value.
For example, we can extend the ex:Person template of the example in the introduction to include information about the email address and the location of the person: ex:Person[?person, ?name, ? ?mail, ?loc=ex:Norway] :: {
o-rdf:Type(?person, foaf:Person), ottr:Triple(?person, foaf:name, ?name), ottr:Triple(?person, foaf:mbox, ?mail), ottr:Triple(?person, foaf:based, ?loc) } .
Since parameter ?mail is marked by (another) ? as optional, we may give none as the corresponding argument. In that case, all occurrences of ?mail are replaced with none in the ex:Person template during its expansion. However, since the ottr:Triple template is non-optional for all parameters, the second instance of ottr:Triple would be ignored. Next, since ?location has a default value, we can also give none as the corresponding argument. In this case, ?location uses its default value instead. So, overall, expanding the instance ex:Person(:Bob, "Bobby Jackson", none, none) results in the triple (:Bob, foaf:based, ex:Norway), in addition to the two triples generated in the original example.
We move on to the third key feature, list expansions, which is used to access the elements of list terms. There are three expansion modes: cross, zipMin, and zipMax. Instances can be specified as having one of these modes, indicating special treatment for list arguments during expansion. Only arguments marked with ++ are afected, while unmarked arguments are treated as normal, even if they are lists. An error is raised if a non-list argument is marked with ++. For all three expansion modes, new instances are created during expansion, with the elements of the lists replacing the lists themselves as instance arguments. In particular, cross combines the list elements via the Cartesian product of the input lists, while zipMin and zipMax combines elements that have the same position in the input lists. The diference between the latter two is that zipMin combines elements up the length of the shortest list, while zipMax pads shorter lists with none up to the length of the longest list.
For example, given two lists of people (:Bob, :John, :Jane) and (:Stephanie, :Ross) we can specify which people in the first list knows the people in the second list. If each person in the first list knows everyone in the second list, then we can use expansion mode cross: ex:Knows[?knowers, ?knowees] :: {
cross | ottr:Triple(++ ?knowers, foaf:knows, ++ ?knowees) } .
Then, expanding the instance ex:Knows((:Bob, :John, :Jane), (:Steph, :Ross)) results in the six triples with all possible combinations of list elements, from (:Bob, foaf:knows, :Steph) to (:Jane, foaf:knows, :Ross). If instead the knowing-relation corresponds with position in the two lists (i.e., :Bob knows :Steph, :John knows :Ross, etc.), then we can use zipping modes zipMin or zipMax instead of cross. For example, replacing cross with zipMin results in the two triples (:Bob, foaf:knows, :Steph) and (:John, foaf:knows, :Ross). Since position of person :Jane exceeds the length of the shorter list, this element is simply ignored with zipMin. Replacing zipMin with zipMax and expanding the same instance results in the additional intermediate instance ottr:Triple(:Jane, foaf:knows, none), which is, however, ignored since the third parameter of ottr:Triple is non-optional, resulting in the same triples as for zipMin.
Finally, we bring attention to the fact that lists inside templates may have variables as elements, as in, for example, (:Bob, :John, ?person, :Jane). This is a way to construct new terms during expansion, which has a significant impact on the expressivity and complexity or OTTR.
We first report several upper bounds for the size of expansion with respect to the size of datasets, which gives us an indication of the conciseness of OTTR. We established a general bound for full OTTR, as well as bounds for two of its important fragments: a fragment without list expansion and a fragment where all lists are ground (i.e., variable-free). In particular, the size of expansion is bounded exponentially by both template nesting depth and by maximal template arity. If no list expansion is allowed, then only template nesting is in the exponent (in fact, only cross mode is essential); if all lists are ground, then only template arity is in the exponent.
We next report our studies of the computational (combined) complexity of a central decision problem associated with the expansion process, namely, the problem Expansion of determining whether a given instance occurs in the expansion of a given error-free OTTR dataset. Studying Expansion helps us understand how dificult it is to retrieve the data stored in OTTR datasets. We consider Expansion for diferent syntactic fragments of OTTR, which allows us to separate the types of datasets which are easy to expand from the ones that are more dificult. In particular, we established a fine border, separating fragments of OTTR for which the combined complexity of Expansion is NP-complete and for which it is NL-complete. It is worth to note that the former includes the full OTTR, while the latter includes essentially the simplest possible fragment.
Finally, we report our results on data complexity of Expansion. In this setting, we assume that the templates of an OTTR dataset are ‘fixed,’ and only the instances of the dataset are considered to form the input. This gives a more practical view of the complexity of Expansion, because the number of templates is usually rather small, while the number of instances may be arbitrarily big. In this case, all relevant OTTR fragments fall into two complexity classes, TC0-complete (under AC0 reductions) and AC0, and the separating property is the presence of lists and expansion modes zipMin or zipMax.
In this extended abstract we report our results on the foundations of OTTR. This is just the beginning of OTTR formal studies, which opens up many further research avenues: we plan to formalise remaining OTTR features, including types, look at DL ontologies produced by OTTR, and study OTTR under a generalisation of OBDA. We also plan to investigate how our algorithms can be used to improve the eficiency of real-life OTTR systems, such as Lutra. [15] B. Krieg-Brückner, T. Mossakowski, Generic Ontologies and Generic Ontology Design Patterns, in: Workshop on Ontology Design and Patterns, 2017. [16] L. Iannone, A. L. Rector, R. Stevens, Embedding Knowledge Patterns into OWL, in: Extended
Semantic Web Conference (ESWC), 2009, pp. 218–232. [17] M. Lefrançois, A. Zimmermann, N. Bakerally, A SPARQL Extension for Generating RDF from
Heterogeneous Formats, in: Extended Semantic Web Conference (ESWC), 2017. [18] P. Lord, The Semantic Web takes Wing: Programming Ontologies with Tawny-OWL, in: International Workshop on OWL: Experiences and Directions (OWLED), 2013. [19] L. H. Karlsen, M. G. Skjaeveland, Adapting Reasonable Ontology Templates to RDF (rOTTR), Technical Report, 2019.