Ontology-based data access (OBDA) is a well-established paradigm for querying incomplete datasources while taking into account knowledge provided by a domain ontology [PLC+08]. Today, the main applications of OBDA can be found in data integration as well as in querying the Semantic Web. So far, OBDA has been studied for relational structures and deployed on top of relational databases, and then transposed to RDF. The database queries used in OBDA are (unions of) conjunctive relational queries (or basic graph pattern queries), while the ontologies are specified in either a description logic (e.g., the lightweight DL-Lite [CGL+07][KLT+10], or the expressive Horn-SHIQ [EOS+12]), or a rule-based fragment of first-order logic (e.g., Datalog [CGP12] and existential rules [BLMS11]). Decidability and complexity of ontologymediated query answering within this framework have been extensively studied and many algorithms have been designed and implemented.
Whether this paradigm can be used in conjunction with other kinds of query languages is a still an open question. The naive way to deal with non relational datasources is to define mappings for translating them into relational structures, and then use the classic OBDA framework as it is. However, this approach would induce a significant performance degrade as it would add a step for converting the data using the mappings and, most importantly, it would make impossible to take advantage of the low level query optimizations provided by native systems. This can be particularly acute for NOSQL systems, like key-value (KV) stores, that have been specifically designed to scale when dealing with very large collections of data.
Our goal is to study ontology-based data access directly on top of NOSQL systems. The term NOSQL (NotOnly SQL) defines a broad collection of languages. KV stores are NOSQL systems adopting the data model of KV records (also called JSON records). These records are processed on distributed systems, but also increasingly exchanged on the Web thereby replacing semistructured XML data and many RDF formats (see JSON-LD [SLK+04]). KV records are non-first normal forms where values are not only atomic (in contrast with relational databases) and nesting is possible [AHV95].
This extended abstract summarizes our work on OBDA for KV stores [MRU16]. We introduce NO-RL, a rule language to express lightweight ontologies on top of KV records, and provide first (un)decidability and data complexity results for ontologymediated query answering in our setting. The NO-RL rule language operates directly on KV records and can be compared to existing languages designed for reasoning on nested structures like F-Logic [KLW95,Kif05], Elog [BFGK01,BCG+03,GK04] and Active XML [ABM04]. However, up to our knowledge, none of this existing work follows an OBDA approach.
Our first contribution is a formalization of the data model of KV stores (sets of KV records) and the associated basic queries. In this abstract, we will just illustrate these notions by an example. The KV record below contains ten different keys: most of them are associated with atomic values, except phone associated with a record, professor and course associated with sequences (of records and of sequences, respectively) and director associated with an unspecified value null . f name : “Alice”; reachable : “yes”; boss : “Charles” g f name : “Bob”; phone : foffice : “5-256”g; speciality : “Logics”g ] course : [ [“C123”; “Java”] ; [“C310”; “C++”] ] director : null g
KV stores feature a limited set of low-level highly parallelizable queries based on paths, and leave other functionalities (such as joins between records) for the application accessing the data. An example of query retrieving the names of professors is get(professor.name). This expression returns the values “Alice” and “Bob” once evaluated on the example record. Another feature supported by KV stores is the possibility to check structural properties of a record before selecting some content. Thus, we further look at queries with a check() construct like the expression check(director): get(professor.name). The get part of the query is evaluated at the only condition that the key director also exists in the record. The check() construct is particularly useful when dealing with incomplete information expressed by null values, like for the key director in the example. 3
To define rules on KV records, we consider atoms of the form (x), where is a (finite) sequence of keys, called a key-path, and x a variable. NO-RL rules can be of two kinds: 0(x) ! (x) or 0(x) ! 9y (y), as illustrated below: 1. “every phone number is a contact (any value for the key phone is a value for the key contact) ” phone(x) ! contact(x) 2. “if there is a reachable field then there is a phone number” reachable(x) ! 9y: phone(y) 3. “if a professor has a boss, then this last one is a director of the department” professor.boss(x) ! director(x) 4. “the department defines a teaching specialty for all of its professors” department(x) ! professor.specialty(x)
We define three rule fragments: NO-RL(1), composed of rules that employ only key-paths of length one (like Rules 1 and 2 in the example), NO-RL(2) and NO-RL(3), which both extend NO-RL(1) by allowing respectively for rule bodies of arbitrary length (like Rule 3) and for rule heads of arbitrary length (like Rule 4).
The following record is obtained from the previous one by application of the four above rules until fixpoint (process called “saturation”). fname : “Alice”; reachable : “yes”; boss : “Charles”; phone : null; specialty : “CS” g; fname : “Bob”; phone : foffice : “5-256”g;
contact : foffice : “5-256”g; specialty : [“CS”; “Logics”]g ] course : [[“C123”; “Java”]; [“C310”; “C++”]] director : “Charles” g
Rule application inserts a path into the existing record, which requires to merge information (e.g., the application of Rule 4 inserts the path professor.specialty : “CS”). We show that the inference operator associated with rule application is confluent (up to a notion of record equality), hence the order in which rules are applied is irrelevant. Finally, a value is an answer to a query Q over a knowledge base (I; ), where I is a set of records and a set of NO-RL rules, if it is an answer to Q on a record inferred from a record in I by the rules in . 4
Despite the apparent simplicity of the NO-RL language, answering check/get queries under NO-RL rules is generally undecidable (which we prove by reduction from the word problem in a semi-Thue system). Intuitively, this is due to the unrestricted interaction between NO-RL(2) and NO-RL(3) rules. In particular, decidability can be recovered by restricting the rule language to NO-RL(2) or NO-RL(3) only.
A soon as a single NO-RL(3) rule is involved, saturation may be infinite. If we consider NO-RL(2) rules, saturation is always finite since these rules do not increase the depth of records. However, with a single NO-RL(1) rule already, saturation can be exponential in the size of the input record. This observation advocates for query reformulation techniques in the spirit of the OBDA paradigm. We define a sound and complete reformulation technique (i.e., a value is an answer to Q over (I; ) iff if it is an answer to a -reformulation of Q over I). Dually to saturation with NO-RL(2) rules, query reformulation with NO-RL(3) rules is always finite since these rules do not increase the depth of records. It follows that the data complexity of (the decision problem associated with) query answering with NO-RL(3) rules is the same as basic query answering on KV stores, i.e., it is in the low complexity class AC0. Query reformulation can be infinite with NO-RL(2) rules, however, given a record of depth d, only reformulations of depth less or equal to d are useful. There is an exponential number of useful reformulations, nevertheless each of them can be produced with a polynomial number of steps ((d + 1) j j), hence query answering over NO-RL(2) rules is in NP (for both data and combined complexities —the exact lower bounds being open).
Future work includes further clarifying query answering complexity, identifying decidable / tractable cases mixing NO-RL(2) and NO-RL(3) rules, as well as designing algorithms that would exploit the parallelization features of KV stores. Acknowledgments. This work has been partially supported by projects PAGODA (ANR12-JS02-007-01) and Labex PERSYVAL-Lab (ANR-11-LABX-0025-01).