Ontology-Mediated Query Answering for Key-Value Stores

1 Introduction

Ontology-mediated query answering (OMQA) is a paradigm for accessing legacy data while taking into account knowledge expressed by a domain ontology. OMQA has received a lot of attention in the last decade, driven by the increasing importance of data integration [Poggi et al., 2008] and the growing interest in semantic technologies. This paradigm can be seen as a family of techniques for querying a virtual knowledge base composed of factual knowledge (the data) and ontological knowledge. So far, most of the attention on OMQA has been on providing techniques to access factual knowledge held by relational and RDF databases. The ontological knowledge is often expressed using data-tractable description logics [Calvanese et al., 2007; Baader et al., 2008; Eiter et al., 2012] or suitable fragments of existential rules / Datalog± [Baget et al., 2011; Cal`ı et al., 2012].

In data-intensive applications, however, the database to access can be composed of key-value (KV) records in JSON format. This data can be sourced from the Web or produced and then analyzed within an organization. In addition to widespread of JSON as a format for data storage and exchange, the recent development of key-value stores (a family of NOSQL data-management systems) makes possible today to efficiently query JSON records [Cattell, 2010]. These data-management systems feature a set of low-level optimizations tailored for the format, which results in fast and scalable data access without requiring any translation to a relational system, which was one of the prominent solutions to handle semi-structured data [Chasseur et al., 2013].

From an OMQA perspective, a natural question is how to integrate JSON records in the setting and, more precisely, how to design OMQA systems directly on top of KV-stores, thereby exploiting the store's native query engine capabilities. The evaluation of ontological queries over key-value stores has received only little attention so far, with the exceptions of [Mugnier et al., 2016; Botoeva et al., 2016] (see last section).

A prominent family of OMQA techniques adapted to query JSON records are those based on query reformulation 1 . The idea is to reformulate the input query by incorporating the relevant information from the ontology in such a way that the answers to the reformulated query over the input database are exactly the answers to the initial query over the virtual knowledge base. By contrast, the approach of materialization involves the generation of the whole virtual knowledge base. The main advantage of query reformulation is that it leaves the data untouched, which is often a desirable characteristic.

Contributions. We propose a rule language for JSON records that i) allows one to express ontological knowledge in terms of hierarchies of properties, path inclusions, and mandatory paths ii) admits tractable query answering, and iii) enables a query reformulation mechanism implementable over KV-stores. We consider core navigational queries supported by KV-stores, namely get and check queries [Mugnier et al., 2016]. Our setting has a natural first-order logic semantics. This allows us to identify relationships to existing ontology languages, namely existential rules and description logics, which yield decidability of query answering, but only provide rough upper complexity bounds because of the specificities of the shape of JSON records and ontology rules.

A distinctive feature of our language are contextual rules. Because JSON records are tree structures, a given value can assume a different meaning depending on the context (of the record) where it is employed. From an ontology modeling perspective, this means that it is interesting to have available rules with context that apply selectively on the record structure. Nevertheless, we show that this important feature makes the combined complexity of query answering jump from NLogSpace-complete (without contexts) to PSpace-complete

1 We use 'query reformulation' rather than the more common 'query rewriting' to avoid any confusion with 'word rewriting'.

(with contexts). Then, independently from contextual rules, the tree shape of JSON records also impacts the data complexity of query answering, which is PTime-hard if we consider arbitrary data instances but in NLogspace in our setting. While PTime-hard problems are considered as probably inherently sequential, this last result gives us hope that OMQA can be efficiently parallelized.

Finally, we are able to establish an interesting and nontrivial connection with word rewriting systems. This allows us to import and extend existing techniques, thereby deriving tight complexity bounds for query answering. Beside the theoretical interest, these techniques allow us to represent the (possibly infinite) set of reformulations of an input query with a regular expression, which in turn can be evaluated over KVstores by unfolding or using simple auxiliary structures like data-guides.

2 The Framework

We start by formalizing JSON records, core queries, and rules we consider, together with their first-order logic semantics.

JSON records. Let CONST and NULLS be (infinite) sets of constants and (labeled) nulls, respectively, and let KEYS be a finite set of keys. A JSON record, or key-value record, is a finite set of key-value pairs. A value is recursively defined as (i) an element of CONST∪NULLS (i.e., a terminal value), (ii) a sequence [e1 . . . en] where each ei is a value and n ≥ 1, or (iii) a record r of the form {(k1, e1) . . . (kn, en)} where each ki ∈ KEYS and each ei is a value, with n ≥ 1 and ki ̸= kj for i ̸= j. A KV-store I is a set of records. A record can be associated with a rooted labeled tree, in which edges are labeled by keys, leaves are labeled by constant or null values, and all other internal nodes are unlabeled. A key-value pair (k, e) where e is a sequence is represented by several edges labeled by k leading to the nodes that represent the elements of e. 2 To illustrate, consider the following JSON record which describes a teaching department, containing its name, a professor, and two courses.

{ dept : { name : "CS", prof : {name : "Bob" , boss : "Alice", phone : "5-256" } , course : ["AI", "Logic"] } }

The tree associated with this record is depicted in Figure 1. From now on, a record will be identified with its associated tree. Hence a path in a record is a path in the associated tree, which is defined as usual. A path (v0 . . . vn) is rooted if v0 is the root of the tree. It is valued if vn is a leaf labeled by a constant. Its associated sequence of keys is K = k1 . . . kn where ki is the label of the edge (vi-1, vi). For convenience, we will sometimes denote a path by v0Kvn (emphasizing the associated sequence of keys) and, when the path is valued, replace vn by its label, e.g. v0Kc where c ∈ CONST. We denote by paths(r) the set of all paths in a record r.

2 In this simplified data model, we do not represent the ordering on the elements of a sequence, since the considered queries will not exploit this order. Moreover, a sequence nested in a sequence is seen as a constant as core queries will not go through them either.

Queries. We consider two types of queries, which capture the core of the native query languages of KV-stores, namely get and check queries. These are evaluated from the root of a record. A get query is used to retrieve all constant values that lie at the end of a rooted and valued path. A check query is a Boolean expression yielding true when a rooted path is found. On the example, the query get(dept.course) returns all courses provided by the department (here: "Logic", "AI"), while the query check(dept.prof.phone) verifies whether at least a professor in the department has a phone.

Formally, a query Q has the form get(K) or check(K) with K a sequence of keys. The set of answers to Q over a record r is denoted by Q(r) and defined as follows. Let r0 be the root of r. Then, get(K)(r) = {c ∈ CONST | r0Kc ∈ paths(r)} and check(K)(r) = {true} if there is r0Kv ∈ paths(r), otherwise check(K)(r) = ∅. Finally, the set of answers to Q over a store I, denoted by Q(I), is the union of Q(r) for all r ∈ I.

Rule language. We now present a novel rule language for expressing ontological knowledge on key-value records. In the OMQA setting we define, KV-records are naturally the language for expressing factual knowledge on the application domain. We make an important distinction between the internal and the leaf nodes of the record's tree. We consider that internal nodes represent individuals, while leaf nodes hold the constants associated by properties. This choice is similar to that of the RDF language, where entities are URIs and values are literals. Building on this, we see the keys within records as binary relations (like roles in description logics), which hold either between a pair of individuals, or between individuals and constants. Another important aspect to consider when dealing with hierarchically organized information is the fact that the semantics of a value is determined by its position within the tree structure. We thus provide a mechanism to select a node based on the key-path defined by its ancestors, that we call a context.

The general form of a KV-rule is Context : Body →Head. Specifically, KV-rules can be of three types:

(A) K : k1 → k2 (inclusion between keys) (B) K : K1.val →K2 (inclusion between valued paths) (C) K : K1 → ∃K2 (mandatory path)

where k1, k2 are keys and K, K1, K2 are sequences of keys. We allow the context K to be empty, which is denoted by ϵ. Moreover we also allow the body path K1 of type (C) rule to be empty, but at the only condition that the context K is not. The context K defines where the rule can be possibly applied. Note that K does not need to start at the root of a record as (in contrast with queries) rules apply at any level.

Type (A) rules define inclusions between keys, hence allowing to organize them hierarchically. Type (B) rules define inclusions between valued paths. They specify multiple ways of accessing a constant value in the record. Finally, type (C) rules are mandatory path assertions. These allow one to express that some path exists in the structure, even if its extremity is unknown. Importantly, since the body of the type (C) rules is possibly empty, these can be used to add properties to all individuals within a certain context.

To illustrate, consider the following KV-rules, whose evaluation on the example record is illustrated in Figure 1.

σ1 = phone → contact

σ2 = course.val → prof.teaching σ3 = dept : prof.boss.val → director.name σ4 = dept : director → faculty σ5 = dept.faculty : ϵ → ∃phone

Rule σ1 says that the key phone is a particular case of the key contact (key inclusion). The application of this rule creates an edge labeled with contact with the same end nodes as the edge labeled with phone. In the example, this allows us to positively answer the query check(dept.prof.contact) whose answer otherwise would be false. Rule σ2 states that each course is taught by a professor. The .val in the rule body indicates that this applies only to valued paths (i.e., course keys pointing only towards constant values). The application of this rule creates a new valued path in the tree ending with a node labeled with the course name. Because of σ2, the answer set of the query get(dept.prof.teaching) includes that of get(dept.course). Contextual rules are exemplified by the last three rules. Rules σ3 and σ4 model the fact that, within a department, the boss of a professor is always the director, and that director is a particular case of faculty, respectively. It is then possible to answer "Alice" to the query get(dept.faculty.name). Rule σ5 is a mandatory path rule asserting that a key phone is always present within the context dept.faculty. Rules σ1 and σ5 make true the answer to the query check(dept.director.contact). Note that σ5 has an empty body, as indicated by the presence of ϵ, hence it applies regardless of the actual sub-record content.

Finally, we conclude remarking that our language can also be seen as a constraint language, as studied in databases (see the related work section), in which case enforcing constraints on incomplete data may also lead to infer new data. In the same way, tuple-generating dependencies [Abiteboul et al., 1995] can be seen either as constraints, or as ontological knowledge under the name of existential rules.

Rule application. As illustrated in Figure 1, rule application does not strictly preserve the tree-shape of records, since key inclusions replace keys by sets of keys (e.g., phone, contact). To formally define rule application we will thus consider trees with multi-edges (i.e., allowing for several edges with the same end nodes), called multi-trees. Similarly, paths with multi-edges will be called multi-paths.

We say that a rule σ = K : K1[.val] → [∃]K2 (optional parts between brackets) is applicable to a multi-tree r, if there exists a path vKv0K1v1 ∈ paths(r), which must be valued if [.val] is used. The effective application of σ at v0 (with respect to v1) consists of adding to the multi-tree a new path v0K2v2, where i) v2 = v1 if σ is of type (A), ii) v2 is a fresh node labeled as v1 if σ is of type (B), otherwise iii) v2 is a fresh node labeled by a fresh null (σ is of type (C)).

Due to space restriction, we do not define the semantics of KV-stores and rules in terms of interpretations (those can, however, be obtained from the logical translation provided later). Instead, we define the notion of the saturation of a record r by a set of rules Σ, which can be seen as a canonical model of (Σ, r), representative of all models of (Σ, r), similarly to the chase on existential rules (see later). The breadth-first saturation of a multi-tree r by a set of KVrules Σ, denoted by Sat(Σ, r), is inductively defined as follows: Sat0 (Σ, r) = r and, for any i > 0, Sati (Σ, r) is obtained from ri-1 = Sati-1 (Σ, r) by performing in parallel all possible rule applications on ri-1 ; finally, Sat(Σ, r) = ⋃i≥0 Sati (Σ, r). This notion is well-defined since the order in which the rule applications are performed at each level has no incidence on the result (up to the choice of labeled nulls).

Ontological query answering. A knowledge base (KB) is a pair K = (I,Σ), where I is a KV-store and Σ is a set of KV-rules. The notion of a (certain) answer is defined as follows. Given a query Q and a tree r, a value e belongs to Q(({r},Σ)) if e ∈ Q(Satk (Σ, r)), for some k ≥ 0. The set of answers to a query Q over K, is defined as Q(K) = ⋃r∈I Q(({r}, Σ)).

Note that materializing the saturation of a tree has several disadvantages of both practical and theoretical nature. First, it produces multi-trees, that are supported by some systems only. Second, the saturated tree may be infinite (e.g., the record r = {k : a} with rule σ : k.val → k.k generates an infinite set of paths). In the remainder of the paper we will therefore consider the following query reformulation problem. Given a KB K = (I,Σ) and a check or get query Q, compute a set of queries {Q1, . . . ,Qn} such that Q(K) = ⋃i Qi(I). Before tackling this question, we give a logical counterpart of our framework.

First-order logic translation. The framework translates naturally into first-order logic (FO). To a record we assign an existentially closed formula. E.g., for the example record: ∃x0, x1(root (x0 ) ∧ dept (x0 ) ∧ name(x0 , CS ) ∧ const (CS ) . . . ∧ prof (x0 , x1 ) ∧ name(x1 ,Bob) ∧ const(Bob) ∧ . . .). Note that the root and the constant leaves are marked by atoms of the form root(-) and const(-) respectively.

A query get(K) translates into a conjunctive query of the form ∃x0(root(x0) ∧ FO(K, x0, xn) ∧ const(xn)), where FO(K, x0, xn) is the translation of the key sequence K into a FO formula with free variables x0 and xn. A query check(K) translates into a Boolean conjunctive query of the form ∃x0∃xn(root (x0) ∧ FO(K, x0, xn)). Finally, we illustrate the translation of KV-rules on the example, omitting universal quantifiers for conciseness:

1. phone(x0, x) → contact (x0, x) 2. course(x0, x) ∧ const (x) → ∃z0 prof (x0, z0) ∧ teach(z0, x)

3. dept (x1, x0) ∧ prof (x0, y1) ∧ boss(y1, x) ∧ const (x) → ∃z0director (x0, z0) ∧ name(z0, x) 4. dept (x1, x0) ∧ director (x0, x) → faculty(x0, x) 5. dept (x1, x2) ∧ faculty(x2, x0) → ∃zphone(x0, z)

We observe that KV-rules are actually translated into existential rules, which are positive and conjunctive rules of the form ∀x∀y(Body[x, y] → ∃zHead[x, z]). Moreover, the notions of a rule application and of an answer in the KV framework coincide with the same notions in the existential rule framework. This allows us to obtain the following result (where |= denotes classical logical entailment, and FO(Q) and FO(K) are the FO translations of Q and K).

Proposition 1 (Soundness and Completeness). Let K = (I,Σ) be a KB. For any query Q=check(K), we have Q(K) ̸= ∅ iff FO(K) |= FO(Q). For any query Q=get(K) and constant value a, we have a ∈ Q(K) iff FO(K) |= FOxn↦→a(Q), where xn ↦→ a is the substitution of xn by a.

As already mentioned, our saturation notion corresponds to

the fundamental (breadth-first) chase tool on existential rules. To study decidability and complexity, we consider the following decision problems: Given a KB K and a check query Q, is Q(K) ̸= ∅? Given a KB K, a get query Q and a constant a, does a ∈ Q(K) hold?

We first point out that the restriction of path inclusions to valued paths is crucial for decidability. Were we to remove this restriction, query answering would become undecidable, as already observed in several contexts [Abiteboul and Vianu, 1999; Buneman et al., 2000; Calvanese et al., 2016; Mugnier et al., 2016].

Relation to existing ontology languages. By slightly modifying the FO translation of path inclusion rules (without incidence on query entailment), we see that KV-rules can be translated into a fragment of existential rules with decidable query answering, namely frontier-guarded existential rules, in which an atom from the rule body (called a guard) contains all the frontier variables, which are the variables shared by the body and the head of the rule [Baget et al., 2011]. To do so, for any rule σ of type B, FO(σ) = ∀x0∀x(B →H) is replaced by |CONST[I]| rules obtained by substituting x with each constant c ∈ CONST[I] (where CONST[I] is the restriction of CONST to I). A closer look at our objects allows to recast our problem as atomic query answering over fixed-arity guarded rules, which provides an upper bound for combined complexity, namely EXPTIME [Cal`ı et al., 2013]. Since the translation to frontier-guarded rules is not data-independent, it does not yield any useful upper bound for data complexity.

Even though KV-rules are based on paths, their logical translation does not fit into any known DL dialect, due to the presence of contextual key inclusions (rules of type A). Were we to consider only context-free key inclusions, then the preceding translation into frontier-guarded existential rules would be expressible in the DL ELHIO (where role inclusions capture the key inclusions, nominals allow us to speak of constants, and inverse roles are used to capture contexts in rules of type B and C). However, this correspondence does not yield improved complexity results.

3 Resolution throughWord Rewriting System

Our approach to the query answering problem is to reformulate an input query into a pointed regular path query (PRPQ) [Abiteboul and Vianu, 1999] which represents in a succinct way the (possibly infinite) set of reformulations of a check or get query. A PRPQ is defined by a regular language, which also is pointed, in the sense that it is evaluated from a fixed node (for JSON, this is always the root of the record). The semantics of a PRPQ over JSON records is as follows. Let L be (the language of) a PRPQ and r be a tree corresponding to a JSON record, then we say that a node v in r is an answer to the query if there exists a word K belonging to L such that root(r).K.v is a path in r. In the remainder, we suppose the reader to be familiar with regular languages.

We want to show that the problem of computing the PRPQ reformulations of check and get queries can be reduced to that of computing the (regular) language of ancestors in a word rewriting system. Towards this goal, starting from a set of KV-rules Σ, we first define a word rewriting system RΣ which simulates the forward-chaining application of the rules in Σ. Then, computing the language of ancestors of words derived by RΣ will mimic the reformulation into PRPQs.

Word rewriting systems. A word (or string) rewriting system R over a finite alphabet A consists of a finite set of word rewriting rules of the form (u1, u2) ∈ A∗ ×A∗ , where u1 and u2 are respectively the left and right hand side of a rule. We say that a word w rewrites to w′ following the rule (u1, u2) if w = w1 ·u1 ·w2 and w′ = w1 ·u2 ·w2, where "·" denotes word concatenation. We denote by →R the single-step rewriting relation and by →∗R its reflexive and transitive closure. We write w→∗R w′ if there exists a (possibly empty) word sequence (w =)w1, . . . ,wn(= w′ ) such that wj rewrites to wj+1 following a rule of R. Given a regular language L, we denote by AncR(L) the set of ancestors of L by R, which is defined as AncR(L) = {w | ∃w′ ∈ L, w→∗R w′ }.

An important family of rewriting systems we are interested in are suffix rewriting systems. Intuitively, these are rewriting systems restricting the application of rules thereby allowing them to rewrite only the suffixes of words. Formally, we say that w1 · u2 · w2 is a suffix rewriting of w1 · u1 · w2 with the rule (u1, u2) whenever w2 is empty. It is well known that, if only suffix rewritings are allowed, then AncR(L) is a regular language [B¨uchi, 1962; Caucal, 2000].

At this point, it is not difficult to see that, for the case of context-free KV-rules, word rewriting can mimic the reformulation of KV-rules of type (A) and suffix word rewriting that of KV-rules of type (B). To capture the full reasoning capabilities of KV-rules we need however to introduce a more general notion of rewriting system, that we call an extended rewriting suffix system (ERS). An ERS contains two types of rules, namely relabeling and suffix rules. Intuitively, the former type of rules replace a single letter, while the latter are used for suffix rewriting. Furthermore, we consider suffix rules made of pairs of regular languages (rather than simply pairs of words) which will allow for a more concise representation of rewriting rules. Conceptually, a rule (L,R) with L and R regular languages means that any word belonging to L can be replaced by any word of R. Finally, all types of rules in an ERS are associated with a context restricting their application. This is necessary to mimic the behaviour of KVrules with contexts. As before, contexts are written as regular languages and make a rule selectively applicable only to subwords that are preceded by a word defined by the context.

Formally, an ERS is made of:

• contextual relabeling rules of the formC : a ↦→ b where C is a regular language, and a and b two letters. Their semantics is a follows: u1 · a · u2 rewrites to u1 · b · u2 by such type of rule if u1 belongs to C;
• contextual extended suffix rules of the formC : L ↦→R with C, L, R regular languages. Their semantics is a follows: u1 · l rewrites to u1 · r by such type of rule if u1 belongs to C, l belongs to L, and r belongs to R.

To illustrate, (c1 | c2)+ : a ↦→ b is a contextual relabeling rule replacing a with b in a word, whenever this is preceded by any (non-empty) sequence of c1 and c2. By this rule, c1 · c1 · c2 · a rewrites to c1 · c1 · c2 · b, while a · a does not rewrite to any word. To illustrate suffix rewriting rules, consider c : b ↦→ a∗ . With this rule, c · b · c has no rewriting, while c · b · c · b rewrites to all words of the form c · b · c · a · · · a.

Simulating KV-rules with ERS. We now build an ERS which simulates the forward-chaining application of KV rules. This is possible because KV-rules actually reason on the paths of the input tree, and therefore we can see a path root(r).k1 . . . kn.v of the saturated tree as a word k1 · k2 · · · kn obtained by applying the ERS rules. We have however to be careful that KV-rules of type (B) and (C) do not interact, because the former rules cannot be applied on a branch generated by the latter rules. We do so by introducing two novel symbols "$" and "♯" to be employed for words within our ERS. Any path root(r).K.v in the tree will be represented by the word K·$ if v is (a leaf) labeled by a constant, and by the word K · ♯ otherwise (that is, v is an internal node or a leaf labeled with a null possibly produced by a type (C) rule). When simulating type (B) KV-rules with ERS rules, we will make these apply only to suffix rules ending with $.

A technical aspect of our construction is that to model the structure of multi-trees, we consider that letters in an ERS are sets of keys. We will consider a new alphabet P = 2KEYS \ ∅. From now on, for clarity we denote by a, b, c ∈ P the (complex) letters belonging to this set and by u, v,w ∈ P ∗ the (complex) words made with these letters. For instance, let a = {a1, a2}, b = {b}, and c = {c1, c2} then u = a · b · c = {a1, a2} · {b} · {c1, c2}. The set of complex words that "enable" a word w = a1 · · · an, is defined as En(w) = {a1 · · · an ∈ P ∗ |ai ∈ ai}. For example, we have that En(a · b) = {(a∪{a})·(b∪{b}) | a, b ∈ P} (note that we may have a = {a} or b = {b}). Note that P ∗ and En(w) are regular languages over P, which we will employ within ERS rules.

Given a word over KEYS∗ it will be handful to represent its corresponding (complex) element over P ∗ . We define the function Sg() (standing for "singleton") which given a (nonempty) word of the form w = a1 · · · an yields its complex version with sets of letters made of a single element Sg(w) = {a1} · · · {an}. Finally, we denote by P ∗ · (♯ + $) the set of words of P ∗ extended with the ♯ or $ symbol. Here "+" denotes the union operator for regular languages.

A set of KV-rules Σ is associated with an ERS RΣ = Ψ(Σ) containing all possible rules obtained by instantiating the following rules.

• (A) inclusion between keys: a rule K : k1 → k2 is associated with the relabeling (meta-)rule

• (B) inclusion between valued paths: a ruleK:K1.val →K2 is associated with the suffix "valued" rule

• (C) mandatory path: a rule K : K1 → ∃K2 is associated with the suffix rule

To illustrate the construction, we give the ERS associated with the example used in the previous section.

We can easily see that ERS rules mimic KV-rules. Consider for example the word {dept} · {prof} · {boss} · $ which corresponds to a path in the input tree of Figure 1 ending on the value "Alice". This rewrites to {dept}·{director}·{name}·$ by Ψ(σ3) and then to {dept}·{director, faculty}·{name}· $ by Ψ(σ4). Then, Ψ(σ5) gives {dept}·{director, faculty}· {phone} · ♯ and Ψ(σ1) gives {dept} · {director, faculty} · {phone, contact} · ♯. All of these words exactly correspond to some multi-paths inferred in Figure 1. Note also that the initial word representing a valued path ends with $ while the final word ends with the ♯ symbol. This is correct, since only check queries have some answers on this multi-path of the saturated tree in Figure 1.

The following proposition formally states the correspondence between KV-rules and ERS.

Proposition 2. Let Σ be KV-rule set, RΣ its corresponding ERS, and w ∈ KEYS∗ a word. Let Lc be the set of words u such that Sg(u)·♯ or Sg(u)·$ is in AncR(En(w)·P ∗ ·($+♯)). Then, for each tree r, check(w)(r, Σ) = ∪u∈Lc check(u)(r). Let Lg be the set of words u such that Sg(u) · $ is in AncR(En(w) · $). Then, get(w)(r, Σ) = ∪u∈Lg get(u)(r).

Proof sketch. First note that a word in P ∗ · (♯ + $) corresponds to a (multi-)path in a (multi-)tree. We take all maximal paths in the tree, together with their proper prefixes, and we associate them with a word ending by ♯. Moreover, for all maximal paths in the tree ending on a leaf node labeled with a constant, we add a word ending by $. By transforming w in En(w), we generate all multi-paths enabling w. We can check that each rewriting step is correct, in the sense that if a word w corresponds to a multi-path in Sat(r,Σ) then its ERS rewritings by R do as well. Conversely, applying one saturation step can be simulated by rewriting the word corresponding to a multi-path. □

Computing the language of ancestors. We now turn to the problem of effectively computing the language of ancestors. In the following, we suppose that the reader is familiar with finite automata (NFAs). Let us first recall that the size of the alphabet P is exponential w.r.t. the size of KEYS. An NFA A is represented by a 5-tuple, (P, Q,∆, I, F), with P the alphabet, Q the set of states, ∆ the set of transitions, and I and F the set of initial and final states, respectively. We denote ϵ-transitions with (q, ϵ, q′ ). We omit P when it is clear from the context and denote by L(A) (resp. LA(q)) the language recognized by A (resp. by A with q as initial state).

The automaton defining Lc (as defined in Proposition 2) can be computed in polynomial time in the size of the NFAs defining AncR(En(w) · P ∗ · ($ + ♯)) by considering only transitions labeled with letters of the form Sg(a) ∈ P, making final all the states reaching ♯ or $. Finally, to get back to the alphabet KEYS, each letter Sg(a) is transformed into a. Similarly, the automaton defining Lg can be computed from AncR(En(w) · $), with this time the final states reaching $. The next proposition presents how to compute the two languages.

Proposition 3. Let Σ be KV-rule set, RΣ its corresponding ERS, and w ∈ KEYS∗ a word. Then there exist NFAs defining AncR(En(w) · P ∗ · ($ + ♯)) and AncR(En(w) · $) whose number of states is in O(2|KEYS|∗(M+1) ∗ (|w| + |Σ|)), where M is the maximal length of contexts in Σ, |Σ| is the size of Σ, and |w| the size of w.

Proof sketch. The construction consists in four steps:

First, starting from the word w = w1 · · ·wn in the input query, we construct an automaton Aw = (Qw,∆w, sI, Fw) recognizing (En(w) · P ∗ · ($ + ♯)) (or similarly (En(w) · $)). The construction is standard: the set of states is {i | 0 ≤ i ≤ |w| + 1}, ∆w = {(i, a, i + 1) | i < |w|,wi+1 ∈ a} ∪ {(|w|, a, |w|) | a ∈ P}∪{(|w|+1, $, |w|+1), (|w|+1, ♯, |w|+ 1)}; 0 (resp. |w| +1) is the initial (resp. final) state.

Secondly, we define the notion of a context automaton for a set of KV-rules Σ: it is an NFA Ac = (Qc,∆c, sc, Qc) able to check (P ∗ · En(K)) for each key sequence K defining a context. So, for each K there exists a set of states FK ⊆ Qc such that L(Qc,∆c, sC, FK) recognizes (P ∗ · En(K)). The set of states Qc corresponds to the set of words over P whose length is at most M and we write q u for the state associated with the word u. So, the size of Qc is bounded by 2|KEYS|∗(M+1) . We use suffixM (u) to denote the suffix of the word u whose length is M, and u itself when |u| ≤ M. Then, we write q u for the state associated with the word u. Then, ∆c = {(q u , a, q suffixM (u·a) ) | q u ∈ Qc, a ∈ P}. The initial state sc corresponds then to qϵ . FK is the set of states q u such that u ∈ P ∗ · En(K).

Thirdly, in the same way, for each suffix rule (Ci : Li ↦→ Ri) we build an NFA ALi recognizing Li with O(|Li|) states.

The last step is the most technical one, and requires extended automata completion techniques for constructing in polynomial time a new automaton B which can recognize AncR(En(w) · P ∗ · ($ + ♯)) and AncR(En(w) · $).

We first initialize B as the product of Ac with the union of Aw together with all of the ALj :

We initialize the automaton with the following transitions ∆ = {((q, q c ), a, (q′ , q′c ))|(q, a, q′ ) ∈ ∆w ∪ (∪j∆j), (q c , a, q′c ) ∈ ∆c} and complete it as follows:

1. for all relabeling rules C : a ↦→ b in RΣ, q c in FC, and ((q, q c ), b, (q′ , q′c )) in ∆, we add ((q, q c ), a, (q′ , q′c ));

As the number of states stays the same, the construction is polynomial in A and B. □

When there is no relabeling, the construction is much simpler: the alphabet P is not needed and the number of states is in O(|Σ|)×(|w|+|Σ|)). Similarly, when there are relabeling rules but no context, a context automaton is no more needed and the number of states is in O(|w| + |Σ|).

4 Complexity of OMQAwith KV-Rules

In the preceding section, we showed how to construct, using word rewriting techniques, query reformulations in the form of pointed RPQs. By analyzing the construction, we obtain the following complexity upper bounds:

Theorem 1. Query answering on KV-stores is:

• in NLSpace for data complexity;
• in PSpace for combined complexity;
• in NLSpace for combined complexity without contexts.

Proof sketch. Membership in NLSpace for data complexity follows directly from the (data-independent) reformulation into RPQs (which can be evaluated in NLSpace).

For the PSpace upper bound, we cannot explicitly construct the automata provided by the proof of Prop. 3, as they may be exponentially large. However, the states of the NFA can be stored in polynomial space, and we can test on the fly whether a given transition belongs to the automaton. The idea is then to simulate, using a non-deterministic PSpace Turing machine, a run of the NFA, keeping only the current position and state in memory. The only real difficulty is handling epsilon transitions, created by a suffix rule (Point 2 in the construction of the automaton B). Indeed, we need to verify whether L((q, qc)) ∩ Rj is non-empty. Such non-emptiness checks can be carried out in PSpace, as emptiness testing is in NLSpace in the size of the automaton (which here is of exponential size). The NLSpace upper bound for combined complexity in the context-free case proceeds similarly, except that now we are working with a polysize automaton.

We have matching lower bounds for combined complexity.

Theorem 2. Query answering on KV-stores is PSPACE-hard for combined complexity, and NLSpace-hard for combined complexity when restricted to context-free rules.

Proof sketch. NLSpace hardness is a simple reduction from directed reachability, so we concentrate on the PSpace hardness result. The proof is by reduction from the word problem for polynomially space-bounded deterministic Turing machines. Let M = (Q, A, δ, qi , qf ) be such a Turing machine, where Q is the set of states, A is the alphabet, δ is the transition function, qi is the initial state and qf the final one. Given M and an input word w, the problem is whether M accepts w. Let n be the bound on the number of tape cells used by M on input w. Configurations can be captured by words of length n over the alphabet Θ = A ∪ (A × Q), where a ∈ A signifies that a tape cell contains a, and (a, q) signifies that the cell contains a, is under the head, and the current state is q. Using the keys (i, β) where i is in {1, · · · , n} and β ∈ Θ, we can straightforwardly encode configurations as sequences of keys (1, σ1) . . . (n, σn).

Our initial KV-store is a record whose only path encodes the initial configuration, i.e., it is of the form r0Kv, with K = (1, (w1, qi )).(2, w2) . . . (k, wk).(k+1, b) . . . (n, b) where w = w1 . . . wk and b denotes the blank symbol.

We then define KV-rules that allow us to build the full sequence of configurations of the run on w. First, for every key (i, a), we include the type (A) rule (i, a) → C, where C is a new key, denoting 'any cell'. Below, we will denote by C n a sequence of such keys of size n. We next include rules that, from the previous configuration, construct the current configuration cell by cell, by 'appending' it at the end of the previous configuration. Note that the label of the i-th cell in the current configuration only depends on the three cells at positions (i - 1), i and (i + 1) in the previous configuration (with the first and last cells depending on only two cells). Therefore, we add the following contextual rules for each i ∈ {2, . . . , n-1}: (i-1, α).(i, β).(i+1, γ).C n-3 :(i-1, ξ) → ∃ (i - 1, ξ).(i, Trans(α, β, γ)) where Trans(α, β, γ) returns the new label for cell i assuming that cells i - 1, i, i + 1 are respectively labelled α, β, γ in the previous configuration. Intuitively, the context goes from cell (i-1) in the previous configuration to the cell that precedes cell (i - 1) in the current configuration, and a new path that encodes cell i-1 followed by cell i in the current configuration is created. Similar rules are introduced to handle the first and last tape cells.

Finally, we use rules of the form (i, (α, qf )) → ∃Ok together with C.Ok→ ∃Ok to propagate upwards the fact that we have reached an accepting configuration. It is easily verified that M accepts w iff check(Ok) returns true.

The question of the lower bound for data complexity remains open, as the specific shape of the data may play a role. Indeed, the following results show that the complexity is higher over arbitrary data instances than over KV-stores (assuming NLSpace ̸= PTime):

Proposition 4. Query answering in the logical fragment associated with KV-rules (resp. context-free KV-rules) and check/get queries is PTime-hard for data complexity (resp. combined complexity) over arbitrary datasets.

5 Discussion and RelatedWork

Evaluating ontology-mediated queries over KV-stores. We showed that the query answering task can be reduced to

(1) computing a regular path expression corresponding to the ancestors of a word encoding the query in an extended rewriting suffix system associated with the KV-rules (2) evaluating this expression on the KV-store. However, the evaluation of regular expressions is not directly supported by KV-stores native languages. Nevertheless, as records have bounded depth d, one can still generate all check/get queries whose length is bounded by d, thereby making query answering complete. In practice, however, this may be inefficient when the regular expression contains a Kleene-∗ or large disjunctions, as many queries could be generated. This is a known issue for semi-structured data-management systems, which is tackled by relying on a concise structural summary of the tree, such as data-guides [Goldman and Widom, 1997]. In our case, by relying on a structure that simply lists all maximal paths in the tree, one can select those belonging to the language of the regular expression, which suffices to ensure complete query answering. The list of maximal paths in a record can be computed off-line in a single traversal of the record. Moreover, path-membership for regular expressions is in linear time.

Related work. Two different approaches to OMQA over KV-stores have been recently proposed by [Mugnier et al., 2016] and [Botoeva et al., 2016]. The approach of [Mugnier et al., 2016] is similar to ours in the sense that they propose a rule language, with rules of the form K1 → K2, that are directly applicable to KV-stores. However, the expressivity of this language makes OMQA undecidable in general, hence restrictions are imposed: either the rules have a body restricted to a single key, or they have a head restricted to a single key, both kinds of rules being incompatible. Moreover, there is no correspondence with first-order-logic, hence the semantics remains operational. The work of [Botoeva et al., 2016] extends the data integration-oriented approach known as Ontology-Based Data Access to KV-stores (and specially MongoDB). The ontology and the queries are expressed at a 'conceptual level' (in OWL 2 and SPARQL) and JSON-toRDF mappings allow one to define a virtual RDF view of JSON data. Query reformulation is performed at the conceptual level, then translated into a KV-query via the mappings.

In the domain of semi-structured databases, several constraint languages have been proposed. In particular, the works of [Abiteboul and Vianu, 1999] and [Andre et al., 2007] study the implication problem for inclusion constraints expressed by regular-path expressions. These capture as a special case the context-free rules of type (B) studied here. In [Buneman et al., 2000] path inclusions with contexts and inverses are studied. Finally, [Calvanese et al., 2016] studied the extension of Description Logics with path-constraints.

As for future work, we plan to extend the rule language to represent concepts associated with nodes and investigate query reformulation with richer KV-queries, such as tree queries as provided for instance in MongoDB.

Acknowledgements

We thank the reviewers for their insightful reviews. This work was supported by ANR projects ASPIQ (ANR-12-BS020003), DeLTA (ANR-16-CE40-0007) and PAGODA (ANR12-JS02-0007), CPER Nord-Pas de Calais/FEDER DATA 2015-2020 and STIC AMSUD project FoG