Wudage Melisachew

Chekol

Schema Query Containment

Keywords: Query containment, schema, SPARQL, ALCH, entailment regime inclusion de requêtes, SPARQL, ontologies, RDF

SPARQL is a schema query language allowing access to the TBox part of a knowledge base. Moreover its entailment regimes enable to take into account knowledge inferred from persistently stored knowledge bases in the query answering process. Thus, the emergence of SPARQL entailment regimes provide a new perspective for the containment problem. As one has to deal with axiomatic triples, datatype reasoning, and blank nodes that result in infinite answers. Of particular interest for us is the union of conjunctive queries that are a core fragment of SPARQL. In this paper, we study the containment of such queries based on the OWL-ALCH Direct and RDF-Based Semantics entailment regimes.

Introduction

Most description logics query languages allow to retrieve only instance information and do not provide a means to access schema contained in a TBox. Tasks such as retrieving, accessing, and reusing parts of an ontology would be greatly facilitated by a query language that would allow querying for schema and instance information. In this regard, there exist query languages for OWL such as SPARQL, SPARQL-DL [START_REF] Sirin | Sparql-dl: Sparql query for owl-dl[END_REF], SPARQL-OWL [START_REF] Kollia | SPARQL query answering over OWL ontologies[END_REF], and OWL-SAIQL [START_REF] Kubias | Owl saiql-an owl dl query language for ontology extraction[END_REF]. SPARQL has support for querying schema. It allows querying of class instances, class and role names, subclasses, subproperties, domain and range relations among others. SPARQL's basic graph pattern is designed in such a way that it can be extended to query different ontology languages. SPARQL is based on simple graph matching (i.e., based on simple entailment) and is not able to include implicitly stored answers that require reasoning. Thus, in order to be able to query ontologies other than based on simple entailment. It is necessary to extend the entailment regime for the respective ontology language. This allows to generate more results that are inferred using the semantics of the axioms in the ontology. Consequently, the W3C has worked towards this issue making SPARQL a query language for ontologies also known as SPARQL entailment regimes [START_REF] Glimm | Using SPARQL with RDFS and OWL entailment. Reasoning Web. Semantic Technologies for the Web of Data[END_REF].

Query containment is a well studied problem dating back to the end of the 70s, that started with the pioneering paper of Chandra and Merlin [START_REF] Chandra | Optimal Implementation of Conjunctive Queries in Relational Data Bases[END_REF]. In that paper, it is proved that conjunctive query containment is NP-complete. In general, query containment is the problem of checking whether the result of one query is included in the result of another one for any given knowledge base. Equivalence and satisfiability problems can be derived from containment, thus, we mainly concentrate on the containment problem. In relational databases, union of conjunctive query containment has been studied using containment mappings also known as graph homomorphism and canonical databases. It is known that, for (union of) conjunctive queries, query answering and containment are equivalent problems since query containment can be reduced to query answering [START_REF] Chandra | Optimal Implementation of Conjunctive Queries in Relational Data Bases[END_REF]. Unfortunately, to apply these techniques to a query language equipped with ontologies and regular expressions is not entirely possible. That is why for semistructured data query languages (referred as regular path queries) automata theoretic notions are often employed to address containment and other problems [START_REF] Calvanese | Containment of Conjunctive Regular Path Queries with Inverse[END_REF]. In addition to using automata, containment has been addressed by a reduction to satisfiability test. In this direction, queries are translated into formulas in a particular logic that supports the query languages features and then the overall problem is reduced into satisfiability test. Several works exist that developed and used this technique [START_REF] Calvanese | Conjunctive Query Containment and Answering under Description Logics Constraints[END_REF][START_REF] Calvanese | Containment of Conjunctive Regular Path Queries with Inverse[END_REF][START_REF] Chekol | SPARQL query containment under RDFS entailment regime[END_REF][START_REF] Chekol | SPARQL query containment under SHI axioms[END_REF][START_REF] Genevès | Efficient Static Analysis of XML Paths and Types[END_REF] which also inspired this work.

The study of SPARQL query containment has attracted a lot of attention. Notable, the works in [START_REF] Chekol | SPARQL query containment under RDFS entailment regime[END_REF] and [START_REF] Chekol | SPARQL query containment under SHI axioms[END_REF] address containment under the ρdf [START_REF] Muñoz | Minimal deductive systems for RDF[END_REF] entailment regime and SHI schema axioms respectively and establish a double exponential upper bound complexity. Additionally, in [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF] the containment and optimization of OPTIONAL queries is investigated while providing a Π P 2 -complete complexity for containment. Importantly, a benchmark of containment solvers is revealed in [START_REF] Melisachew Wudage Chekol | Evaluating and benchmarking sparql query containment solvers[END_REF]. The implementations of containment solvers allow the extension of query and ontology languages. Consequently, in this paper, we consider a fragment of OWL 2 based on the description logic ALCH that can be encoded in the µ-calculus extended with nominals and converse, to study the containment of SPARQL queries under OWL-ALCH Direct and RDF-Based Semantics entailment regimes.

Preliminaries

We assume basic familiarity with the syntax and semantics of RDF(S) and OWL on the level of the RDF and OWL Primers [START_REF] Hayes | RDF semantics[END_REF][START_REF] Hitzler | Owl 2 web ontology language primer[END_REF][START_REF] Manola | Rdf primer[END_REF]. We present a very minimal introductory of SPARQL, Inria µ-calculus, and RDF transition systems. Additionally, we shorten (in parenthesis) RDF(S) and OWL vocabularies names as follows:

OWL-ALCH

Encoding OWL 2 schema axioms (built from the DL underlying OWL, SROIQ(D)) into the µcalculus with nominals and inverse leads to undecidability. Thus, we need to consider a fragment of OWL that alleviates this problem. Removing the features such as role inverse (I), role composition (R), transitivity (S), data type restrictions (D), (qualified) cardinality restrictions (Q) from SROIQ(D) reduces the complexity from N2ExpTime to ExpTime. The OWL fragment based on this logic (ALCH) can be encoded into µ-calculus. A DL-based syntax of this language is discussed as follows. In the schema language ALCH, a concept C can be a bottom concept (⊤), an atomic concept A, or a complex concept ¬C, ∃R.C, ∀R.C or C ⊓ D. A role R is an atomic role. An ALCH TBox consists a set of concept and role inclusion axioms [START_REF] Horrocks | Practical reasoning for expressive description logics[END_REF].

Semantics: the OWL 2 Direct Semantics (DS) is a direct model-theoretic semantics of OWL 2 which is strongly related to the semantics of description logics. Whereas the OWL 2 RDF-Based Semantics (RBS) is a direct extension of the RDFS semantics. It interprets RDF triples directly without the need of mapping an RDF graph into structural OWL objects [START_REF] Hitzler | Owl 2 web ontology language primer[END_REF].

Here we present the syntax and Direct Semantics of OWL-ALCH concepts, roles and axioms. OWL 2 has various syntactic notations, we use the user friendly functional style syntax 1 . The OWL functional style syntax is constructed as shown in Table 1 and2. OWL-ALCH axioms: as the name implies OWL-ALCH axioms lack role inverse, role composition, number restrictions, and description logic datatypes. This choice allows to retain satisfiability of containment under the µ-calculus fragment chosen for this study. Next, we present the abstract syntax of a fragment of SPARQL that is used to query OWL-ALCH ontologies.

SPARQL

Abstract syntax : SPARQL queries are formed from query patterns which in turn are defined inductively from path patterns, i.e., tuple t ∈ UBV × e × UBLV, with V a set of variables disjoint from UBL (URIs, Blank nodes and Literals -are used to identify values such as strings, integers and dates), and e is regular path expression (knows property hierarchies2 . Query patterns are formed according to the following definition. Definition 1. A query pattern q is inductively defined as: The AND fragment of query patterns are also known as basic graph patterns (BGPs) . A SPARQL SELECT query is a query of the form q(W ) such that W is a tuple of variables in V which are called distinguished variables, and q is a query pattern. The variables V W are called non-distinguished variables. As discussed below, in SPARQL entailment regimes, nondistinguished variables cannot appear by design.

q ::= UBV × e × UBLV | q 1 AND q 2 | {q 1 } UNION {q 2 } e ::= U | V | e 1 /e 2 | e 1 e 2 | e + | e * Chekol Descriptions(C) DL Syntax DL Semantics I = (∆ I , . I ) A A A I ⊆ ∆ I owl:Thing ⊤ ⊤ I = ∆ I owl:Bottom ⊥ ⊥ I = ∅ ObjectUnionOf(C 1 C 2 ) C 1 ⊔ C 2 C I 1 ∪ C I 2 ObjectIntersectionOf(C 1 C 2 ) C 1 ⊓ C 2 C I 1 ⊓ C I 2 ObjectComplementOf(C) ¬C ∆ I \ C I ObjectOneOf(o 1 o 2 ) {o 1 } ⊔ {o 2 } {o I 1 } ⊔ {o I 2 } ObjectSomeValuesFrom(R C) ∃R.C {x | ∃y. x, y ∈ R I and y ∈ C I } ObjectAllValuesFrom(R C) ∀R.C {x | ∀y. x, y ∈ R I implies y ∈ C I } Descriptions(R) R R R I ⊆ ∆ I × ∆ I Individuals (o) o o o I ∈ ∆ I _:anonymous _:anonymous _:anonymous I ∈ ∆ I
= (∆ I , . I ) SubClassOf(C 1 C 2 ) C 1 ⊑ C 2 C I 1 ⊑ C I 2 EquivalentClasses(C 1 C 2 ) C 1 ≡ C 2 C I 1 ≡ C I 2 DisjointClasses(C 1 C 2 ) C 1 ⊓ C 2 ⊑ ⊥ SubObjectPropertyOf(R 1 R 2 ) R 1 ⊑ R 2 R I 1 ⊑ R I 2 EquivalentObjectProperties(R 1 R 2 ) R 1 ≡ R 2 R I 1 ≡ R I 2 ObjectPropertyDomain(R C) ∃R.⊤ ⊑ C ObjectPropertyRange(R C) ⊤ ⊑ ∀R.C ClassAssertion( C o) o : C o I ⊆ C I ObjectPropertyAssertion( R o 1 o 2 ) (o 1 , o n ) : R (o I 1 , o I n ) ⊆ R I
Semantics: SPARQL has multiset (or bag) semantics, however, when dealing with containment, we consider set semantics. This is due to the undecidability of union of conjunctive queries under bag semantics [START_REF] Ioannidis | Containment of conjunctive queries: Beyond relations as sets[END_REF]. We refer the reader for the semantics SPARQL queries under OWL DS and RBS entailment regimes to [START_REF] Glimm | Using SPARQL with RDFS and OWL entailment. Reasoning Web. Semantic Technologies for the Web of Data[END_REF]. Importantly, under both DS and RBS entailment regimes, there are no non-distinguished variables since answers are computed from the BGPs of the query, projection is considered a post-processing step. In other words, projection is performed after the evaluation of basic graph patterns, i.e., after all the variables are bound to values in the ontology. We consider this essential feature when dealing with containment. Now, we provide a compact summary of the semantics of SPARQL query evaluation under OWL-ALCH Direct Semantics entailment regime. A detailed discussion with insightful examples can be found in [START_REF] Glimm | Using SPARQL with RDFS and OWL entailment. Reasoning Web. Semantic Technologies for the Web of Data[END_REF][START_REF] Glimm | SPARQL beyond subgraph matching[END_REF][START_REF] Kollia | SPARQL query answering over OWL ontologies[END_REF]. The following definition is taken from [START_REF] Glimm | Using SPARQL with RDFS and OWL entailment. Reasoning Web. Semantic Technologies for the Web of Data[END_REF]. The function sk(.) replaces blank nodes with fresh IRIs (IRIs that are neither in the queried graph nor in the query). |= DS denotes the OWL DS entailment relation.

Definition 3 (Containment under an entailment regime). Given a set of TBox axioms S of OWL-ALCH and two queries q and q ′ with the same arity, q is contained in q ′ with respect to an entailment regime e, denoted q ⊑ e q ′ , iff q(O) ⊆ q ′ (O) for every ontology O satisfying S based on e-semantics. Where q(O) denotes the answers of q when evaluated in O.

Definition 4 (Equivalence). Given queries q, q ′ , and a set of axioms S, q and q ′ are equivalent with respect to an entailment regime e, denoted q ≡ e q ′ , iff q ⊑ e q ′ and q ′ ⊑ e q.

Example 1 (Containment under e-entailment). Containment does not hold between the following queries, namely q and q ′ , under simple and RDF entailment. However, containment holds under e-(RDFS, DS, and RBS) entailment regime in one direction, i.e., q ⊑ e q ′ and q ′ ⊑ e q. SELECT ? s ? c WHERE { ? s ? x ? d . ? x s p t y p e . ? d s c ? c . } SELECT ? s ? c WHERE { ? s t y p e ? c . } Example 2. Consider containment of the following queries under different entailment regimes. q(x, y) = (z, sp, sc) AND (z, domain, Class) AND (x, z, y) q ′ (x, y) = (x, sc, y) q ′′ (x, y) = (x, type, Class) UNION (y, type, Class) Example 3 (Containment). q is contained in q ′ under the RDFS entailment regime but not under the simple and RDF regimes. q(x) = (x, sp, parentOf) q ′ (x) = (x, a, rdf : Property) Note that we switch between SPARQL's W3C and abstract syntax of queries as necessary.

The evaluation of SPARQL queries is proved to be PSPACE-complete. However, the evaluation problem is NP-complete for the fragment containing only AND and UNION query patterns [START_REF] Alkhateeb | Extending SPARQL with regular expression patterns (for querying RDF)[END_REF]. In addition, union of conjunctive query answering in ALCH is ExpTime [START_REF] Ortiz | Worst-case optimal conjunctive query answering for an expressive description logic without inverses[END_REF]. SPARQL queries can be encoded into µ-calculus formula. The syntax of this logic is given in the next section.

Chekol

µ-calculus

The µ-calculus is a logic obtained by adding fixpoint operators to ordinary modal logic [START_REF] Kozen | Results on the propositional µ-calculus[END_REF]. It has several extensions, for this work, we use the µ-calculus with nominals and converse programs. The syntax of the µ-calculus is composed of countable sets of atomic propositions and nominals AP , a set of variables Var, a set of programs and their respective converses Prog for navigating in graphs. A µ-calculus formula, ϕ, can be defined inductively as follows:

ϕ ::= ⊤ | q | X | ¬ϕ | ϕ ∧ ψ | a ϕ | [a]ϕ | µXϕ | νXϕ
where q ∈ AP, X ∈ V ar and a ∈ P rog is a transition program or its converse ā. The greatest and least fixpoint operators (ν and µ) respectively introduce general and finite recursion in graphs [START_REF] Kozen | Results on the propositional µ-calculus[END_REF]. The semantics of the µ-calculus is given over a transition system, K = (S, R, L) where S is a non-empty set of nodes, R : P rog → 2 S×S is the transition function, and L : AP → 2 S assigns a set of nodes to each atomic proposition or nominal where it holds, such that L(p) is a singleton for each nominal p. For converse programs, R can be extended as

R(ā) = {(s ′ , s) | (s, s ′ ) ∈ R(a)}.
The valuation function V : Var → 2 S maps each variable into a set of nodes. For a valuation V , variable X, and a set of nodes S ′ ⊆ S, V [X/S ′ ] is the valuation that is obtained from V by assigning S ′ to X. The semantics of a formula in terms of a transition system K (a.k.a. Kripke structure) and a valuation function is represented by ϕ K V ⊆ S. The semantics of basic µ-calculus formulae is defined as follows:

⊤ K V = S ⊥ K V = ∅ q K V = L(q), q ∈ AP, L(q) is singleton if q is a nominal X K V = V (X), X ∈ V ar ¬ϕ K V = S\ ϕ K V ϕ ∧ ψ K V = ϕ K V ∩ ψ K V ϕ ∨ ψ K V = ϕ K V ∪ ψ K V a ϕ K V = {s ∈ S | ∃s ′ ∈ S.(s, s ′ ) ∈ R(a) ∧ s ′ ∈ ϕ K V } [a]ϕ K V = {s ∈ S | ∀s ′ ∈ S.(s, s ′ ) ∈ R(a) ⇒ s ′ ∈ ϕ K V } µXϕ K V = {S ′ ⊆ S | ϕ K V [X/S ′ ] ⊆ S ′ } νXϕ K V = {S ′ ⊆ S | S ′ ⊆ ϕ K V [X/S ′ ] }
Note that the evaluation of sentences is independent of valuations and hence we define the following. For a sentence ϕ, a Kripke structure K = (S, R, L), and s ∈ S, we denote K, s |= ϕ if and only if s ∈ ϕ K , henceforth K is considered as a model of ϕ. In other words, K is considered as a model of φ if there exists an s ∈ S such that K, s |= φ. If a sentence has a model, then it is called satisfiable. If a µ-calculus formula ψ appears under the scope of a least µ or greatest ν fixed point operator over the programs {s, p, o, d, s, p, ō, d} as, µX.

ψ ∨ s X ∨ p X ∨ • • • or νX.ψ ∧ s X ∧ p X ∧ • • • , then
, for the sake of legibility, we denote the formulae by lfp(X, ψ) and gfp(X, ψ), respectively. µ-calculus formulas that are encodings of SPARQL queries are interpreted over RDF transition systems.

RDF Transition Systems

RDF transition systems are first introduced in [START_REF] Chekol | SPARQL query containment under RDFS entailment regime[END_REF].They are labelled transition system representations of RDF graphs where two sets of nodes are introduced: one set for each triple (called triple node) and the other set for each subject, predicate, and object of each triple. A triple node Inria is connected to its subject, predicate, and object nodes. Transition from one node to another is done by using a set of transition programs {s, p, o, d} and their converses.

Example 4 (RDF transition system). Consider the RDF transition system associated with RDFS graph given below.

Resource sc Class . The µ-calculus extended with nominals and converse lacks functionality or number restrictions. Thus, one cannot impose that each triple node is connected to exactly one node for each subject, predicate, and object node. However, one can impose a lighter restriction to achieve this by taking advantage of the technique introduced in [13] and adopted in [START_REF] Wudage | Static Analysis of Semantic Web Queries[END_REF]. Since it is not possible to ensure that there is only one successor, then we restrict all the successors to bear the same constraints. Thus, they become interchangeable. This can be done by rewriting the formulas using a function f such that all occurrences of a ϕ (existential formulas) are replaced by a ⊤ ∧ [a]ϕ. f is defined inductively on the structure of a µ-calculus formula.

Resource sc

f (⊤) = ⊤ f (q) = q q ∈ AP ∪ N om f (X) = X X ∈ V ar f (¬ϕ) = ¬f (ϕ) f (ϕ ∧ ψ) = f (ϕ) ∧ f (ψ) f (ϕ ∨ ψ) = f (ϕ) ∨ f (ψ) f ( a ϕ) = a ⊤ ∧ [a]f (ϕ) a ∈ {s, p, o} f ( a ϕ) = a f (ϕ) a ∈ {d, s, p, ō} f ([a]ϕ) = [a]f (ϕ) a ∈ Prog f (µX.ϕ) = µX.f (ϕ) f (νX.ϕ) = νX.f (ϕ)
Thus, when checking for query containment, we assume that the formulas are rewritten using function f . So far, we have laid the foundations by introducing the basics of SPARQL, µ-calculus and RDF transition systems. We are ready to final embark on the problem of schema query containment.

Schema Query Containment

To show the importance of SPARQL query containment under entailment regimes, we provide the following examples.

Example 5. Containment between q and q ′ does not hold under the RDFS entailment. However, containment holds q ⊑ e q ′ (for e = DS and RBS entailment regimes) because eqp can be expressed as a two-way sp relation. q(y) = (x, eqp, sc) AND (y, x, C) q ′ (y) = {(x, sp, sc) UNION (sc, sp, x)} AND (y, x, C) Chekol Example 6 (Satisfiability). q is unsatisfiable because of the semantics of disjointWith. q(x) = (x, type, y) AND (x, type, D) AND (y, disjointWith, D)

These examples show that when dealing with query containment and satisfiability problems, one has to consider not only the schema axioms but also the semantics of the schema vocabulary.

Beforehand, there are two main issues that one needs to take care of when dealing with schema query containment: infinite answers and blank nodes.

Infinite answers: query evaluation under OWL entailment regimes can result in infinite answers due to either: (1) inconsistency in the queried graph, (2) an infinite number of axiomatic triples, (3) arbitrary blank nodes, or (4) infinite entailments in datatype reasoning. The axiomatic triples of RDFS are used only by the RBS and can be handled by suitably restricting solutions to an answer domain. In fact, the W3C recommendation 3 prohibits infinite answers by restricting answers to RDF(S) and OWL vocabulary subtracting rdf:_i (for all i ∈ N) and terms occurring in the data graph. Besides, blank nodes are skolemized, and inconsistencies are treated as errors [START_REF] Glimm | Using SPARQL with RDFS and OWL entailment. Reasoning Web. Semantic Technologies for the Web of Data[END_REF].

Blank nodes (bnodes): in the OWL entailment regimes, there are two sets of bnodes: (i) bnodes that represent anonymous OWL individuals, and (ii) bnodes used for encoding complex OWL syntax in RDF. The DS treats these bnodes differently (in the query answering process) whereas RBS handles bnodes just like RDFS, even in cases where they are needed for encoding OWL class expressions. However, when dealing with containment, we do not distinguish between these sets of bnodes in both DS and RBS entailment regimes. They are interpreted as existential variables (or non-distinguished variables). Since non-distinguished variables are not a feature of entailment regimes, we treat them as distinguished for checking containment.

Containment under OWL-ALCH Direct Semantics Entailment Regime

The OWL DS maps BGPs into OWL structural objects for query answering. However, when dealing with containment, we do not perform this mapping (as it is not relevant for testing containment). Checking the containment of SPARQL queries under the DS entailment can be reduced to encoding OWL-ALCH ontology axioms and queries as µ-calculus formulas and checking the unsatisfiability of the encoding (or formula). Consequently, in the following, we present the encoding of OWL-ALCH schema axioms, rewriting queries by considering the semantics of the schema, encoding the rewritten queries, and finally the reduction of containment into unsatisfiability test.

Definition 5. Given a set of schema axioms S and SPARQL queries q and q ′ , their containment under the OWL-ALCH Direct semantics entailment, q ⊑ DS q ′ , can be reduced to µ-calculus by rewriting the queries and checking the validity of the formula η(S) ∧ A(τ (q)) ∧ ¬A(τ (q ′ )). η, A, and τ are schema encoding, query encoding, and query rewriting functions respectively.

In the following, we present each of these functions in detail.

3 http://www.w3.org/TR/sparql11-entailment/ Inria

Encoding OWL-ALCH Schema

Given a set of schema axioms S = {s 1 , . . . , s n } comprising concept and role inclusions. The µ-calculus encoding of S is obtained using the function η as follows:

η(S) = η(s 1 ) ∧ • • • ∧ η(s n ) η(C 1 ⊑ C 2 ) = gfp X, η(C 1 ) ⇒ η(C 2 ) η(⊥) = ⊥ η(A) = A η(¬C) = ¬ω(C) η(C 1 ⊓ C 2 ) = η(C 1 ) ∧ η(C 2 ) η(∃R.C) = s p R ∧ o ( s o η(C)) η(∀R.C) = [s] [p]R ⇒ [o]([s][o]η(C)) η(R 1 ⊑ R 2 ) = gfp X, R 1 ⇒ R 2 Lemma 1.
Given a set of ALCH schema axioms S, S has a model iff η(S) is satisfiable.

Proof. (⇒) assume that there exists a model I = (∆ I , . I ) of S such that I |= S. We build a restricted transition system K = (S, R, L) from I using the following:

• for each element of the domain e I ∈ ∆ I , we create a node n e ∈ S ′ ,

• for each atomic concept A, if a I ∈ A I , then (n a , t) ∈ R(s), (t, n type ) ∈ R(p), (t, n A ) ∈ R(o), L(type), = n type , L(A) = n A and L(a) = n a where t ∈ S ′′ ,
• for each atomic role T , if

(x I , y I ) ∈ T I , then (n x , t) ∈ R(s), (t, n T ) ∈ R(p), and (t, n y ) ∈ R(o) such that n x , n y , n T ∈ S ′ , t ∈ S ′′ , and L(x) = n x , L(T ) = n T , L(y) = n y , • S = S ′ ∪ S ′′
To show that η(S) is satisfiable in K. We proceed inductively on the construction of the formula.

As the axioms, {s 1 , . . . , s n }, are made of role or concept inclusions or nominals, we consider the following cases:

• when η(s i ) = gfp X, ω(C 1 ) ⇒ ω(C 2 ) .
From the assumption it is the case that I |= c i , alternatively, C I 1 ⊆ C I 2 . To show that η(s i ) is satisfiable in K, we proceed on the construction of C 1 and C 2 .

1. If C 1 and C 2 are atomic concepts, then their encodings are atomic propositions C 1 and C 2 in the µ-calculus.

From C I 1 ⊆ C I 2 , we have that ω(C 1 ) K ⊆ ω(C 2 ) K = C 1 K ⊆ C 2 K . And hence, ω(C 1 ) ⇒ ω(C 2 ) is satisfiable in K.
Besides, the general recursion ν guarantees that the constraint is satisfied in each state of the transition system. Therefore, η(s i ) is satisfiable. 2. If C 1 and C 2 are complex concepts, then K |= η(s i ) can be proved by exploiting the construction each axiom and ω. For instance, if the axiom is

I |= C∧D∧∃R.C ⊑ ∀R.D ⇔ (C ∧ D ∧ ∃R.C) I ⊆ (∀R.D) I ⇔ C I ∩ D I ∩ (∃R.C) I ⊆ (∀R.D) I ⇔ ω(C) K ∩ ω(D) K ∩ ω(∃R.C) K ⊆ ω(∀R.D) K from case (1). ⇔ ω(C) ∧ ω(D) ∧ ω(∃R.C) K ⊆ ω(∀R.D) K µ-calculus semantics.
⇔ gfp X, ω(C) ∧ ω(D) ∧ ω(∃R.C) ⇒ ω(∀R.D) K the gfp (or ν) ensures that the implication holds in the entire transition system.

Intuitively, this extends to any axiom composed of complex concept constructs.

RR n°8484

• when η(s i ) = gfp X, ω(r 1 ) ⇒ ω(r 2 ) . From r I 1 ⊆ r I 2 we have that ∃n r1 ∈ L(r 1 ) implies

∃n r2 ∈ L(r 2 ) in K. Thus, ∃s ∈ ω(r 1 ) ⇒ ω(r 2 ) K . As K is a construction of I, η(c i ) is satisfiable in K.
Since K is a model of each η(s i ), then η(S) is satisfiable. (⇐) consider a transition system model K for η(S). From K, we construct an interpretation I = (∆ I , . I ) and show that it is a model of S.

• ∆ I = S, A I = A K for each atomic concept A,

• ⊤ I = ⊤ K , for a top concept, • r I = {(s, s ′ ) | ∀t ∈ r K ∧ t ′ ∈ S ∧ (s, t ′ ) ∈ R(s) ∧ (t ′ , t) ∈ R(p) ∧ (t ′ , s ′ ) ∈ R(o)} for each atomic role r,
Consequently, formulas such as gfp X, ω(r 1 ) ⇒ ω(r 2 ) and gfp X, ω(C 1 ) ⇒ ω(C 2 ) are true in I. The first formula expresses that there is no node in the transition system where ω(r 1 ) holds and ω(r 2 ) does not hold. This is equivalent to ω(r 1 ) ⇒ ω(r 2 ) and r 1 K ⊆ r 2 K since r 1 and r 2 are basic roles. Thus, we obtain r I 1 ⊆ r I 2 and I |= r 1 ⊑ r 2 . On the other hand, for the latter formula from above, one can exploit its construction. Note however that, similar justifications as above can be worked out to arrive at I |= C 1 ⊑ C 2 if C 1 and C 2 are basic concepts. Nonetheless, if they are complex concepts, we proceed as below. Consider the case when

C 1 = A ⊓ B and C 2 = ∃R.C, ω(C 1 ) ⇒ ω(C 2 ) K ⇔ ω(A ⊓ B) K ⊆ ω(∃R.C) K ⇔ A ∧ B K ⊆ s p R ∧ o ( s o C) K ⇔ A K ∧ B K ⊆ {s | ∃s ′ .s ∈ s p R K ∧ s ′ ∈ s o C K } ⇔ A I ∩ B I ⊆ {s | ∃s ′ .(s, s ′ ) ∈ R I ∧ s ′ ∈ C I } ⇔ (A ⊓ B) I ⊆ (∃R.C) I ⇔ I |= C 1 ⊑ C 2 Accordingly, from I |= s 1 ∧ • • • ∧ I |= s n , it follows that I |= S.

Query Rewriting

SPARQL query containment under OWL-ALCH DS entailment regime can be determined by rewriting queries using the semantics of the schema vocabulary and then reducing the encoding of the rewriting to unsatisfiability test. The rewriting of SPARQL queries can be done by using SPARQL property paths and the semantics of the schema vocabulary as discussed in the following. Definition 6. Given a SPARQL query q, a rewriting function τ produces its rewriting shown in Table 3. (c 2 , onp, p 2 ) . (p 1 , sp, p 2 ) τ (q 1 AND q 2 ) = τ (q 1 ) AND τ (q 2 ) τ (q 1 UNION q 2 ) = τ (q 1 ) UNION τ (q 2 ) Table 3: Rewriting SPARQL queries using inference rules.

| eqc * ), c) τ ((s, x, o)) = (s, x, o) when x is a variable τ (c 1 , disWith, c 2 ) = (c 1 , sc, ¬c 2 ) τ (s, eqc, o) = (s, eqc, o) UNION (s, sc, o) AND (o, sc, s) τ ((p, eqp, q)) = (p, eqp + , q) UNION (p, sp, q) AND (q, sp, p) τ (c 1 , sc, c 2 ) = (c 1 , sc + | eqc + , c 2 ) UNION (c 1 , svf,

SELECT ? s WHERE {

? s ? x ? d . ? x s p+ t y p e . ? d s c+ ? c . } SELECT ? s WHERE { { ? s t y p e / ( s c * | e q p * ) ? c . } UNION { ? s ? r ? y . ? r s p * /dom/ s c * ? c . } UNION { ? y ? r ? s . ? r s p * / r a n g e / s c * ? c . } }

Encoding Queries

The variables and constants in a query are encoded using nominals of the µ-calculus. Basically, the variables and constants are frozen, i.e., equivalent to obtaining a canonical instance of the query. Afterwards, a recursive function A is used to inductively construct a formula. Given two SPARQL queries q(W ) and q ′ (W ), the containment test q(W ) ⊑ q ′ (W ) can be encoded into the µ-calculus as follows:

Φ q⊑q ′ = A(q) ∧ ¬A(q ′ ) A((x, y, z)) = lfp X, s x ∧ R(y, z) A(q 1 AND q 2 ) = A(q 1 ) ∧ A(q 2 ) A(q 1 UNION q 2 ) = A(q 1 ) ∨ A(q 2 )
In lfp, x and z are nominals whereas regular expression patterns (property hierarchies) that appear in the query are encoded into atomic propositions using the function R. This function takes two arguments (the predicate which is a regular expression pattern and the object of a triple).

R(uri

Φ q⊑q ′ = A(q) ∧ ¬A(q ′ ) A(q) = A(s, x, d) ∧ A(x, sp, type) ∧ (d, sc, c) = lfp X, s s ∧ p x ∧ o d ∧ lfp X, s x ∧ p sp ∧ o type ∧ lfp X, s d ∧ p sc ∧ o c A(q ′ ) = lfp X, s s ∧ p type ∧ o c ¬A(q ′ ) = gfp X, [s]¬s ∨ [p]¬type ∨ [o]¬c
So far, we have produced the encoding of schema axioms and the rewriting of queries and their encodings. Thus, we are ready to prove the correctness of this reduction. We denote the reduction by Φ(q ⊑ DS q ′ ) = η(S) ∧ A(τ (q)) ∧ ¬A(τ (q ′ )).

Lemma 2. Let q be a SPARQL query, for every RDF transition system K whose associated RDF graph is G, we have that q is satisfiable in G iff A(q) is satisfiable in K.

Proof. (Sketch) (⇒) q G = ∅ implies that G is at least a canonical instance of q and can be produced using a function f as shown below:

• if (x, y, z) ∈ q, then f ((x, y, z)) = (x, y, z) ∈ G,
• if (x, e, z) ∈ q, then f ((x, e, z)) = (x, e, z) ∈ G,

• if (x, e/e ′ , z) ∈ q, then f ((x, e, y)) ∈ G and f ((y, e ′ , z)) ∈ G,

• if (x, e | e ′ , z) ∈ q, then f ((x, e, z)) ∈ G or f ((x, e ′ , z)) ∈ G,
• if (x, e + , z) ∈ q, then f ((x, e, y 1 )) ∈ G and . . . and f ((y n , e, z)) ∈ G, Inria • if (x, e * , z) ∈ q, then f ((x, e + , z)) ∈ G Consequently, since G is an instance of q, G is a model of q. Now, one can construct an RDF transition system σ(G) = (S, R, L) in the same way as is done in [START_REF] Wudage | Static Analysis of Semantic Web Queries[END_REF]. To prove that σ(G) is a model of A(q), we consider the encoding of the non-distinguished variables with ⊤ suffices to justify that σ(G) is a model of its encoding. Since ⊤ gets instantiated (in all possible ways) with the constants (and frozen variables) appearing in the lhs query. (⇐) Assume that A(q) K = ∅. We now create an RDF graph G from K as follows:

• if ∀s 1 , s 2 , s 3 ∈ S ′ ∧ t ∈ S ′′ .(s 1 , t) ∈ R(s) ∧ (t, s 2 ) ∈ R(p) ∧ (t, s 3 ) ∈ R(o) and for each triple t i = (x i , y i , z i ) ∈ q if s 1 ∈ L(x i ) ∧ s 2 ∈ L(y i ) ∧ s 3 ∈ L(z i ), then (x i , y i , z i ) ∈ G.
This case holds if x i , y i and z i are either distinguished variables or constants. Note here that if x i or y i or z i appear in another triple t j = (x j , y j , z j ) ∈ q, then the equivalent item in t j is replaced with the value of the corresponding entry in t i .

• if ∀s 1 , s 2 , s 3 ∈ S ′ ∧ t ∈ S ′′ .(s 1 , t) ∈ R(s) ∧ (t, s 2 ) ∈ R(p) ∧ (t, s 3 ) ∈ R(o)
and for each triple

t i = (x i , y i , z i ) ∈ q if s 1 ∈ L(x i ) ∧ s 2 ∈ L(y i ), then (x i , y i , c i ) ∈ G
where c i is a fresh constant. This case holds if z i is a non-distinguished variable. Similarly, the case when x i or y i or both are variables can be worked out.

• if ∀s 1 , s 2 , s 3 ∈ S ′ ∧ t ∈ S ′′ .(s 1 , t) ∈ R(s) ∧ (t, s 2 ) ∈ R(p) ∧ (t, s 3 ) ∈ R(o) and for each triple t i = (x i , e i , z i ) ∈ q if s 1 ∈ s p e i K ∈ L(e i ) ∧ s 2 ∈ L(e i ) ∧ s 3 ∈ ō p e i K , then (c i , e i , d i ) ∈ G
where c i and d i are fresh constants. This case holds if x i and y i are multiply occurring non-distinguished variables. Similarly, all the other cases can be worked out.

Since G is a technical construction obtained from an RDF transition system associated to q, it holds that q G = ∅.

Theorem 1 (Containment under OWL-ALCH DS entailment). Given SPARQL queries q(W ), q ′ (W ), and a set of ALCH axioms S, q(W ) ⊑ DS q ′ (W ) iff Φ(q ⊑ DS q ′ ) is unsatisfiable.

Proof. (⇒) We show the contrapositive: if q ⊑ DS q ′ , then Φ(q ⊑ DS q ′ ) is satisfiable. One can verify that every model G of S in which there is at least one tuple satisfying q but not q ′ can be turned into an RDF transition system model for Φ(q ⊑ DS q ′ ). To do so, consider a graph G that satisfies schema axioms S. Assume also that there is a tuple -→ a in the answers of q over G but not in the answers of q ′ . We can construct an RDF transition system K from G (as done [START_REF] Wudage | Static Analysis of Semantic Web Queries[END_REF]. From Lemma 1, we obtain that η(S) is satisfiable in K. At this point, it remains to verify that while A(q) is satisfiable in K, A(q ′ ) is not. To do so, we build the formulas A(q) and A(q ′ ) by first skolemizing the distinguished variables using the answer tuple -→ a . Consequently, from Lemma 2 one obtains A(q) is satisfiable. However, A(q ′ ) is unsatisfiable, this is because the nominals in the formula corresponding to the constants and variables that do not appear in the SELECT clause are not satisfied in K. This is justified by the fact that if a formula ϕ is satisfiable in an RDF transition system, then its negation ¬ϕ is unsatisfiable. So far we have: η(S), A(q), and ¬A(q ′ ) are satisfiable in K. Thus, Φ(q ⊑ DS q ′ ) is satisfiable in K. Without loss of generality, we get that Φ(q ⊑ DS q ′ ) is satisfiable.

(⇐) Φ(q ⊑ DS q ′ ) implies that there exists a transition system where the formula Φ(q ⊑ DS q ′ ) holds. Consequently, K is an RDF transition system due to the restriction imposed on the formula (cf. Proposition 1 [START_REF] Wudage | Static Analysis of Semantic Web Queries[END_REF]). From K it is possible to construct a model I so that we can utilize Lemma 1 to verify that indeed I is a model of S. Thus, it remains to show that the answers of q are not included in the answers of q ′ over I. From our assumption, we have that A(q) ∧ ¬A(q ′ ) is satisfiable in K. From this, we obtain that A(q) is satisfiable while A(q ′ ) is not. It is possible to build an RDF graph from the model I using a function that uses assertions to Chekol form triples. Thus, we have that the answers of q over G are not empty but q ′ is empty because G contains all those triples that satisfy q and not q ′ . Therefore, we get that the answers of q are not contained in that of q ′ . Queries and formulas are linearly encoded into the µ-calculus and the satisfiability test of a µ-caclulus formula can be done in an exponential amount of time. Therefore, we get the following proposition.

Proposition 1. SPARQL query containment under the OWL-ALCH DS entailment can be solved in a time of 2 O(n) , where n is the size of the encoding.

We thus obtain an ExpTime upper bound by Theorem 1. A lower bound is obtained by a reduction from query answering in ALCH [START_REF] Ortiz | Worst-case optimal conjunctive query answering for an expressive description logic without inverses[END_REF]. Hence, proving optimality of the complexity bound. So far, we have seen containment under the DS. Next, we address containment under the RBS entailment regime.

Lemma 3 ([4]

). Given queries q and q ′ , and an ALCH TBox T , query containment under OWL Direct Semantics, q ⊑ DS q ′ , can be polynomially reduced to query entailment with respect to a knowledge base that has a frozen q as an ABox, K = T , f (q) |= q ′ . f (q) is the frozen q i.e., all the terms in the query become constants. Proof. To prove this, we reduce the problem of (union of) conjunctive query entailment to query containment with respect to ALCH axioms [START_REF] Calvanese | Conjunctive Query Containment and Answering under Description Logics Constraints[END_REF][START_REF] Ortiz | Worst-case optimal conjunctive query answering for an expressive description logic without inverses[END_REF]. In doing so, we use a function π that translates union of conjunctive queries into SPARQL queries.

π(q 1 ∨ • • • ∨ q n ) = π(q 1 ) UNION • • • UNION π(q n ) π(C(x)) = (x, type, C) π(R(x, y)) = (x, R, y) π(q 1 , . . . , q n ) = π(q 1 ) AND • • • AND π(q n )
It remains to show that, given a TBox T and (union of) conjunctive queries q and q ′ , π(q) ⊑ T π(q ′ ) ⇔ K = T , f (q) |= q ′ (⇒) this direction is immediate from [START_REF] Calvanese | Conjunctive Query Containment and Answering under Description Logics Constraints[END_REF]. There, it has been implicitly shown that query containment under TBox axioms can be reduced to query entailment w.r.t. a knowledge base (cf. Lemma 3). (⇐) T , f (q) |= q ′ ⇒ ∀I. I |= T and

I |= f (q) ⇒ I |= q ′ ⇒ ∀I. I |= T and π(q) G = ∅ ⇒ π(q ′ ) G = ∅ * ⇒ ∀I. I |= T and π(q) G ⊆ π(q ′ ) G ⇒ π(q) ⊑ T π(q ′ )
* G can be constructed from I using σ ′ , by translating each assertion of the form a ∈ A I into (a, type, A) ∈ G and (a, b) ∈ R I into (a, R, b) ∈ G. Furthermore, the knowledge base f (q) can be unfrozen to q. Now, let us verify that, if there is an interpretation for a knowledge base K = T , O , then the following holds:

∀I. I |= q ⇔ π(q) G=σ ′ (I) = ∅ Inria
this can be proved by induction on the structure of the query. (Base case) when q

(v) = C(v). (⇒) I |= C(v) ⇒ τ (v) ∈ C I . Hence, we get G = σ ′ (I) = {(τ (v), type, C)}. Clearly, π(C(v)) G = (v, type, C) G = ∅. (⇐) Assume π(C(v)) G = ∅ ⇒ ∃ρ.ρ ∈ π(C(v)) G ⇒ ∃ρ.ρ ∈ (v, type, C) G ⇒ ∃ρ.(ρ(v), ρ(type), ρ(C)) ∈ G ⇒ ∃ρ.(ρ(v), type, C) ∈ G From G, one can generate a DL interpretation I = (∆ I , • I ) such that C I = {ρ(v)}. Thus, I |= C(v) since τ (v) = ρ(v) ∈ C I . When q(v, v ′ ) = R(v, v ′ ). (⇒) I |= R(v, v ′ ) ⇒ (τ (v), τ (v ′ )) ∈ R I . Let us construct a graph G using I, G at least contains {(τ (v), R, τ (v ′ ))}. Obvious, π(R(v, v ′ )) G = (v, R, v ′ ) G = ∅. (⇐) Assume π(R(v, v ′ )) G ⇒ ∃ρ.ρ ∈ (v, R, v ′ ) G ⇒ ∃ρ.(ρ(v), ρ(R), ρ(v ′ )) ∈ G ⇒ ∃ρ.(ρ(v), R, ρ(v ′ )) ∈ G Using G, let us build a DL interpretation I such that R I = {(ρ(v), ρ(v ′ ))}. As a consequence, I |= τ R(v, v ′ ) since (τ (v), τ (v ′ )) = (ρ(v), ρ(v ′ )) ∈ R I .
This concludes the proof of the base case. (Inductive case) when q( -→ v ) = q 1 , . . . , q n . Assume that I |= q 1 , . . . , q n ⇔ I |= τ q 1 and . . . and I |= τ q n ⇔ ∃ρ.ρ ∈ π(q 1 ) σ ′ (I) and . . . and ρ ∈ π(q n ) σ ′ (I) by induction hypothesis

⇔ ∃ρ.ρ ∈ π(q 1 ) σ ′ (I) ✶ • • • ✶ π(q n ) σ ′ (I) ⇔ ∃ρ.ρ ∈ π(q 1 ) AND • • • AND π(q 2 ) σ ′ (I) ⇔ π(q 1 ) AND • • • AND π(q 2 ) σ ′ (I) = ∅ When q( - → v ) = q 1 ∨ • • • ∨ q n . Starting from I |= q 1 ∨ • • • ∨ q n ⇔ I |= τ q 1 or . . . or I |= τ q n ⇔ ∃ρ.ρ ∈ π(q 1 ) σ ′ (I) or . . . or ρ ∈ π(q n ) σ ′ (I) from induction hypothesis. ⇔ ∃ρ.ρ ∈ π(q 1 ) σ ′ (I) ∪ • • • ∪ ρ ∈ π(q n ) σ ′ (I) ⇔ ∃ρ.ρ ∈ π(q 1 ) σ ′ (I) ∪ • • • ∪ π(q n ) σ ′ (I) ⇔ ∃ρ.ρ ∈ π(q 1 ) UNION • • • UNION π(q n ) σ ′ (I) ⇔ π(q 1 ) UNION • • • UNION π(q n ) σ ′ (I) = ∅
This concludes the induction step and the overall proof.

Containment under OWL-ALCH RDF-Based Semantics Entailment Regime

Unlike DS, in RBS, we need to take care of the RDFS axiomatic triples. Consider the following example.

Chekol

Example 9. Consider containment of the following queries. q = SELECT ? x WHERE { ? x r d f : t y p e r d f : P r o p e r t y . } q ' = SELECT ? x WHERE { ? x r d f : t y p e r d f s : C o n t a i n e r M e m b e r s h i p P r o p e r t y . } The answers of these queries under the OWL-ALCH RBS are infinite due to the RDFS axiomatic triples (particularly rdf:_i). As answering is tied to a queried graph, this can be eliminated as discussed above. However, containment faces a challenge as it is impossible to encode infinite axiomatic triples. One approach to alleviate this problem is to avoid all axiomatic triples that involve the URI rdf:_i. This is what is done is this paper. Another approach is by analysing the queries beforehand to see if they contain vocabularies that lead to infinite answers. When so, restrict the axiomatic triples to those that occur in the queries. As a consequence, q ⊑ RBS q ′ and q ′ ⊑ RBS q. By contrast, q ⊑ DS q ′ and q ′ ⊑ DS q since the DS does not involve axiomatic triples.

SPARQL query containment under the RBS entailment regime can be reduced to unsatisfiability test in the µ-calculus. That is, by encoding queries, OWL-ALCH schema axioms, and RDFS axiomatic triples into the µ-calculus, and testing the validity of the reduction. It is possible to reuse the encodings for the DS entailment regime with the encoding of axiomatic triples. Instead, here, we provide a different encoding for the semantics of the schema using OWL inference rules and the schema itself. Definition 7. The encoding of RDFS axiomatic triples (AT) minus rdf:_i for i ∈ N, AT = {at 1 , • • • , at n }, is produced by encoding each triple at i = (x, y, z) ∈ AT such that:

Φ AT = n i=1∧ati∈AT lfp X, s x ∧ p y ∧ o z
where x, y, and z are atomic propositions encoding triple elements.

Encoding OWL-ALCH rules and schema

The W3C calculus provides 78 rules, various simplification rules are introduced that allow to restrict to a much smaller number of features [START_REF] Krötzsch | The not-so-easy task of computing class subsumptions in OWL RL[END_REF]. Out of which, we are mainly interested in the rules that express the semantics of the schema vocabulary 4 . So that this semantics can be taken into account when testing containment. Note that, transitive and reflexive properties such as sc, sp, eqp, eqc, and sameAs are encoded as reflexive transitive closure: sc * and so on. This is because, with the µ-calculus, it is not possible to enforce transitivity of a property in a transition system. This is a consequence of the tree-model property of the µ-calculus, and the fact that transitivity does not hold in tree-shaped models [Sattler & Vardi 2001]. Definition 8. The encoding of OWL rules into µ-calculus formulae, Φ rules , is given by a function γ as shown in Table 4. So far, we have produced the encoding of the schema, inference rules, axiomatic triples and queries. Thus, we are ready to prove the correctness of the reduction:

Φ(q ⊑ RBS q ′ ) = Φ AT ∧ Φ rules ∧ Φ S ∧ A(q) ∧ ¬A(q ′ )
Theorem 3 (Containment under OWL-ALCH RBS). Given SPARQL queries q(W ), q ′ (W ), and a set of ALCH axioms S, q(W ) ⊑ RBS q ′ (W ) iff Φ(q ⊑ RBS q ′ ) is unsatisfiable.

Proof. It is sufficient to extend the proof of theorem 1. Since the RDFS axiomatic triples are satisfied by every graph, one can build an RDF transition system from such a graph which can be a model for Φ AT . Thus, we get that; when the axiomatic triples are satisfiable, then Φ AT is also satisfiable.

SPARQL query containment under RBS entailment can be determined in exponential amount of time (upper bound). Thus far we have shown that SPARQL query containment under the DS and RBS entailment regimes can be determined with the µ-calculus. Unlike DS, RBS adds RDFS axiomatic triples (making the size of the encoding large) and allows higher order queries [START_REF] Glimm | Using SPARQL with RDFS and OWL entailment. Reasoning Web. Semantic Technologies for the Web of Data[END_REF].

Discussion

Containment under simple, RDF, and RDFS entailment In order to determine SPARQL containment under simple, RDF, and RDFS entailment regimes. We fall back on the definition of entailment based RDF(S) semantics [START_REF] Hayes | RDF semantics[END_REF][START_REF] Horst | Combining rdf and part of owl with rules: Semantics, decidability, complexity[END_REF]. To be able to use this semantics for testing containment, we need to transform UCQs into RDF graphs by replacing variables with blank nodes. From any query it is possible to build an homomorphic graph by collecting all triples connected by AND and only those at the left of UNION (replacing variables by blank nodes). This graph is consistent as all RDF graphs. This is only true if the query does not contain a variable in the predicate position of its triple patterns. However, it has been shown that allowing blank nodes in predicate positions makes RDFS reasoning complete [START_REF] Horst | Combining rdf and part of owl with rules: Semantics, decidability, complexity[END_REF]. Leading us to the notion of generalized RDF graph, it is defined as a subset of the set UB × UB × UBL.

Definition 10 (BGP containment). Given two BGPs q and q ′ , determining q ⊑ s q ′ , q ⊑ rdf q ′ , and q ⊑ rdfs q ′ can be done by verifying the entailments f (q) |= s g(q ′ ), f (q) |= rdf g(q ′ ), and f (q) |= rdfs g(q ′ ) respectively. f and g transform each triple pattern in q and q ′ as:

f ((s, p, o)) = (f (s), f (p), f (o)) g((s, p, o)) = (g(s), g(p), g(o)) f (a) = freshURI(a) if a ∈ var(q) a otherwise g(a) = _:a if a ∈ var(q) a otherwise
Definition 11 (Entailment). Given query graphs G and G ′ , G e-entails G ′ , written as G |= e G ′ , if G can be extended to a graph G ex by applying e-entailment rules such that G ′ ⊆ G ex .

To define the containment between two UNION patterns, we extend the functions f and g as: g(q 1 UNION q 2 ) = g(q 1 ), g(q 2 ).

Inria

Definition 12 (UNION pattern containment). Given two UNION patterns q and q ′ , let f (q) = {g 1 , . . . , g n } and g(q ′ ) = {g ′ 1 , . . . , g ′ m } be their respective transformations, q ⊑ e q ′ iff ∀g ′ i ∈ g(q ′ ) ∃g j ∈ f (q) : g ′ i |= e g j , where 1 ≤ i, j ≤ n. Since the transformation of a BGP into an RDF graph is linear in the size of the pattern, the complexity of deciding containment under entailment regimes is the same as entailment check.

Related Work

Recently, the study of SPARQL query containment has gained moment, notably in [START_REF] Chekol | SPARQL query containment under RDFS entailment regime[END_REF][START_REF] Chekol | SPARQL query containment under SHI axioms[END_REF][START_REF] Melisachew Wudage Chekol | Evaluating and benchmarking sparql query containment solvers[END_REF][START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF]. The literatures in [START_REF] Chekol | SPARQL query containment under RDFS entailment regime[END_REF] and [START_REF] Chekol | SPARQL query containment under SHI axioms[END_REF] address containment under the ρdf [START_REF] Muñoz | Minimal deductive systems for RDF[END_REF] entailment regime and SHI schema axioms respectively and establish a double exponential upper bound complexity. Additionally, in [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF] the containment and optimization of OPTIONAL queries is investigated while providing a Π P 2 -complete complexity for containment. Importantly, a benchmark of containment solvers is revealed in [START_REF] Melisachew Wudage Chekol | Evaluating and benchmarking sparql query containment solvers[END_REF]. The implementations of containment solvers allow the extension of query and ontology languages. Thus, what we did here can benefit from these implementations.

Query Entailment is the decision problem associated with query answering. For CQs, query answering and containment are equivalent problems. In fact, query containment can be reduced to query answering. In this regard, conjunctive query containment under the description logic DLR is studied in [START_REF] Calvanese | Conjunctive Query Containment and Answering under Description Logics Constraints[END_REF]. CQ query answering in the presence of simple ontologies (fragments of DL-Lite) has been studied [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Lutz | Conjunctive query answering in the description logic el using a relational database system[END_REF]. For expressive ontology languages, query entailment (and hence containment) in DLs ranging from ALCI to SHIQ is shown to be 2EXPTIME in [START_REF] Eiter | Query answering in description logics with transitive roles[END_REF][START_REF] Glimm | Conjunctive query answering for the description logic shiq[END_REF][START_REF] Lutz | The complexity of conjunctive query answering in expressive description logics[END_REF][START_REF] Ortiz | Data complexity of query answering in expressive description logics via tableaux[END_REF]. By contrast, in this study we do not deal with the same query language as the one dealt with in [START_REF] Glimm | Conjunctive query answering for the description logic shiq[END_REF][START_REF] Ortiz | Worst-case optimal conjunctive query answering for an expressive description logic without inverses[END_REF]. In fact, the supported SPARQL fragment is strictly larger than the one studied in [START_REF] Glimm | Conjunctive query answering for the description logic shiq[END_REF][START_REF] Ortiz | Worst-case optimal conjunctive query answering for an expressive description logic without inverses[END_REF]. Specifically, UCQs in [START_REF] Ortiz | Worst-case optimal conjunctive query answering for an expressive description logic without inverses[END_REF] are made of C(x), R(x, y) for an atom C, a role R, and variables x and y, whereas we do also support queries capable of querying concept and role names at the same time, such as q(x) = (x, y, z). Beyond this, the novelty of the study is the reduction of the SPARQL containment problem to µ-calculus satisfiability, and the advantages of using such a logic: expressivity, good computational properties, extensibility. The main focus of the contribution is not the complexity bound by itself but rather a new approach with a broader logic, paving the way for future extensions as it was never done before.

Finally, with an implicit goal of minimizing query evaluation costs, in [START_REF] Pichler | Redundancy elimination on rdf graphs in the presence of rules, constraints, and queries[END_REF] comprehensive complexity results were obtained for the problem of redundancy elimination on RDF graphs in the presence of rules (RDFS or OWL), constraints (tuple-generating dependencies) and with respect to SPARQL queries.

Conclusion

We showed that deciding the containment of SPARQL queries under the OWL-ALCH DS and RBS semantics is ExpTime-complete. We have reduced the problem to the validity test in the µcalculus to establish membership and then the hardness by a reduction from query answering in ALCH. Implicitly, we have also shown that containment of SPARQL path queries under ALCH axioms can be determined in exponential amount of time. Recently, some implementations of containment solvers have been made available [START_REF] Melisachew Wudage Chekol | Evaluating and benchmarking sparql query containment solvers[END_REF][START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF]. Some of these are built on top of µ-calculus satisfiability solvers, thus this study enables to take advantage of these implementations. In the future, we will experiment the proposed approach using these tools. Additionally, we will explore the possibility of extending the schema language by using other fragments of the µ-calculus that enable encoding number restrictions [START_REF] Bonatti | The Complexity of Enriched µ-calculi[END_REF].

Chekol

A summary of complexity results on the problem of SPARQL query containment is shown in Table 5.

⊑

Inria Definition 2 (

 2 SPARQL query evaluation under OWL DS entailment regime). A partial mapping function ρ is a solution for a Object Graph Pattern (OGP) P and G under OWL Direct Semantics entailment if: 1. G can be mapped into an OWL DL ontology O(G) 2. P can be mapped into an extended OWL DL axioms O(P ) 3. Domain of ρ is exactly the set of variables in P 4. Terms in the range of ρ occur in O(G) or Voc(OWL): OWL vocabulary terms 5. If O(P ′ ) obtained from O(P ) by replacing anonymous individuals (blank nodes) with either IRIs or blank nodes is such that: O(G) ∪ O(P ′ ) is an OWL DL ontology and sk(O(G)) |= DS sk(ρ(O(P ′ )))

Example 7 .

 7 Consider the rewritings of the queries in Example 1. Inria τ ((s, sp, o)) = (s, sp + | eqp + , o) τ ((s, p, o)) = (s, x, o) AND (x, sp * eqp * , p) τ ((s, type, o)) = (s, type/(sc * | eqc * ), o) UNION (s, x, y) AND (x, (sp * | eqp * )/dom/(sc * | eqc * ), o) UNION (y, x, s) AND (x, (sp * | eqp * )/range/(sc * | eqc * ), o) τ ((p, dom, c)) = (p, (sp * | eqp * )/dom/(sc * | eqc * ), c) τ ((p, range, c)) = (p, (sp * | eqp * )/range/(sc *

Example 8 (

 8 , y) = p uri ∧ o y R(x, y) = p x ∧ o y R(e e ′ , y) = (R(e, y) ∨ R(e ′ , y)) R(e/e ′ , y) = R(e, s R(e ′ , y)) R(e + , y) = µX.R(e, y) ∨ R(e, s X) R(e * , y) = R(e + , y) ∨ s y Query encoding). Consider the encoding of the containment between queries in Example 1.

Theorem 2 .

 2 Query containment under ALCH Direct Semantics is EXPTIME-hard.

Definition 9 .

 9 b, c) ⇒ (a, sameAs, a) gfp X, θ(a, b, c) ⇒ θ(a, sameAs, a) rdfp5b (a, b, c) ⇒ (a, sameAs, a) gfp X, θ(a, b, c) ⇒ θ(c, sameAs, c) rdfp6 (a, sameAs, c) ⇒ (c, sameAs, a) gfp X, θ(a, sameAs, c) ⇒ θ(c, sameAs, a) rdfp7 (a, sameAs, b).(b, sameAs, c) ⇒ (a, sameAs, c) gfp X, θ(a, sameAs, c) ⇒ θ(a, sameAs + , c) * rdfp9 (a, type, Class).(a, sameAs, c) ⇒ (a, sc, c) gfp X, θ(a, type, Class) ∧ θ(a, sameAs, c) ⇒ θ(a, sc, c) rdfp10 (b, type, Property). (b, sameAs, d) ⇒ (b, sp, d)gfp X, θ(b, type, Property)∧ θ(b, sameAs, d) ⇒ θ(b, sp, d) rdfp12a (a, eqc, c) ⇒ (a, sc, c) gfp X, θ(a, eqc, c) ⇒ θ(a, sc, c) rdfp12b (a, eqc, c) ⇒ (c, sc, a) gfp X, θ(a, eqc, c) ⇒ θ(c, sc, a) rdfp12c (a, sc, b).(b, sc, c) ⇒ (a, eqc, c) gfp X, θ(a, sc, b) ∧ θ(b, sc, c) ⇒ θ(a, eqc * , c) * rdfp13a (a, eqp, c) ⇒ (a, sp, c) gfp X, θ(a, eqp, c) ⇒ θ(a, sp, c) rdfp13b (a, eqp, c) ⇒ (c, sp, a) gfp X, θ(a, eqp, c) ⇒ θ(c, sp, a) rdfp13c (a, sp, c).(c, sp, a) ⇒ (a, eqp, c) gfp X, θ(a, sp, c) ∧ θ(c, sp, a) ⇒ θ(a, eqp, c) * rdfp15 (a,svf, b).(a, onp, c). (d, c, e).(e, type, b) ⇒ (d, type, a) θ(d, θ ′ (θ(a, svf, θ ′ (e, type, b)), onp, c), b) ⇒ θ(d, type, a) rdfp16 (a, avf, b).(a, onp, c). (d, type, a).(d, c, e) ⇒ (e, type, b) θ ′ (θ(d, type, θ(a, onp, c) ∧ θ(a, avf, b)), c, e) ⇒ (e, type, b)prp-eqp1 (a, eqp, b)(c, a, d) ⇒ (c, b, d) gfp X, θ(c, θ(a, eqp, b), d) ⇒ θ(c, b, d) prp-eqp2 (a, eqp, b)(c, b, d) ⇒ (c, a, d) gfp X, θ(c, θ ′ (a, eqp, b), d) ⇒ θ(c, b, d) prp-pdw (a, propDisWith, b).(c, a, d) . (c, b, d) ⇒ false gfp X, θ(c, θ(a, propDisWith, b), d) ∧ θ(c, θ ′ (a, propDisWith, b), d) ⇒ ⊥ cls-nothing2(a, type, Nothing) ⇒ false gfp X, θ(a, type, Nothing) ⇒ ⊥ cls-svf1 (a, svf, b) (a, onp, c) (d, c, e)(e, type, b) ⇒ (d, type, a) gfp X, θ(d, θ ′ (θ(a, svf, θ ′ (e, type, b)), onp, c), b) ⇒ θ(d, type, a) cls-avf (a, avf, b) (a, onp, c) (d, type, a) (d, c, e) ⇒ (e, type, b) gfp X, θ ′ (θ(d, type, θ(a, onp, c) ∧ θ(a, avf, b)), c, e) ⇒ (e, type, b) scm-sco (a, sc, b)(b, sc, c) ⇒ (a, sc, c) gfp X, µY. p sc ∧ o ⊤ ∨ p sc ∧ s Y scm-spo (a, sp, b)(b, sp, c) ⇒ (a, sp, c) gfp X, µY. p sp ∧ o ⊤ ∨ p sp ∧ s Y scm-dom1 (a, dom, b)(b, sc, d) ⇒ (a, dom, d) gfp X, θ(a, dom, θ(b, sc, d)) ⇒ θ(a, dom, d) scm-dom2 (a, dom, b)(d, sp, a) ⇒ (d, dom, b) gfp X, θ(d, sp, θ(a, dom, b)) ⇒ θ(d, dom, b) scm-rng1 (a, range, b)(b, sc, d) ⇒ (a, range, d) gfp X, θ(a, range, θ(b, sc, d)) ⇒ θ(a, range, d) scm-rng2 (a, range, b)(d, sp, a) ⇒ (d, range, b) gfp X, θ(d, sp, θ(a, range, b)) ⇒ θ(d, range, b) where θ((x, y, z)) = x ∧ s ( p y ∧ o z) and θ ′ ((x, y, z)) = z ∧ ō ( p y ∧ s x Table 4: OWL 2 RL min rules encoded into µ-calculus formulae. The encoding of an OWL-ALCH TBox schema S = {t 1 , • • • , t n } is produced by encoding each schema triple t i = (x, y, z) ∈ S such that: Chekol Φ S = n i=1∧ti∈S lfp X, s x ∧ p y ∧ o z where x, y, and z are atomic propositions corresponding to triple elements.

Table 1 :

 1 OWL-ALCH syntax: concept, role and individual constructs.

	OWL syntax	DL syntax	DL Semantics I

Table 2 :

 2 OWL-ALCH axioms syntax and semantics.

Table 5 :

 5 rdf , ⊑ rdfs SPARQL query containment state-of-the-art.

	BGP, UNION	⊑ s NP-complete NP-complete new (ExpTime) new (ExpTime) ⊑ DS ⊑ RBS
	CQ, UCQ	NP-complete 2ExpTime	2ExpTime
	OPTIONAL OPTIONAL with projection	Π P 2 -complete Π P 2

RR n°8484

http://www.w3.org/TR/owl-primer/

http://www.w3.org/TR/sparql11-query/#propertypaths RR n°8484

Table 9 in http://www.w3.org/TR/owl2-profiles/ Inria

rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399


Devender Bhalla
email: devender.bhalla@unilim.fr

Dr Devender Bhalla

MICHEL DUMAS AND PIERRE-MARIE PREUX: PROMOTING TROPICAL NEUROLOGY SILENTLY -THE GIST OF THEIR CONTRIBUTIONS

Keywords: capacity-building, dementia, epilepsy, health system, neurology, neglected tropical diseases, research, tropical countries

This article presents the contribution by two senior French Neurologists over the past three decades in building, developing and promoting "tropical neurology" in a number of neglected countries of Asia, Africa and Latin America. It talks about the "human, dedicational and contributive value" of these two experts who do not come from an English-speaking world. It highlights meaningful changes that have been achieved in different tropical countries as a result of their direct contribution. This overview may likely be a cause for learning and motivation to others to really work in and for tropical countries, where a large proportion of global health burden is to be found.

"To our shame, neglected diseases have not received the attention they deserve from European Union for actions". Such tell-tale statements in support of neglected diseases (NDs) have appeared time and again, yet little groundwork on NDs has made such statements and acknowledgments, a decorative one.

Despite a restrictive and unsupportive environment around NDs [START_REF] Vanderelst | Quantifying the lack of scientific interest in neglected tropical diseases[END_REF], Institut d"épidémiologie neurologique et de Neurologie tropicale" of Limoges (France) has been actively working on a number of NDs in a number of "less visible (neglected)" tropical countries. This institute was established in 1982 by Prof Michel Dumas (figure 1) and is run by Prof Pierre-Marie Preux (figure 2). Since then, the institute has been the only organization in Europe, and one of the very few in the world, which has brought together two neglected themes: "neurological disorders" and "tropical countries".

By establishing this institute, Prof. Michel Dumas provided an apt platform to conduct "real" ground work for addressing the neurological needs of those living in the tropical countries.

Although the term "neglected" is frequently used in the literature, there has been nearly no attempt to precisely define what exactly is "neglected". The current list of NDs includes only infections, while chronic conditions, such as epilepsy, seizures, dementia, amyotrophic lateral sclerosis (ALS), stroke, multiple sclerosis (MS), etc. have been subjected to a similar neglect in developing/tropical countries. These chronic conditions also inflict severe burden in the poorest regions and have a known association with several neglected infections that are endemic in these regions. Chronic conditions do not cause dramatic outbreaks but rather exact their toll over a longer period of time, leading to crippling complications, severe disabilities and/or relatively slow deaths. For some of these chronic conditions, therapeutic and preventive solutions are available, but are nearly not being utilised, that further adds to the irony of them being labelled as "nonneglected". With respect to some of these neglected (infectious and chronic) conditions, we discuss some aspects of the contributions made by Prof Michel Dumas and Prof Pierre-Marie Preux towards advancement of epidemiology and neurology, development of scientific acumen and clinical capacity, and in turn improvement of the state of public health in various tropical regions (table 1). Dementia: Dementia is an important public health problem in tropical countries. They initiated and developed long-term research-action programs on dementia in several central African countries, despite periodic bouts of civil unrest here [START_REF] Guerchet | Factors associated with dementia among elderly people living in two cities in Central Africa: the EDAC multicenter study[END_REF][START_REF] Guerchet | Prevalence of dementia in elderly living in two cities of Central Africa: the EDAC survey[END_REF][START_REF] Paraiso | Prevalence of dementia among elderly people living in Cotonou, an urban area of Benin (West Africa)[END_REF]. They also identified a tool to determine accurate age of dementia subjects, an extremely important problem in dementia research [START_REF] Paraiso | Validation of the use of historical events to estimate the age of subjects aged 65 years and over in Cotonou (Benin)[END_REF]; as well as certain psychosocial factors important in the survival of demential subjects [START_REF] Guerchet | Factors associated with dementia among elderly people living in two cities in Central Africa: the EDAC multicenter study[END_REF].

Human T-lymphotropic virus type I (HTLV-1): HTLV-1 is a retrovirus implicated in a number of disorders and were one of the first groups to have conducted several surveys in West Africa to determine the seroprevalence and incidence of HTLV-1, and to have demonstrated a familial transmission and clustering of this viral disease in this sub-region [START_REF] Preux | HTLV-I-associated facial nerve palsy in Africans and people of African descent. Research Group in Tropical Neurology[END_REF][START_REF] Vallat | Lack of association between peripheral neuropathy and HTLV-I infection in west Africa. Epidemiological, serological and nerve biopsy study[END_REF]. They had also demonstrated a correlation of HTLV-1 with spastic paraparesis, as well as with lifestyle, environmental and geographic factors, and concomitant infections such as filariasis. For the first time, they had validated Lot quality assurance sampling method for field application to detect small clusters of infection.

Central nervous system infections (CNSIs): Their surveys and projects have helped to fill

"knowledge-gaps" on several CNSIs in tropical Africa. Particularly, these CNSIs included onchocerciasis and cysticercosis [START_REF] Druet-Cabanac | Onchocerciasis and epilepsy: a matched case-control study in the Central African Republic[END_REF], among other CNSIs. Interest of other research agencies on sleeping sickness (SS) has long declined in favor of other popular infections. However, they conducted several research-action programs on SS in tropical Africa, that particularly helped to determine: appropriate trypanocidal (mono and combination) therapies for second stage SS, regulatory role of several antibodies [START_REF] Girard | In vitro induction of nitric oxide synthase in astrocytes and microglia by Trypanosoma brucei brucei[END_REF] and cytokines, as well as development of validated models for carrying out immunopathological, neurohistological and therapeutic studies on SS [START_REF] Keita | Trypanosoma brucei brucei: a longterm model of human African trypanosomiasis in mice, meningo-encephalitis, astrocytosis, and neurological disorders[END_REF].

Development of chronic experimental models for SS in animals with cerebral lesions and neurological disorders had been a matter of difficulty then [START_REF] Keita | Trypanosoma brucei brucei: a longterm model of human African trypanosomiasis in mice, meningo-encephalitis, astrocytosis, and neurological disorders[END_REF].

Epilepsy: Their research-action programs have recently demonstrated epileptogenic role of malaria in Mali [START_REF] Ngoungou | Epilepsy as a consequence of cerebral malaria in area in which malaria is endemic in Mali, West Africa[END_REF] and Gabon [START_REF] Ngoungou | Cerebral malaria and sequelar epilepsy: first matched case-control study in Gabon[END_REF]. For this, a Bruce S. Schoenberg international Award in Neuroepidemiology for 2009 was given to the principal investigator from Gabon (Prof Edgard Ngoungou. This was the first time that someone from tropical Africa became an awardee. He is an ex-student of Prof Pierre-Marie Preux, and interestingly received a "letter of appreciation" from the President of Gabon as well (read: recognition of tropical experts through organized research).

Their estimates of the prevalence of epilepsy in Asia and sub-Saharan Africa are considered authoritative and are widely used. Their Limoges epilepsy screening questionnaire is also widely used in tropical countries and has helped to standardise data collection on epilepsy. They have recently demonstrated a greater benefit of using individual, rather than household, questionnaires for determining the burden of neurological disorders in low-income countries [START_REF] Quet | Determining the burden of neurological disorders in populations living in tropical areas: who would be questioned? Lessons from a Mexican rural community[END_REF].

Their recent activities on epilepsy in Asia have culminated in numerous first-timer results, for instance (a) validated epidemiological tools on self-esteem, fear, social support, discrimination, coping strategies, patient-derived quality of life, etc. [START_REF] Bhalla | Comprehensive evaluation of the psychosocial parameters of epilepsy: A representative population-based study in Prey Veng (Cambodia)[END_REF]; (b) an estimate on the annual requirement of two anti-epileptic drugs in an Asian country (i.e. Cambodia); (c) validation of reproductive causality of epilepsy and precise estimation of the preventability of epilepsy [START_REF] Bhalla | Population-based study of epilepsy in Cambodia associated factors, measures of impact, stigma, quality of life, knowledgeattitude-practice, and treatment gap[END_REF].

Besides this, they are one of the first researchers that have shown in Asia that not all epilepsy populations are stigmatized, although stigma is nearly always accorded to epilepsy "by default" [START_REF] Bhalla | Population-based study of epilepsy in Cambodia associated factors, measures of impact, stigma, quality of life, knowledgeattitude-practice, and treatment gap[END_REF]. Besides this, they have also long demonstrated a two-way correlation of epilepsy with malnutrition in Africa [START_REF] Crepin | Link between epilepsy and malnutrition in a rural area of Benin[END_REF].

Recently, experts of a parent body on epilepsy had repeatedly recommended that their activities on epilepsy in Asia (particularly Cambodia) are a "model for investigation of epilepsy in developing countries". Several activities are ongoing on epilepsy in a neighboring country, Laos where they were the first and only to determine the true burden of epilepsy in Laos, as well as several other aspects of epilepsy, particularly treatment-related [START_REF] Odermatt | Availability and costs of antiepileptic drugs and quality of phenobarbital in Vientiane municipality, Lao PDR[END_REF][START_REF] Harimanana | Is insufficient knowledge of epilepsy the reason for low levels of healthcare in the Lao PDR?[END_REF].

Although training of local staffs is often recommended as a means to bridge manpower and consequently treatment gap of epilepsy [START_REF] Bhalla | Manpower gap: An important barrier against reduction of the treatment gap of epilepsy[END_REF]. However, little thought has been given to which of them should be trained since not just doctors, but also neurologists, psychiatrists, nurses, pharmacists, midwives are insufficient in number and are also inequitably distributed. Very recently, they have been instrumental in identifying a "new" service provider (i.e. primary health center staff) for providing trained epilepsy care at a primary-care level. For many reasons, this strategy is extremely suitable, especially for rural populations [START_REF] Bhalla | Manpower gap: An important barrier against reduction of the treatment gap of epilepsy[END_REF]. Based on this strategy, a provincial program on epilepsy has very recently been started in two Asian countries [START_REF] Bhalla | Manpower gap: An important barrier against reduction of the treatment gap of epilepsy[END_REF]. This is one of the rare achievements since there aren"t many countries where a formal provincial/national program on epilepsy has been, or is, running. Interestingly, in case of Cambodia, it took merely three years to progress from conducting a first-ever prevalence survey to starting a formal provincial program on epilepsy. Also, for the first time, a new strategy named "domestic health visiting" has been devised and is also being tested to reach epilepsy patient population in a standard, organized, professional and a regular manner in two Asian countries [START_REF] Bhalla | Manpower gap: An important barrier against reduction of the treatment gap of epilepsy[END_REF].

Capacity-building:

This is one of their most important contributions towards improvement of the healthcare system of recipient countries. Apart from extensive teaching activities at various home institutions, they have raised a whole new generation of researchers, neurologists, and epidemiologists in the last three decades; most of whom are working in their home countries. As an example, where none of the neurologists existed in Cambodia fifteen years ago, today seven neurologists and one neuro-rehabilitation specialist are available in Cambodia [START_REF] Bhalla | Epilepsy in Asia: A Cambodian Experience[END_REF]. Besides this, they have also trained several provincial practitioners (primary health-center staff and general practitioners) in several African and Asian countries; many of such training programs are currently ongoing as well [START_REF] Bhalla | Epilepsy in Asia: A Cambodian Experience[END_REF].

Miscellaneous:

In another valuable contribution, they were instrumental in conducting a threecountry survey on multiple sclerosis (MS) that came out with extremely novel findings on the risk and prevention of MS [START_REF] Dalmay | Multiple sclerosis and solar exposure before the age of 15 years: case-control study in Cuba, Martinique and Sicily[END_REF]. In particular, outdoor leisure activities, in addition to sun exposure was for the first-time found to be associated with a reduced risk of MS, with an evidence of dose response. This survey had received much appreciation from the experts working in the field of MS.

Low-income countries are rarely taken as a priority location for conducting events of advocacy and professional and academic exchange. As an example, a parent body on epilepsy has conducted only four congresses in a low-income location since 1909 and none at a low-income location in the last ten years. In contrast, due to their efforts, low-income locations have been taken "as a priority" to conduct such events; such as the ones in Cambodia, Vietnam and recently in Paris, France in which experts from 16 low-income countries (Asia, Africa, Latin America) were specifically invited and given travel bursaries to participate. Another such event is currently being organized in Varetz, France and experts from several low-income countries have been specifically

given travel bursaries to participate. Such events are important for advocacy, direct participation of public and private stakeholders, and motivation as well as encouragement of local expertise.

They have also been extremely active on Amyotrophic lateral sclerosis (ALS), created a first-ever register in France, and one of the only three such efforts in Europe [START_REF] Marin | Can mortality data be used to estimate amyotrophic lateral sclerosis incidence?[END_REF]. Their institute is also France"s sole ALS expert center. They have been one of the few research groups to have actively utilized geoepidemiological tools in ALS research to identify agrregate zones of ALS in France. They have been one of the few sources of generating knowledge on ALS from Africa and have, since long, established an active consortium of African neurologists and researchers working on ALS, called TROPALS (Study of ALS under the tropics; www.tropals.unilim.fr/ ). Several nutritional factors and environmental toxins have been identified that serve as risk, prognostic and diagnostic factors for ALS.

Due to space constraint, many of their contributions are not discussed here in details, for instance (a) facilitating programs of professional and academic exchange [START_REF] Bhalla | Epilepsy in Asia: A Cambodian Experience[END_REF], (b) prioritizing silent diseases and silent countries mostly (e.g. ALS in Africa, MS in Cuba and Martinique, countries like Mali, Martinique, Burundi, Cambodia, etc.), (c) contribution in the development of "early neurology" in Africa (in 1960s), (d) development of time-tested public-private partnerships that are often crucial for sustaining research-action programs, (e) treatment programs on epilepsy that continues to contribute to bring people out of epilepsy shadow in many African and Asian countries. Very recently, introduction of "new" epilepsy service providers (i.e.

primary health center staff) in Asia

Giving scientific platform and international visibility An international award for principal investigator from Gabon (for the first time in Africa)

Appreciation of local tropical expert by the President of his country

As a priority, conduct/organize several international manifestations in low-income locations, with particular participation of tropical experts from Africa, Asia and Latin America.

Figure 1 :Figure 2 :

 12 Figure 1: Photo (Prof Michel Dumas, permission obtained to use and publish photo)

Table 1 : Summary of all relevant contributions

 1

	Dementia	Only source of knowledge on dementia from central African
		countries
		Tool to determine accurate age of dementia subjects identified
		Psychosocial factors important in the survival of demential subjects
		identified
	Human T-lymphotropic virus	Fill "knowledge gaps" on epidemiological aspects of HTLV-1 in West
	type-1	Africa; correlation of HTLV-1 with spastic paraparesis, concomitant
		infections, as well as with lifestyle, environmental and geographic
		factors.
		Validation of a simple model to detect small clusters of infection
	Central Nervous System	Fill "knowledge gaps" on burden, epidemiology, and their correlation
	infections	with epilepsy, particularly onchocerciasis, cysticercosis and
		appropriate trypanocidal therapies for sleeping sickness (SS),
		regulatory role of several antibodies and cytokines, as well as
		development of validated models for SS.
	Epilepsy	Correlation with malaria and malnutrition
		Screening of epilepsy questionnaire for tropical populations
		Authoritative estimate of the prevalence of epilepsy in Asia and sub-
		Saharan Africa
		"Progression" from a prevalence survey to a provincial program on
		epilepsy in Cambodia, in merely three calendar years
		Design and validation of epidemiological tools on many psychosocial
		parameters, which didn"t exist before
		A reliable estimation of the annual requirement of two anti-epileptic
		drugs in a country
		Validation of reproductive causality of epilepsy
		Estimation of the preventability of epilepsy, for first-time in Asia,
		Recognition of activities on epilepsy in Asia "as a model for the
		investigation of epilepsy in developing countries"
	Capacity building	Neurologists and neurorehabilitation specialists, where none existed
		Epidemiologists, neuroepidemiologists, Public Health specialists,

Conflicts of interest statements

No conflicts of interest to declare.

Role of funding source

None

Ethics committee approval

Not applicable. I also confirm that I have read the Journal"s position on issues involved in ethical publication and affirm that this report is consistent with those guidelines.