Sébastien Ferré
email: ferre@irisa.fr

Alice Hermann
email: alice.hermann@irisa.fr

Semantic Search: Reconciling Expressive Querying and Exploratory Search

Faceted search and querying are two well-known paradigms to search the Semantic Web. Querying languages, such as SPARQL, offer expressive means for searching RDF datasets, but they are difficult to use. Query assistants help users to write well-formed queries, but they do not prevent empty results. Faceted search supports exploratory search, i.e., guided navigation that returns rich feedbacks to users, and prevents them to fall in dead-ends (empty results). However, faceted search systems do not offer the same expressiveness as query languages. We introduce Query-based Faceted Search (QFS), the combination of an expressive query language and faceted search, to reconcile the two paradigms. In this paper, the LISQL query language generalizes existing semantic faceted search systems, and covers most features of SPARQL. A prototype, Sewelis (aka. Camelis 2), has been implemented, and a usability evaluation demonstrated that QFS retains the ease-of-use of faceted search, and enables users to build complex queries with little training.

Introduction

With the growing amount of available resources in the Semantic Web (SW), it is a key issue to provide an easy and effective access to them, not only to specialists, but also to casual users. The challenge is not only to allow users to retrieve particular resources (e.g., flights), but to support them in the exploration of a knowledge base (e.g., which are the destinations? Which are the most frequent flights? With which companies and at which price?). We call the first mode retrieval search, and, following Marchionini [START_REF] Marchionini | Exploratory search: from finding to understanding[END_REF], the second mode exploratory search. Exploratory search is often associated to faceted search [START_REF] Hearst | Finding the flow in web site search[END_REF][START_REF]Dynamic taxonomies and faceted search. The information retrieval series[END_REF], but it is also at the core of Logical Information Systems (LIS) [START_REF] Ferré | A file system based on concept analysis[END_REF][START_REF] Ferré | Camelis: a logical information system to organize and browse a collection of documents[END_REF], and Dynamic Taxonomies [START_REF] Sacco | Dynamic taxonomies: A model for large information bases[END_REF]. Exploratory search allows users to find information without a priori knowledge about either the data or its schema. Faceted search works by suggesting restrictions, i.e., selectors for subsets of the current selection of items. Restrictions are organized into facets, and only those that share items with the current selection are suggested. This has the advantage to provide guided navigation, and to prevent dead-ends, i.e., empty selections. Therefore, faceted search is easy-to-use and safe: easy-to-use because users only have to choose among the suggested restrictions, and safe because, whatever the choice made by users, the resulting selection is not empty. The selections that can be reached by navigation correspond to queries that are generally limited to conjunctions of restrictions, possibly with negation and disjunction on values. This is far from the expressiveness of query languages for the semantic web, such as SPARQL 3 . There are semantic faceted search that extend the expressiveness of reachable queries, but still to a small fragment of SPARQL (e.g., SlashFacet [START_REF] Hildebrand | /facet: A browser for heterogeneous semantic web repositories[END_REF], BrowseRDF [START_REF] Oren | Extending faceted navigation to RDF data[END_REF], SOR [START_REF] Lu | SOR: A practical system for ontology storage, reasoning and search (demo)[END_REF], gFacet [START_REF] Heim | Facet graphs: Complex semantic querying made easy[END_REF]). For instance, none of them allow for cycles in graph patterns, unions of complex graph patterns, or negations of complex graph patterns.

Querying languages for the semantic web are quite expressive but are difficult to use, even for specialists. Users are asked to fill an empty field (problem of the writer's block), and nothing prevents them to write a query that has no answer (dead-end). Even if users have a perfect knowledge of the syntax and semantics of the query language, they may be ignorant about the data schema, i.e., the ontology. If they also master the ontology or if they use a graphical query editor (e.g., SemanticCrystal [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF], SCRIBO Graphical Editor4 ) or an auto-completion system (e.g., Ginseng [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF]) or keyword query translation (e.g., Hermes [START_REF] Tran | Hermes: Data web search on a pay-as-you-go integration infrastructure[END_REF]), the query will be syntactically correct and semantically consistent w.r.t. the ontology but it can still produce no answer.

The contribution of this paper, Query-based Faceted Search (QFS), is to define a semantic search that is (1) easy to use, (2) safe, and (3) expressive. Easeof-use and safeness are retained from existing faceted search systems by keeping their general principles, as well as the visual aspect of their interface. Expressiveness is obtained by representing the current selection by a query rather than by a set of items, and by representing navigation links by query transformations rather than by set operations (e.g., intersection, crossing). In this way, the expressiveness of faceted search is determined by the expressiveness of the query language, rather than by the combinatorics of user interface controls. In this paper, the query language, named LISQL, generalizes existing semantic faceted search systems, and covers most features of SPARQL. The use of queries for representing selections in faceted search has other benefits than navigation expressiveness. The current query is an intensional description of the current selection that complements its extensional description (list of items). It informs users in a precise and concise way about their exact position in the navigation space. It can easily be copied and pasted, stored and retrieved later. Finally, it allows expert users to modify the query by hand at any stage of the navigation process, without loosing the ability to proceed by navigation.

The paper is organized as follows. Section 2 discusses the limits of set-based faceted search by formalizing the navigation from selection to selection. Section 3 introduces LISQL queries and their transformations. In Section 4, navigation with QFS is formalized and proved to be safe and complete w.r.t. LISQL, and efficient. Section 5 reports about a usability evaluation, and Section 6 concludes.

Limits of Set-based Faceted Search

The principle of faceted search [START_REF]Dynamic taxonomies and faceted search. The information retrieval series[END_REF] is to guide users from selection of items to selection of items. At each navigation step, a new selection is derived by applying a set operation between the current selection S and a restriction R. A restriction is a feature that applies to at least one item of the current selection, i.e., S ∩ R = ∅. Typically, a feature is a pair facet-value, and the set operation is intersection: S := S ∩ R. The new selection is the set of items that belong to the current selection, and that belong to the restriction. Extensions of faceted search may allow for the exclusion of a restriction (S := S \ R), or the union with a restriction (S := S ∪ R). Restrictions can also be tags or item names.

In the context of the Semantic Web, items and values are resources, facets are properties, and tags are classes. Because of the relational nature of semantic data, new kinds of restrictions and set operations have been introduced in semantic faceted search (e.g., /facet [START_REF] Hildebrand | /facet: A browser for heterogeneous semantic web repositories[END_REF], BrowseRDF [START_REF] Oren | Extending faceted navigation to RDF data[END_REF], SOR [START_REF] Lu | SOR: A practical system for ontology storage, reasoning and search (demo)[END_REF], gFacet [START_REF] Heim | Facet graphs: Complex semantic querying made easy[END_REF]). A restriction can be the set of items that are subject of some property (the domain of the property), or that are object of some property (the range of the property) (e.g., BrowseRDF). A facet can be defined as a path of properties. Finally, a property p can be crossed forwards (S := p(S, .)) or backwards (S := p(., S)) (e.g., /facet, SOR, gFacet).

Both in theory and in practice, it is useful to distinguish between syntax and semantics. For example, we should distinguish between a pair facet-value (syntax), and the set of items it matches (semantics). In the following table, we define the syntax and semantics of the various kinds of restrictions: r denotes any RDF resource (URI, literal), c denotes a RDFS class, p denotes a RDF property, and S 0 denotes the set of all items (possibly all resources of a RDF dataset). This grammar already defines a rich language of accessible queries, but it has strong limits in terms of flexibility and expressivity, as we discuss now. To reach some selections requires a precise ordering in navigation steps, which hinders the flexibility of the search, and assumes that the user has a clear idea of his query in advance. For example, to reach the query father of (mother of (name : "John") and name : "Jane"), the user has first to select name : "John" (people named John), then to cross forward mother (their mothers), then to intersect with name : "Jane" (. . . whose name is Jane), and finally to cross forward father (their fathers). Any other ordering will fail; starting from the expected result (grand-fathers) will lead to the set of grand-children instead.

Some useful selections that can be defined in terms of set operations are not reachable by set-based faceted search. For example, the following kinds of selections are not reachable: unions of complex selections. e.g., (R 1 ∩ R 2 ) ∪ (R 3 ∩ R 4 ); or intersection of crossings from complex selections, e.g., p 1 (., R 1 ∩ R 2 ) ∩ p 2 (., R 3 ∩ R 4 ). Note that a selection S 1 ∩ p(., S 2 ) cannot in general be obtained by first navigating to S 1 , then crossing forwards p, navigating to S 2 , and finally crossing backwards p, because it is not equivalent to p(., p(S 1 , .) ∩ S 2 ) unless p is inverse functional. Therefore, not all combinations of intersection, union, and crossing are reachable, which is counter-intuitive and limiting for end users.

Existing approaches to semantic faceted search often have additional limitations, which are sometimes hidden behind a lack of formalization. A same facet (a property path) cannot be used several times, which is fine for functional properties but not for relations such as "child": p(., f 1 ∩ f 2 ) is reachable but not p(., f 1 )∩p(., f 2 ) (e.g., BrowseRDF, gFacet). A property whose domain and range are the same cannot be used as a facet (e.g., /facet), which includes all family and friend relationships for instance.

Expressive Queries and their Transformations

The contribution of our approach, Query-based Faceted Search (QFS), is to significantly improve the expressivity of faceted search, while retaining its properties of safeness (no dead-end), and ease-of-use. The key idea is to define navigation steps at the syntactic level as query transformations, rather than at the semantic level as set operations. The navigation from selection to selection, as well as the computation of restrictions related to the current selection, are retained by defining the semantics of features and queries, i.e., the mapping from a feature f or a query q to a set of items: R = items(f ) and S = items(q). Transformations at the syntactic level are necessary because there exist useful navigation steps that cannot be obtained by applying set operations on the current selection. For example, given S = R 1 ∩ R 2 , the set of items S ′ = R 1 ∩ (R 2 ∪ R 3 ) cannot be derived from S and R 3 . On the contrary, the query f 1 and (f 2 or f 3 ) can be derived from the query f 1 and f 2 and the feature f 3 because enough information is retained at the syntactic level.

In this section, we generalize in a natural way the set of queries compared to Section 2. This defines a query language, which we call LISQL (LIS Query Language). We then define a set of query transformations so that every LISQL query can be reached in a finite sequence of such transformations. This is in contrast with previous contributions in faceted search that introduce new selection transformations, and leave the query language implicit. We think that making the language of reachable queries explicit is important for reasoning on and comparing different faceted search systems. In Section 3.3, we give a translation from LISQL to SPARQL, the reference query language of the Semantic Web. This provides both a way to compute the answers of queries with existing tools, and a way to evaluate the level of expressivity achieved by LISQL.

The LIS Query Language (LISQL)

A more general query language, LISQL, can be obtained simply by merging the syntactic categories of features and queries in the grammar of Section 2, so that every query can be used in place of a feature.

Definition 1 (LISQL queries). The syntax and semantics of the LISQL constructs is defined in the following table, where r is a resource, c is a class, p is a property, S 0 is the set of all items, and q 1 , q 2 are LISQL queries s.t. S 1 = items(q 1 ) and S 2 = items(q 2 ). query syntax (q) semantics (items(q)) resource r {r} class a c rdf:type(., {c}) all ? S 0 crossing backwards p : q 1 p(., S 1 ) crossing forwards p of q 1 p(S 1 , .)

complement not q 1 S 0 \ S 1 intersection q 1 and q 2 S 1 ∩ S 2 union q 1 or q 2 S 1 ∪ S 2
The definition of LISQL allows for the arbitrary combination of intersection, union, complement, and crossings. In order to further improve the expressiveness of LISQL from tree patterns to graph patterns, we add variables (e.g., ?X) as an additional construct. Variables serve as co-references between distant parts of the query, and allows for the expression of cycles. For example, the query that selects people who are an employee of their own father can be expressed as a person and father : ?X and employee of ?X, or alternately as a person and ?X and employee of father of ?X. The semantics of queries with variables is given with the translation to SPARQL in Section 3.3, because it cannot be defined like in the table of Definition 1.

Syntactic constructs are given in increasing priority order, and brackets are used in concrete syntax for disambiguation. The most general query ? is a neutral element for intersection, and an absorbing element for union. In the following, we use the example query q ex = a person and birth : (year : (1601 or 1649) and place : (?X and part of England)) and father : birth : place : not ?X, which uses all constructs of LISQL, and selects the set of "persons born in 1601 or 1649 at some place in England, and whose father is born at another place".

Query Transformations

We have generalized the query language by allowing complex selections in place of restrictions: e.g., S 1 ∩ S 2 instead of S ∩ R. However, because the number of suggested restrictions in faceted search must be finite, it is not possible to suggest arbitrarily complex restrictions. More precisely, the vocabulary of features must be finite. In QFS, we retain the same set of features as in Section 2, which is a finite subset of LISQL for any given dataset.

The key notion we introduce to reconcile this finite vocabulary, and the reachability of arbitrary LISQL queries is the notion of focus in a query.

Definition 2 (focus).

A focus of a LISQL query q is a node of the syntax tree of q, or equivalently, a subquery of q. The set of foci of q is noted Φ(q); the root focus corresponds to the root of the syntax tree, and represents the whole query. The subquery at focus φ ∈ Φ(q) is noted q[φ]; and q[φ := q 1 ] denotes the modified query q, where the subquery at focus φ has been replaced by q 1 .

In the following, when it is necessary to refer to a focus in a query, the corresponding subquery is underlined with the focus name as a subscript, like in mother of ? φ . Foci are used in QFS to specify on which subquery a query transformation should be applied. For example, the query (f 1 and f 2 ) or (f 3 and f 4 ) can be reached from the query (f 1 and f 2 ) or f 3 by applying the intersection with restriction f 4 to the subquery f 3 , instead of to the whole query. Similarly, the query p 1 : (f 1 and f 2 ) and p 2 : (f 3 and f 4 ) can be reached by applying the intersection with restriction f 4 to the subquery f 3 . This removes the problem of unreachable selections in set-based faceted search presented in Section 2. Moreover, this removes the need for a strategy in the ordering of navigation steps. For example, the query a woman and mother of name : "John" can be reached by first selecting a woman, then by selecting mother of ? φ , then by inserting name : "John" at the focus φ. Definition 3 (query transformation). The different kinds of LISQL query transformations are listed in the following table, where each transformation is paramaterized by a focus φ and a query q 1 . The expression q[t] is the query that results from the application of transformation t to query q. transformation notation (t) result query (q[t]) intersection φ and q 1 q[φ := q[φ] and q 1 ] exclusion φ and not q 1 q[φ := q[φ] and not

q 1 ] union φ or q 1 q[φ := q[φ] or q 1 ]
We show in the following equations how the intersection with an arbitrary LISQL query can be recursively decomposed into a finite sequence of intersections with features, and exclusions and unions with the most general query ?.

q[φ and (?)]

= q q[φ and (p : q 1 )]

= q[φ and p : ? φ1 ][φ 1 and q 1 ] q[φ and (p of q 1 )] = q[φ and p of ? φ1 ][φ 1 and q 1 ] q[φ and (not q 1 )]

= q[φ and not ? φ1 ][φ 1 and q 1 ] q[φ and (q 1 and q 2 )] = q[φ and q 1φ1 ][φ 1 and q 2 ] q[φ and (q 1 or q 2 )] = q[φ and q 1φ1 ][φ 1 or ? φ2 ][φ 2 and q 2 ] For example, the complex query q ex = a person and birth : (year : (1601 or 1649) and place : (?X and part of England)) and father : birth : place : not ?X can be reached through the navigation path: Sequences of query transformations are analogous to the use of graphical query editors, but the key difference is that answers and restrictions are returned at each step, providing feedback, understanding-at-a-glance, no dead-end, and all benefits of exploratory search. Despite the syntax-based definition of navigation steps, those have a clear semantic counterpart. Intersection is the same as in standard faceted search, only making it available on the different entities involved in the current query. In the above example, intersection is alternately applied to the person, his birth, his birth's place, his father, etc. The set of relevant restrictions is obviously different at different foci. The union transformation introduces an alternative to some subquery (e.g., an alternative birth's year). The exclusion transformation introduces a set of exceptions to the subquery (e.g., excluding some father's birth's place). In Section 4, we precisely define which query transformations are suggested at each navigation step, and we prove that the resulting navigation graph is safe (no dead-end), and complete (every "safe" query is reachable).

? φ0 [

Translation to and Comparison with SPARQL

We here propose a (naive) translation of LISQL queries to SPARQL queries. It involves the introduction of variables that are implicit in LISQL queries. As this translation applies to LISQL queries with co-reference variables, it becomes possible to compute their set of items.

Definition 4 (SPARQL translation). The SPARQL translation of a LISQL query q is sparql (q) = SELECT DISTINCT ?x WHERE { S 0 (x) GP (x, q) }, where the graph pattern S 0 (x) binds x to any element of the set of all items S 0 , and the function GP inductively defines the graph pattern of q with variable x representing the root focus.

GP (x, ?v)

= S 0 (v) FILTER (?x = ?v) GP (x, r) = FILTER (?x = r) GP (x, a c) = ?x rdf:type c GP (x, p : q 1 ) = ?x p ?y. GP (y, q 1 ) where y is a fresh variable GP (x, p of q 1 ) = ?y p ?x. GP (y, q 1 ) where y is a fresh variable GP (x, ?) = { } GP (x, not q 1 ) = NOT EXISTS { GP (x, q 1 ) } GP (x, q 1 and q 2 ) = GP (x, q 1 ) GP (x, q 2 ) GP (x, q 1 or q 2 ) = { GP (x, q 1 ) } UNION { GP (x, q 2 ) }

We now discuss the translations of LISQL queries compared to SPARQL in general. They have only one variable in the SELECT clause because of the nature of faceted search, i.e., navigation set to set. From SPARQL 1.0, LISQL misses the optional graph pattern, and the named graph pattern. Optional graph patterns are mostly useful when there are several variables in the SELECT clause. LISQL has the NOT EXISTS construct of SPARQL 1.1. If we look at the graph patterns generated for intersection and union, the two subpatterns necessarily share at least one variable, x. This is a restriction compared to SPARQL, but one that makes little difference in practice as disconnected graph patterns are hardly useful in practice.

A Safe and Complete Navigation Graph

In this section, we formally define the navigation space over a RDF dataset as a graph, where vertices are navigation places, and edges are navigation links. A navigation place is made of a query q and a focus φ of this query. The focus determines the selection of items to be displayed, and the corresponding restrictions at this focus. A navigation link is defined by a query transformation and, possibly, a focus move. Before defining the navigation graph itself, we first define the set of items and the set of restrictions for some query q and some focus φ ∈ Φ(q). The set of items is defined as the set of items of the query flip(q, φ) that is the reformulation of q from the point of view of the focus φ. For example, the reformulation, called the flip, of the query a woman and mother of name : "John" φ is the query name : "John" and mother : a woman. Definition 5 (flip at focus). The flip of a query q at a focus φ ∈ Φ(q) is defined as flip(q, φ) = flip ′ (?, q, φ), where the function flip ′ (k, q ′ , φ) is inductively defined, with k representing the context of q ′ in q, by (only main cases are given):

flip(k, p : q 1 , φ) = flip(p of k, q 1 , φ) if φ ∈ q 1 flip(k, q 1 and q 2 , φ) = flip(k and q 2 , q 1 , φ) if φ ∈ q 1 flip(k, q 1 or q 2 , φ) = flip(k, q 1 , φ) if φ ∈ q 1 flip(k, not q 1 , φ) = flip(k, q 1 , φ) if φ ∈ q 1 flip(k, q ′ , φ)
= q ′ and k otherwise

When the focus is in the scope of an union, only the alternative that contains the focus is used in the flipped query. This is necessary to have the correct set of restrictions at that focus, and this is also useful to access the different subselections that compose an union. For example, in the query a man and (firstname : "John" φ or lastname : "John"), the focus φ allows to know the set of men whose firstname is John without forgetting the second alternative. When the focus is in the scope of a complement, this complement is ignored in the flipped query. This is useful to access the subselection to be excluded. For example, in the query a man and not father : ? φ , the focus φ allows to know the set of men who have a father, i.e., those who are to be excluded from the selection of men.

Definition 6 (items at focus). items of a query q at focus φ is defined as the items of the flip of q at focus φ, i.e., items(q, φ) = items(flip(q, φ)).

This enables the definition of the set of restrictions at each focus in the normal way. The navigation graph can then be formally defined.

Definition 7 (restrictions at focus). The restrictions of a query q at focus φ is defined as the features that share items with the query q at focus φ:

restr (q, φ) = {f | items(q, φ) ∩ items(f ) = ∅}.
Definition 8 (navigation graph). Let D be a RDF dataset. The navigation graph G D = (V, E) of D has its set of vertices defined by

V = {(q, φ) | q ∈ LISQL, φ ∈ Φ(q)},
and its set of edges defined by the following table for every vertice (q, φ). The notation (q ′ , φ ′ ) = (q, φ)[l] denotes the navigation place obtained by traversing the navigation link l from the navigation place (q, φ). navigation link notation (l) target ((q ′ , φ ′ )) conditions focus change focus φ ′ (q, φ ′ ) for every focus φ ′ ∈ Φ(q) intersection and f (q[φ and f φ ′ ], φ ′ ) for every f ∈ restr (q, φ) exclusion and not ? (q[φ and not ? φ ′ ], φ ′ ) union or ?

(q[φ or ? φ ′ ], φ ′ ) name name ?v (q[φ and ?v φ ′ ], φ ′ ) for some fresh variable v reference ref ?v (q[φ and ?v φ ′ ], φ ′ ) for every v ∈ vars(q) s.t. items(q ′ , φ ′ ) = ∅ delete delete (q[φ := ?], φ)

The number of navigation places (vertices) is infinite because there are infinetely many LISQL queries, but the number of outgoing navigation links (edges) is finite at each navigation place because the vocabulary of features is finite, and the number of foci and variables in a query is finite. By default, the initial navigation place is v 0 = (? φ , φ). The following lemma shows that intersection navigation links behave as in standard faceted search. Lemma 1. For every query q, focus φ ∈ Φ(q), and feature f , the following equality holds: items((q, φ)[and f ]) = items(q, φ) ∩ items(f ).

Safeness and Completeness

From the formal definition of navigation graphs, we can now formally state safeness and completeness theorems. Those theorems have subtle conditions w.r.t. focus change, and the main purpose of this section is to discuss them. For reasons of space, lemmas and proofs have been removed, but they are fully available in a research report [START_REF] Ferré | Semantic faceted search: Safe and expressive navigation in RDF graphs[END_REF] (the presentation is slightly different but equivalent).

Theorem 1 (safeness). Let D be a RDF dataset. The navigation graph G D is safe except for some focus changes, i.e., for every path of navigation links without focus change from (q, φ) to (q ′ , φ ′ ), items(q, φ) = ∅ implies items(q ′ , φ ′ ) = ∅.

We justify to allow for unsafe focus changes by considering the following navigation scenario. The current query has the form q = f 1 or f 2φ , i.e., the union of two restrictions. The feature f 3 is a restriction of q such that items(f 2 )∩ items(f 3 ) = ∅, i.e., only items of f 1 match f 3 . The intersection with f 3 leads to the query q ′ = (f 1 or f 2 ) and f 3φ ′ , and a focus change on f 2 leads to an empty selection. We could prevent intersection with f 3 but this would be counter-intuitive because it is a valid restriction for (q, φ). We could simplify the query q ′ by removing the second alternative f 2 (q ′ = f 1 and f 3 ), or forbid the focus change, but we think users should have full control on the query they have built. Finally, allowing for the unsafe focus change is a simple way to inform users that no item of f 2 matches the new restriction feature f 3 .

Theorem 2 (completeness). Let D be a RDF dataset. The navigation graph G D is complete except for some queries having an unsafe focus change, i.e., for every query q s.t. for every φ ∈ P hi(q), items(q, φ) = ∅, there is a navigation path from v 0 to the navigation place (q φ , φ).

In the above scenario, it was possible to navigate to (f 1 or f 2 ) and f 3 that has an unsafe focus change on f 2 , but it is not possible to navigate to the equivalent f 3 and (f 1 or f 2 ) because f 2 / ∈ restr (f 3 and (f 1 or ? φ2 ), φ 2 ). Fortunately, a query that is not a dead-end but has unsafe focus changes can be simplified into an equivalent query (same set of items) without unsafe focus changes. It suffices to delete from the query empty alternatives (S ∪ ∅ = S), and empty exclusions (S \ ∅ = S).

Efficiency

Each navigation step from a navigation place (q, φ) requires the computation of the set of items items(q, φ), the set of restrictions restr (q, φ), and the set of navigation links as specified in Definition 8. In many cases, the set of items can be obtained efficiently from the previous set of items, and the last navigation link. If the last navigation link was an intersection, Lemma 1 shows that the set of items is the result of the intersection that is performed during the computation of restrictions, like in standard faceted search. For an exclusion or a naming, the set of items is unchanged. For a reference, the set of items was already computed at the previous step. Otherwise, for an union or a focus change, the set of items is computed with a LISQL query engines, possibly reusing existing query engines for the Semantic Web (see Section 3.3).

Computing the set of restrictions is equivalent to set-based faceted search, i.e., amounts to compute set intersections between the set of items and the precomputed set of items of features. The same datastructures and algorithms can therefore be used. As features are LISQL queries, their set of items can be computed like for queries, possibly with optimizations given features are simple queries. Finally, determining the set of navigation links requires little additional computation. A navigation link is available for each focus of the query (focus change), and each restriction (intersection). Three navigation links for exclusion, union, and naming are always available. Only for reference navigation links it is necessary, for each variable in the query, to compute the set of items of the target navigation place, in order to check it is not empty. This additional cost is limited as the number of variables in a LISQL query is very small in practice, and is bounded by the number of foci of the query.

Usability Evaluation

This section reports on the evaluation of QFS in terms of usability 5 . We have measured the ability of users to answer questions of various complexities, as well as their response times. Results are strongly positive and demonstrate that QFS offers expressiveness and ease-of-use at the same time.

Prototype. QFS has been implemented as a prototype, Sewelis6 (aka. Camelis 2). Figure 1 shows a screenshot of Sewelis. From top to bottom, and from left to right, it is composed of a menu bar (M), a toolbar (T), a query box (Q), query controls (QC), feature controls (FC), an answer list or extension box (E), a facet hierarchy (F), and a set of value boxes (V). A query engine can be derived from Sewelis by retaining only the components Q and E. A standard faceted search system can be derived by retaining only the components E, F, and V. Navigation links, i.e., suggested query transformations, are available on all components. Whenever a navigation control is triggered, the corresponding navigation link is applied, and components (Q,E,F,V) are refreshed accordingly. The query box (Q) is clickable for setting the focus on any subquery. Query controls (QC) provide buttons for naming, union, exclusion (and a few others). Every element of components (E,F,V) can be used as an argument for intersection, with the guarantee that the resulting query does have answers. Restriction are dispatched between components (E,F,V) according to their types. The facet hierarchy (F) contains variables of the current query (e.g., ?X), classes (e.g., a person), and property paths (e.g., father of ?, birth : year : ?). Each value box (V) contains a list or hierarchy of relevant values for some property path facet (e.g., father of 'George Washington', birth : year : 1601). The extension box (E) contains resources (e.g., England). The hierarchical organization of facets in (F) is based on RDFS class and property hierarchies. A value box (V) is hierarchically organized according to the last property of its property path, if that property is transitive (here, in = part of).

Dataset. The datasets were chosen so that subjects had some familiarity with the concepts, but not with the individuals. We found genealogical datasets about former US presidents, and converted them from GED to RDF. We used the genealogy of Benjamin Franklin for the training, and the genealogy of George Washington for the test. The latter describes 79 persons by their birth and/or death events, which are themselves described by their year and place, by their firstname, lastname, and sex, and by their relationships (father, mother, child, spouse) to other persons. Places are linked by a transitive part-of relationship, allowing for the display of place hierarchies in Sewelis.

Methodology. The subjects consisted of 20 graduate students in computer science. They had prior knowledge of relational databases but neither of Sewelis, nor of faceted search, nor of Semantic Web. None was familiar with the dataset used in the evaluation. The evaluation was conducted in three phases. First, the subjects learned how to use Sewelis through a 20min tutorial, and had 10 more minutes for free use and questions. Second, subjects were asked to answer a set Table 1. Questions of the test, by category, and the minimum number of navigation links to answer them. of questions, using Sewelis. We recorded their answers, the queries they built, and the time they spent on each question. Finally, we got feedback from subjects through a SUS questionnaire and open questions [START_REF] Brooke | SUS: A quick and dirty usability scale[END_REF]. The test was composed of 18 questions, with smoothly increasing difficulty. Table 1 groups the questions in 7 categories: the first 2 categories are covered by standard faceted search, while the 5 other categories are not in general. For category Visualization, the exploration of the facet hierarchy was sufficient. In category Selection, we asked to count or list items that have a particular feature. In category Path, subjects had to follow a path of properties. Category Disjunction required the use of unions. Category Negation required the use of exclusions. Category Inverse required the crossing of the inverse of properties. Category Cycle required the use of co-reference variables (naming and reference navigation links).

Results. Figure 2 shows the number of correct queries and answers, the average time spent on each question and the number of participants who had a correct query for at least one question of each category. For example, in category "Visualization", the first two questions had 20 correct answers and queries; the third question had 10 correct answers and 13 correct queries; all the 20 participants had a correct query for at least one question of the category; the average re-Fig. 2. Average time and number of correct queries and answers for each question sponse times were respectively 43, 21, and 55 seconds. The difference between the number of correct queries and correct answers is explained by the fact that some subjects forgot to set the focus on the whole query after building the query.

All subjects but one had correct answers to more than half of the questions. Half of the subjects had the correct answers to at least 15 questions out of 18. Two subjects answered correctly to 17 questions, their unique error was on a disjunction question for one and on a negation question for the other. All subjects had the correct query for at least 11 questions. For each question, there is at least 50 percent of success. The subjects spent an average time of 40 minutes on the test, the quickest one spent 21 minutes and the slowest one 58 minutes.

The first 2 categories corresponding to standard faceted search, visualization and selection, had a high success rate (between 94 and 100) except for the third question. The most likely explanation for the latter is that the previous question was so simple (a man) that subjects forgot to reset the query between the questions 2 and 3. All questions of the first two categories were answered in less than 1 minute and 43 seconds on average. Those results indicate that the more complex user interface of QFS does not entail a loss of usability compared to standard faceted search for the same tasks.

For other categories, all subjects but two managed to answer correctly at least one question of each category. Within each category, we observed that response times decreased, except for the Cycle category. At the same time, for Path, Disjunction and Inverse, the number of correct answers and queries increased. Those results suggest a quick learning process of the subjects. The decrease in category Negation is explained by a design flaw in the interface. For category Cycle, we conjecture some lassitude at the end of the test. Nevertheless, all but two subjects answered correctly to at least one of Cycle questions. The peak of response time in category Inverse is explained by the lack of inverse property examples in the tutorial. It is noticeable that subjects, nevertheless, managed SUS Question Score (on a 0-4 scale) I think that I would like to use this system frequently 2.8 Agree I found the system unnecessarily complex 0.8 Strongly disagree I thought the system was easy to use 2.6 Agree I think that I would need the support of a technical person to be able to use this system 1.5 Disagree I found the various functions in this system were well integrated 2.9 Agree I thought there was too much inconsistency in this system 0.6 Strongly disagree I would imagine that most people would learn to use this system very quickly 2.5 Agree I found the system very cumbersome to use 1.0 Disagree I felt very confident using the system 2.8 Agree I needed to learn a lot of things before I could get going with this system 1.7 Neutral Table 2. Results of SUS questions.

to solve the Inverse questions with a reasonable success rate, and a decreasing response time. SUS Questionnaire. Table 2 shows the answers to the SUS questions, which are quite positive. The first noticeable thing is that, despite the relative complexity of the user interface, subjects do not find the system unnecessarily complex nor cumbersome to use. We think this is because the principles of QFS are very regular, i.e., they follow few rules with no exception. The second noticeable thing, which may be a consequence of the first, is that subjects felt confident using the system and found no inconsistency. Finally, even if it is necessary for subjects to learn how to use the system, they thought that the system was easy to use, and that they would learn to use it very quickly. The results of the test demonstrate that they are right, even for features that were not presented in the tutorial (the Inverse category).

Conclusion

We have introduced Query-based Faceted Search (QFS) as a search paradigm for Semantic Web knowledge bases, in particular RDF datasets. It combines most of the expressiveness of the SPARQL query language, and the benefits of exploratory search and faceted search. The user interface of QFS includes the user interface of other faceted search systems, and can be used as such. It adds a query box to tell users where they are in their search, and to allow them to change the focus. It also adds a few controls for applying some query transformations such as the insertion of disjunction, negation, and variables.

QFS has been implemented as a prototype, Sewelis. Its usability has been demonstrated through a user study, where, after a short training, all subjects were able to answer simple questions, and most of them were able to answer complex questions involving disjunction, negation, or co-references. This means QFS retains the ease-of-use of other faceted search systems, and gets close to the expressiveness of query languages such as SPARQL.

Fig. 1 .

 1 Fig. 1. A screenshot of the user interface of Sewelis. It shows the selection of male persons whose lastname is Washington.

  The syntactic form of restrictions are features. The syntactic form of selections are queries whose answers are sets of items, i.e., subsets of S 0 . The above tables implicitly define a grammar for features and queries: S → ? | S and R | S and not R | S or R | p : S | p of S R → r | a c | p : r | p of r | p : ? | p of ?.

	restriction	syntax semantics	examples
	name	r	{r}		<JohnSmith>, "John", 2011
	tag	a c	rdf:type(., {c}) a person
	(facet, value) p : r p(., {r})		year : 2011
	(facet, value) p of r p({r}, .)		mother of <JohnSmith>
	domain	p : ? p(., S 0 )		year : ?
	range	p of ? p(S 0 , .)		mother of ?
	The same distinction can be made for complex selections, and we introduce in
	the following table a syntax for the various set operations that can be applied
	between selections and restrictions: S denotes a selection, and R denotes a re-
	striction that is relevant to S: i.e., S ∩ R = ∅.
		selection		syntax	semantics
		initial		?	S 0
		intersection	S and R	S ∩ R
		exclusion		S and not R S \ R
		union		S or R	S ∪ R
		crossing backwards p : S	p(., S)
		crossing forwards p of S	p(S, .)

  φ 0 and a person] [φ 0 and birth : ? φ1 ] [φ 1 and year : 1601 φ2 ] [φ 2 or ? φ3 ] [φ 3 and 1649] [φ 1 and place : ? φ4 ] [φ 4 and ?X] [φ 4 and part of England] [φ 0 and father : ? φ5 ] [φ 5 and birth : ? φ6 ] [φ 6 and place : ? φ7 ] [φ 7 and not ? φ8 ] [φ 8 and ?X]. The classical facet-value features appear to be redundant for navigation as their intersection can be decomposed, but they are still useful for visualization in a faceted search interface.

see http://www.w3.org/TR/rdf-sparql-query/

http://www.scribo.ws/xwiki/bin/view/Blog/SparqlGraphicalEditor

Details can be found on http://www.irisa.fr/LIS/alice.hermann/camelis2.html

See http://www.irisa.fr/LIS/softwares/sewelis/ for a presentation, screencasts, a Linux executable, and sample data.

Acknowledgments. We would like to thank the 20 students, from the University of Rennes 1 and the INSA engineering school, for their volunteer participation to the usability evaluation.

Category

Question (# navig. links) Visualization 1 How many persons are there? (0) 2 How many men are there? (0) 3 How many persons have a birth's place in the base? (0) 17 How many persons have the same firstname as one of their parent? (8) 18 Which persons were born the same year as their spouse? [START_REF] Marchionini | Exploratory search: from finding to understanding[END_REF]


Sébastien Ferré
email: ferre@irisa.fr

Alice Hermann
email: alice.hermann@irisa.fr

Mireille Ducassé
email: ducasse@irisa.fr

Combining Faceted Search and Query Languages for the Semantic Web

Faceted search and querying are the two main paradigms to search the Semantic Web. Querying languages, such as SPARQL, offer expressive means for searching knowledge bases, but they are difficult to use. Query assistants help users to write well-formed queries, but they do not prevent empty results. Faceted search supports exploratory search, i.e., guided navigation that returns rich feedbacks to users, and prevents them to fall in dead-ends (empty results). However, faceted search systems do not offer the same expressiveness as query languages. We introduce semantic faceted search, the combination of an expressive query language and faceted search to reconcile the two paradigms. The query language is basically SPARQL, but with a syntax that better fits in a faceted search interface. A prototype, Camelis 2, has been implemented, and a usability evaluation demonstrated that semantic faceted search retains the ease-of-use of faceted search, and enables users to build complex queries with little training.

Introduction

With the growing amount of available resources in the Semantic Web (SW), it is a key issue to provide an easy and effective access to them, not only to specialists, but also to casual users. The challenge is not only to allow users to retrieve particular resources (e.g., flights), but to support them in the exploration of a knowledge base (e.g., which are the destinations? Which are the most frequent flights? With which companies and at which price?). We call the first mode retrieval search, and, following Marchionini [START_REF] Marchionini | Exploratory search: from finding to understanding[END_REF], the second mode exploratory search. Exploratory search is often associated to faceted search [HEE + 02,ST09], but it is also at the core of Logical Information Systems [START_REF] Ferré | Camelis: a logical information system to organize and browse a collection of documents[END_REF], and Dynamic Taxonomies [START_REF] Sacco | Dynamic taxonomies: A model for large information bases[END_REF]. Exploratory search allows users to find information without a priori knowledge about either the data or its schema. Faceted search works by suggesting restriction values, i.e., selectors for subsets of the current selection of items. Restriction values are organized into facets, and only those that share items with the current selection are suggested. This has the advantage to remove the need to write queries, and to prevent dead-end queries, i.e., queries with no answer. Therefore, faceted search is easy and safe: easy because users only have to choose among the suggested restriction values, and safe because, whatever the choice made by users, the resulting selection is not empty. The selections that can be reached by navigation correspond to queries that are generally limited to conjunctions of restriction values, possibly with restricted negation and disjunction. This is far from the expressiveness of query languages for the semantic web, such as SPARQL1 . SlashFacet [START_REF] Hildebrand | /facet: A browser for heterogeneous semantic web repositories[END_REF] and BrowseRDF [START_REF] Oren | Extending faceted navigation to RDF data[END_REF] are faceted search systems for RDF data that extend the expressiveness of reachable queries, but still to a small fragment of SPARQL. For instance, both of them allow for neither cycles in graph patterns, nor unions of graph patterns (disjunction).

Querying languages for the semantic web, such as SPARQL [START_REF] Angles | The expressive power of SPARQL[END_REF], OWL-QL [START_REF] Fikes | OWL-QL -a language for deductive query answering on the semantic web[END_REF], or SPARQL-DL [START_REF] Sirin | SPARQL-DL: SPARQL query for OWL-DL[END_REF], are quite expressive but are difficult to use, even for specialists. They do not return enough feedback to offer exploratory search, and nothing prevents users to write a query that has no answer. Indeed, even if users have a perfect knowledge of the syntax and semantics of the query language, they may be ignorant about the data schema, i.e., the ontology. If they also master the ontology or if they use a query assistant (e.g., Protégé2 ) or an auto-completion system (e.g., Ginseng [START_REF] Bernstein | Querying the semantic web with Ginseng: A guided input natural language search engine[END_REF]), the query will be syntactically correct and semantically consistent w.r.t. the ontology but it can still produce no answer.

The contribution of this paper is to extend faceted search to the Semantic Web, so as to offer an exploratory search that is (1) easy to use, (2) safe, and (3) expressive. Ease-of-use and safeness are retained from existing faceted search systems by keeping their general principles, as well as the visual aspect of their interface. Expressiveness is obtained by representing the current selection by a query rather than by a set of items, and by representing navigation links by query transformations rather than by set operations (e.g., intersection). In this way, the expressiveness of faceted search is determined by the expressiveness of the query language, rather than by the combinatorics of user interface controls. In this paper, the query language is based on SPARQL graph patterns, but with a syntax that better fits in a faceted search interface: LISQL.

The use of queries for representing selections in faceted search has other benefits than navigation expressiveness. The current query is an intensional description of the current selection that complements its extensional description (listing of items). It informs users in a precise and concise way about their exact position in the navigation space. It can easily be copied and pasted, stored and retrieved later. Finally, it allows expert users to modify the query by hand at any stage of the navigation process, without loosing the ability to proceed by navigation.

The paper is organized as follows. Section 2 presents semantic faceted search, and illustrates it with our prototype implementation Camelis 2. Section 3 reports about a user study that demonstrates the usability of our approach. Our approach is also compared in Section 4 to other work in faceted search for the Semantic Web. Section 5 concludes this paper.

The principle of our approach, Semantic Faceted Search (SFS), is to reconcile querying and navigation. Navigation can be defined as moving from place to place through navigation links. In faceted search, a navigation place is a set of items, and a navigation link is the choice of a restriction value. In SFS, a navigation place is defined by a query, whose answers form the current set of items; and a navigation link is defined as a query transformation. The set of possible query transformations is designed to make it possible to build arbitrary queries. However, the set of navigation links is restricted to those query transformations that do not lead to empty results, like in standard faceted search. In the following, SFS is illustrated on genealogical datasets converted from GED files 3 .

Queries and Query Transformations

The reference query language for the Semantic Web is SPARQL. While its semantics is adequate to our needs, we find that its syntax is not best-suited to SFS. First, it makes it difficult to define query transformations, because it is not regular and compositional enough. Second, it tends to be verbose, and exhibits relational algebra operators, and a number of symbols that are alien to most people: e.g., UNION, &&.

We propose an alternative syntax, LISQL, for a large fragment of SPARQL. This fragment corresponds to unary queries, i.e., queries with only one variable in the SELECT clause. This restriction is not due to LISQL, but to the very definition of faceted search, where a navigation place is a set and not a relation. For reasons of space, we present LISQL and its query transformations through examples only. Full definitions can be found in a research report [START_REF] Ferré | Semantic faceted search: Safe and expressive navigation in rdf graphs[END_REF].

As an illustrating example covering all aspects of LISQL, we consider the task of retrieving, in the genealogy of George Washington, "every person that was born in 1601 or 1649 at some place in England, and some child of which was not born at the same place". In SPARQL, this query can be expressed as follows.

SELECT DISTINCT ?p WHERE {

?p a person. ?p birth ?b. ?b year ?y FILTER (?y=1601 || ?y=1649). ?b place ?X. ?X in England. ?c father ?p.

?c birth ?bc. ?bc place ?pc FILTER ?pc != ?X }

The same query can be expressed in LISQL as:

a person and birth : (year : (1601 or 1649) and place : (?X and in England)) and father of birth : place : not ?X.

A LISQL query is a LISQL expression, where some subexpression, the query focus, is underlined. LISQL expressions denote sets of items (RDF resources), and can be coordinated by Boolean operators that correspond to set operations: and for intersection, or for union, and not for complement. Atomic expressions can be individuals (e.g., 1601, England) that denote themselves as singleton sets, or classes (e.g., person) that denote their set of instances. The subexpression year : (1601 or 1649) is a restriction, made of the property year and of the subexpression, (1601 or 1649), and here denotes the set of events whose year is 1601 or 1649. The keyword (of) is used instead of (:) for the inverse reading of a property. The variable ?X is here used to refer to the birthplace of the father, whatever it is. A LISQL expression translates to a SPARQL graph pattern, using a variable for each entity. The query focus determines which of those variables is put in the SELECT clause. Therefore, the query a woman and father : ? denotes the women's fathers, and is equivalent to father of a woman. A focus is never ambiguous; however, two different foci can be equivalent, i.e., put the same variable in the SELECT clause, if they are conjunctively coordinated or associated to a same LISQL variable. LISQL variables therefore allow for cycles in the graph patterns. We present the different kinds of query transformations through a possible scenario for building the above query. Table 1 gives for each step the query transformations, and the resulting intermediate query. Most transformations apply to the query focus, letting the rest of the query unchanged. Transformation Reset resets the whole query to the most general query ?. Transformation And appends a given subexpression to the focus, connecting the two with and (? is a neutral element for and). When the focus is on the whole expression, this transformation corresponds to faceted search selection. Transformation Focus on moves the focus on a given subexpression. Transformation Cross is an abbreviation for a common navigation idiom: the And of a restriction followed by a Focus on the subexpression of the restriction. Transformation Name does the same as a And, but for a freshly generated variable. The And of the same variable at a later stage allows for the formation of cycles. Transformation Or introduces an alternative to the focus with the connector or. Transformation Not applies the connector not to the focus.

Only transformation And requires a LISQL expression to be passed. A set of expressions is suggested to the user so as to avoid dead-ends, and to allow for arbitrarily complex queries. It is sufficient to suggest individuals, variables already in the query, classes, and unqualified restrictions (e.g., father of ?) [START_REF] Ferré | Semantic faceted search: Safe and expressive navigation in rdf graphs[END_REF].

Faceted User Interface and Interaction

SFS has been implemented as a prototype, Camelis 24 . Figure 1 shows a screenshot of Camelis 2. From top to bottom, and from left to right, it is composed of a menu bar (M), a toolbar (T), a query box (Q), query controls (QC), feature controls (FC), an answer list or extension box (E), a facet hierarchy (F), and a set of value boxes (V). A query engine can be derived from Camelis 2 by retaining only the components Q and E. A standard faceted search system can be derived by retaining only the components E, F, and V. Navigation links, i.e., suggested query transformations, are available on all components. Whenever a navigation control is triggered, the corresponding query transformation is applied, and components (Q,E,F,V) are refreshed accordingly. The toolbar (T) has a button for Reset. The query box (Q) is clickable for setting the focus on any subexpression. Query controls (QC) provide buttons for Name, Or, Not (and a few others). Every element of components (E,F,V) can be used as an argument for And, with the guarantee that the resulting query does have answers; And is replaced by Cross for unqualified restrictions. The contents of components (E,F,V) play the role of restriction values in standard faceted search, and are here dispatched in the three components according to their type. The facet hierarchy (F) contains variables of the current query (e.g., ?X, classes (e.g., a person), and unqualified restrictions (e.g., father of ?, birth : year : ?). Value boxes (V) contain qualified restrictions with individuals as subexpressions (e.g., father of 'George Washington', birth : year : 1601), grouped by property path. The extension box (E) contains individuals (e.g., England). The hierarchical organization of facets in (F) is based on RDFS class and property hierarchies. A value box (V) is hierarchically organized according to the last property of its property path, if it is transitive (e.g, in).

Usability Evaluation

This section reports on the evaluation of Semantic Faceted Search in terms of usability5 . we have measured the ability of users to answer questions of various complexities, as well as their response times. Results are strongly positive and demonstrate that semantic faceted search offers expressiveness and ease-of-use at the same time.

Methodology. The subjects consisted of 20 graduate students in computer science. They had prior knowledge of relational databases but neither of Camelis 2, Figure2. Average time and number of correct queries and answers for each question nor of faceted search, nor of semantic web. None was familiar with the dataset used in the evaluation. The evaluation was conducted in three phases. First, the subjects learned how to use Camelis 2 through a 20min tutorial, and had 10 more minutes for free use and questions. Second, subjects were asked to answer a set of questions, using Camelis 2. We recorded their answers, the queries they built, and the time spent on each question.

The test was composed of 18 questions, with smoothly increasing difficulty. The questions can be grouped in 7 categories: the first 2 categories are covered by standard faceted search, while the 5 other categories are not in general. The first category, Visualization, did not require the creation of a query. The exploration of the facet hierarchy was sufficient: e.g., "How many men are there?". In the second category, Selection, we asked to count or list items that have a particular feature: e.g., "How many women are named Mary?". In the third category, Path, subjects had to follow a path of properties: e.g., "Which man is married with a woman born in 1708?". The fourth category, Disjunction, required to use disjunction: e.g., "Which women have for mother Jane Butler or Mary Ball?". The fifth category, Negation, required to use negation: e.g., "How many women have a mother whose death's place is not Warner Hall?". The sixth category, Inverse, required to use the inverse of a property: e.g., "Who was born in the same place as Robert Washington?". In the seventh category, Cycle, required the use of variables: e.g., "How many persons have the same firstname as one of their parent?".

Results. Figure 2 shows the number of correct queries and answers, the average time spent on each question and the number of participants who had a correct query for at least one question of each category. For example, in category "Visualization", the first two questions had 20 correct answers and queries; the third question had 10 correct answers and 13 correct queries; all the 20 participants had a correct query for at least one question of the category; the average re-sponse times were respectively 43, 21, and 55 seconds. The difference between the number of correct queries and correct answers is explained by the fact that some subjects forgot to set the focus on the whole query after building the query.

All subjects but one had correct answers to more than half of the questions. Half of the subjects had the correct answers to at least 15 questions out of 18. Two subjects answered correctly to 17 questions, their unique error was on a disjunction question for one and on a negation question for the other. All subjects had the correct query for at least 11 questions. For each question, there is at least 50 percent of success. The subjects spent an average time of 40 minutes on the test, the quickest one spent 21 minutes and the slowest one 58 minutes.

The first 2 categories corresponding to standard faceted search, visualization and selection, had a high success rate (between 94 and 100) except for the third question. The most likely explanation for the latter is that the previous question was so simple (a man) that subjects forgot to reset the query between the questions 2 and 3. All questions of the first two categories were answered in less than 1 minute and 43 seconds on average. Those results indicate that the more complex user interface of semantic faceted search does not entail a loss of usability compared to standard faceted search for the same tasks.

For other categories, all subjects but two managed to answer correctly at least one question of each category. Within each category, we observed that response times decreased, except for the Cycle category. At the same time, for Path, Disjunction and Inverse, the number of correct answers and queries increased. Those results suggest a quick learning process of the subjects. The decrease in category Negation is explained by a design flaw in the interface. For category Cycle, we conjecture some lassitude at the end of the test. Nevertheless, all but two subjects answered correctly to at least one of Cycle questions. The peak of response time in category Inverse is explained by the lack of inverse property examples in the tutorial. It is noticeable that subjects, nevertheless, managed to solve the Inverse questions with a reasonable success rate, and a decreasing response time.

Related Work

As faceted search is becoming widespread, a number of proposals have been made to apply it on the Semantic Web (SW). They all have in common to assume that data is represented in a SW format, either RDF(S) or OWL. Most of them, such as Ontogator [START_REF] Mäkelä | Ontogator -a semantic view-based search engine service for web applications[END_REF], mSpace6 , and Longwell7 , do not claim for a contribution in terms of expressiveness, and contribute either to the design of better interfaces and visualizations, or to methods for the rapid or user-centric configuration of faceted views [START_REF] Suominen | User-centric faceted search for semantic portals[END_REF]. Therefore, their contributions are somewhat orthogonal to ours, and could certainly complement ours. Other approaches, such as Slash-Facet [START_REF] Hildebrand | /facet: A browser for heterogeneous semantic web repositories[END_REF], BrowseRDF [START_REF] Oren | Extending faceted navigation to RDF data[END_REF], and SOR [LMZ + 07], extend faceted search towards a more expressive navigation.

The most essential ingredient for an expressive and flexible semantic search in RDF graphs is focus change. It allows to change the perspective without changing the underlying graph pattern. To the best of our knowledge, no faceted search system offers this in a general way. SlashFacet and SOR have the crossing operation that selects the images of the items in the current selection through a property. Crossing includes a focus change, but crossing back a property is not equivalent to a focus change, because it introduces an additional restriction: starting from a query Q and crossing p : ? and then p of ? leads to p : p of Q instead of Q and p : ? (they are not equivalent). Other systems allow to focus on different types of items, but this focus cannot be changed in the course of a search. For example, in a dataset about publications, a choice has to be made between authors and documents.

It is generally considered that the query should be hidden from the interface. In fact, in most faceted search systems, the query is displayed as the list of the restriction values users have already selected in the course of their search. This is important so that users do not feel lost, and can easily reverse previous selections. When expressiveness is raised to SPARQL with graph patterns, disjunction, and negation, it becomes necessary to introduce syntax. While, in Camelis 2, the query is simply rendered as a sentence following some grammar, nothing prevents to render syntax through graphical widgets (e.g., lists for conjunction, trees for restrictions, tab panels for disjunction).

Disjunction and negation are either absent or strongly limited in existing approaches. Disjunction is restricted to build sets of values or sets of items, e.g., in SlashFacet. Negation is restricted to restriction values, and also applies to unqualified restrictions (not father of ?) in BrowseRDF. No other system allows to form cycles as we do with variables.

Conclusion

We have introduced Semantic Faceted Search (SFS) as a search paradigm for Semantic Web knowledge bases, in particular RDF graphs. It combines the expressiveness of the SPARQL query language, and the benefits of exploratory search and faceted search. The user interface of semantic faceted search includes the user interface of other faceted search systems, and can be used as such. It adds a query box to tell users where they are in their search, and to allow them to change the focus or to remove query parts. It also adds a few controls for applying some query transformations such as insertion/deletion of disjunction, negation, and variables. We have introduced a new query syntax, LISQL, to better fit with a faceted interface and query transformations. Beside the list of selected items, the user interface has a hierarchy of facets organizing classes and properties by subsumption.

SFS has been implemented as a prototype, Camelis 2. Its usability has been demonstrated through a user study, where, after a short training, all subjects were able to answer simple questions, and most of them were able to answer complex questions involving disjunction, negation, or cycles. This means seman-tic faceted search retains the ease-of-use of other faceted search systems, and gets close to the expressiveness of query languages such as SPARQL.

Figure1.

  Figure1. A screenshot of the user interface of Camelis 2. It shows the selection of male persons whose lastname is Washington.

  Focus on a person + Cross father of birth : place : ?

	0 Reset
	?
	1 And a person
	a person
	2 And birth : year : 1601
	a person and birth : year : 1601
	3 Focus on year : 1601
	a person and birth : year : 1601
	4 Cross place : ? + Name
	a person and birth : (year : 1601 and place : ?X)
	5 And in England
	a person and birth : (year : 1601 and place : (?X and in England))
	6 Focus on 1601 + Or
	a person and birth : (year : (1601 or ?) and place : (?X and in
	England))
	7 And 1649
	a person and birth : (year : (1601 or 1649) and place : (?X and in
	England))
	8

a person and birth : (year : (1601 or 1649) and place : (?X and in England)) and father of birth : place : ? 9 Not a person and birth : (year : (1601 or 1649) and place : (?X and in England)) and father of birth : place : not ? 10 And ?X + Focus on a person a person and birth : (year : (1601 or 1649) and place : (?X and in England)) and father of birth : place : not ?X Table1. A navigation scenario in Camelis 2 on the genealogy of George Washington.

see http://www.w3.org/TR/rdf-sparql-query/

See http://protege.stanford.edu/

downloadable at http://www.irisa.fr/LIS/ferre/camelis/camelis2.html

Details can be found on http://www.irisa.fr/LIS/alice.hermann/camelis2.html

see http://mspace.fm/

see http://simile.mit.edu/wiki/Longwell

Acknowledgments. We would like to thank the 20 students, from the University of Rennes 1 and the INSA engineering school, for their volunteer participation to the usability evaluation.


Mélika Nadia Belhadj Hmida

Mélika Ben Ahmed

Majd Amel Moussa

Ben Rejeb

Yosra Said

Nadia Kourda

Bertrand Meresse

Maha Abdeladhim

Hechmi Louzir

Nadine Cerf-Bensussan
email: nadine.cerfbensussan@inserm.fr

Nadia Belhadj Hmida

Majd Ben Rejeb

Dr Mélika Ben

Impaired Control of Effector T Cells by Regulatory T Cells: A Clue to Loss of Oral Tolerance and Autoimmunity in Celiac Disease?

Keywords: Celiac disease, Regulatory T cells, IL-15

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Results. While percentages of CD4+CD25+FOXP3+ LPL were significantly increased in patients with active CD, proliferation and IFN-γ production of intestinal T lymphocytes were significantly less inhibited by autologous or heterologous Tregs in CD patients than in controls (p< 0.01). In all tested CD patients, IEL were unable to respond to Tregs. Resistance of LPL and PBL to Tregs suppression was observed in patients with villous atrophy who had serum levels of IL-15 significantly enhanced compared to patients without villous atrophy and to controls.

Conclusion.

Our results indicate that effector T lymphocytes from active CD become resistant to suppression by Tregs. This resistance might cause loss of tolerance to gluten but also to self-antigens.

Word count : 261

Pre-Print Version 3

Study highlights: WHAT IS CURRENT KNOWLEDGE:

IL-15 is overexpressed in the intestine of celiac disease patients.

One important mechanism to achieve and maintain tolerance to dietary proteins relies on the generation and activation of CD4+CD25+FOXP3+ T regulatory cells.

IL-15 renders in vitro conventional lymphocytes resistant to suppressive functions of regulatory T cells.

In active celiac disease, regulatory T cells are increased in the intestine and can suppress activation of conventional lymphocytes.

WHAT IS NEW HERE:

Suppression of lamina propria T lymphocytes by peripheral autologous and heterologous

Tregs is impaired in celiac disease patients and the level of inhibition varies depending on the presence or not of intestinal lesions.

Intraepithelial lymphocytes of both active and treated celiac disease patients are resistant to the inhibitory effects of peripheral Tregs.

INTRODUCTION

Celiac disease (CD) is a small intestinal enteropathy induced by cereal-derived prolamins (gluten) in genetically susceptible individuals. Activation of lamina propria gliadin-specific CD4+ T cells is a keystone of CD pathogenesis and results from the selective interplay between prolamins, the triggering environmental factor, and HLA-DQ2/8 molecules, the main genetic risk factor [START_REF] Qiao | Antigen presentation in celiac disease[END_REF]. This mechanism, although necessary, is however not sufficient to explain the loss of tolerance to dietary gluten in only a subset of individuals with at risk HLA. Furthermore, humanized mice engineered to express human HLA-DQ8 mount efficient CD4+ responses to gluten but do not develop intestinal lesions [START_REF] Black | HLA-DQ determines the response to exogenous wheat proteins: a model of gluten sensitivity in transgenic knockout mice[END_REF]. One important mechanism to achieve and maintain tolerance to dietary proteins relies on the generation and activation of CD4+CD25+FOXP3+ T regulatory cells (Tregs), a subset of lymphocytes initially identified by Sakaguchi in mice for their role against autoimmunity (reviewed in (3)).

In humans, patients with mutations affecting the FOXP3 gene and lacking functional Tregs develop severe autoimmune diseases [START_REF] Bennett | The immune dysregulation, polyendocrinopathy, enteropathy, X-linked syndrome (IPEX) is caused by mutations of FOXP3[END_REF][START_REF] Gambineri | Immune dysregulation, polyendocrinopathy, enteropathy, and X-linked inheritance (IPEX), a syndrome of systemic autoimmunity caused by mutations of FOXP3, a critical regulator of T-cell homeostasis[END_REF] but also dramatic food allergy [START_REF] Torgerson | Severe food allergy as a variant of IPEX syndrome caused by a deletion in a noncoding region of the FOXP3 gene[END_REF]. In mice, antigen feeding induce specific Tregs in gut-associated lymphoid tissues and in lamina propria (reviewed in [START_REF] Tsuji | Oral tolerance: intestinal homeostasis and antigen-specific regulatory T cells[END_REF]) and the depletion of such cells results in the loss of intestinal and peripheral tolerance to the corresponding food antigen [START_REF] Hadis | Intestinal Tolerance Requires Gut Homing and Expansion of FoxP3(+) Regulatory T Cells in the Lamina Propria[END_REF]. No genetic link of CD with the FOXP3 gene has been observed [START_REF] Bjornvold | FOXP3 polymorphisms in type 1 diabetes and coeliac disease[END_REF] and previous studies have suggested that the number of lymphocytes with a Treg phenotype, evaluated in the peripheral blood by flow cytometry [START_REF] Frisullo | Increased CD4+CD25+Foxp3+ T cells in peripheral blood of celiac disease patients: correlation with dietary treatment[END_REF][START_REF] Granzotto | Regulatory T-cell function is impaired in celiac disease[END_REF] and in the intestine by immunohistochemistry [START_REF] Tiittanen | Infiltration of forkhead box P3expressing cells in small intestinal mucosa in coeliac disease but not in type 1 diabetes[END_REF][START_REF] Vorobjova | Increased FOXP3 expression in small-bowel mucosa of children with coeliac disease and type I diabetes mellitus[END_REF][START_REF] Brazowski | FOXP3 Expression in Duodenal Mucosa in Pediatric Patients with Celiac Disease[END_REF][START_REF] Westerholm-Ormio | Infiltration of Foxp3-and Toll-like receptor-4-positive cells in the intestines of children with food allergy[END_REF] was increased. Recent findings, however, indicate that IL-15, a cytokine overexpressed in the intestine and in the serum of active CD patients [START_REF] Mention | Interleukin 15: a key to disrupted intraepithelial lymphocyte homeostasis and lymphomagenesis in celiac disease[END_REF][START_REF] Sabatino | Epithelium derived interleukin 15 regulates intraepithelial lymphocyte Th1 cytokine production, cytotoxicity, and survival in coeliac disease[END_REF][START_REF] Ahmed | Increased serum level of IL-15 in celiac disease: a role in the loss of peripheral immune homeostasis ?[END_REF], might, at least in combination with retinoic acid, hamper in vitro generation of mouse Tregs in the presence of dendritic cells [START_REF] Depaolo | Co-adjuvant effects of retinoic acid and IL-15 induce inflammatory immunity to dietary antigens[END_REF]. Contrasting with the later finding, we have observed that IL-15 did not impair but rather promoted the generation of functional human Tregs in an in vitro assay without dendritic cells [START_REF] Ahmed | IL-15 renders conventional lymphocytes resistant to suppressive functions of regulatory T cells through activation of the phosphatidylinositol 3-kinase pathway[END_REF]. Yet, following pre-incubation in the presence of IL-15, human peripheral T lymphocytes became resistant to the suppressive functions of Tregs, a resistance that resulted from PI3 kinase activation [START_REF] Ahmed | IL-15 renders conventional lymphocytes resistant to suppressive functions of regulatory T cells through activation of the phosphatidylinositol 3-kinase pathway[END_REF]. Altogether, these conflicting data led us to reevaluate by flow cytometry the numbers of Tregs in the peripheral blood and in the lamina propria of CD patients and, subsequently, to investigate the responses of intestinal and peripheral T cells of CD patients to Treg immunosuppressive effects.

MATERIAL AND METHODS

Patients and Controls

Twenty-four adult patients (age range, 22-50 years; mean age, 35 years) had uncomplicated CD. The diagnosis was based on detection of villous atrophy and antiendomysium/transglutaminase antibodies. At the time of study, 15 patients had active CD with partial to total villous atrophy and 9 were on a gluten free diet (GFD). Six of the later patients strictly adhered to GFD (3 months -7 years; mean, 4 years), had normal villous architecture and were negative for anti-endomysium antibodies, while three were partially compliant to the diet (4 months -3 years; mean, 2 years), had areas of mild partial villous atrophy on all or some biopsy specimens and were positive for celiac antibodies (IgA antiendomysium and anti-transglutaminase). All biopsies were obtained during endoscopy performed for diagnosis or follow-up purposes. Twenty-two patients were included as controls (age range, 30-37 years; mean, 41 years). These patients, with no family history of CD or other autoimmune diseases, underwent gastro-duodenal endoscopy for diagnostic purposes and had histologically normal small intestinal samples. Informed consent was obtained from all patients before the study. All experiments were approved by local ethics committee (Institute Pasteur of Tunis).

Lymphocyte Isolation

IELs and LPL were isolated from endoscopic samples as previously described [START_REF] Cerf-Bensussan | Intraepithelial lymphocytes of human gut: isolation, characterisation and study of natural killer activity[END_REF][START_REF] Cellier | Refractory sprue, coeliac disease, and enteropathy-associated T-cell lymphoma. French Coeliac Disease Study Group[END_REF]. Yield from biopsies was 0.3-0.8 x 10 6 for IEL and 0.5-1.3 x 10 6 for LPL. CD25 negative cells (0.35 to 1.1 x 10 6 ) were recovered from LPL after negative selection using magnetic beads (CD25 microbeads, Miltenyi Biotec, Bergisch-Gladbach, Germany). Peripheral blood mononuclear cells (PBMC) were isolated on Ficoll-Hypaque gradient. For co-culture experiments, CD4+CD25+ (Tregs) and CD4+CD25-T cells were isolated in a two-step procedure using the CD4+CD25+ regulatory T-cell isolation kit (Miltenyi Biotec) according to manufacturer's instructions. Peripheral Tregs were collected with a purity ranging from 63% to 72%.

Flow cytometry analysis

The percentage of lamina propria CD4+CD25+FOXP3+ lymphocytes was analyzed by flow cytometry. LPL (2 x 10 5 ) were incubated with FITC, PE, PerPC or APC conjugated mAbs to human CD4, CD25, CD45 or with control isotypes (BD Biosciences, Le Pont de Claix, France) for 20 minutes at 4°C. For intracellular FOXP3 detection, cells were fixed, permeabilized using Human FOXP3 Buffer Set (BD Biosciences) and labelled with PEconjugated anti-human or control isotype (BD Biosciences). Analyses were performed with a BD LSRII flow cytometer using the CELLQuest software (BD Biosciences). As lamina propria preparations can be contaminated by some epithelial cells, percentages of CD4+CD25+FOXP3+ lymphocytes were determined in the gate of hematopoietic cells labeled by the pan-anti-CD45 antibody.

Functional analysis

The suppressive functions of peripheral Tregs were tested in co-culture experiments in RPMI 1640 medium supplemented with 10% AB human serum (Sigma, St Louis, MO), 1% sodium pyruvate, 1% non essential aminoacids, 1% Hepes buffer, 5 x 10-5 M/l βmercaptoethanol and 40 µg/ml gentamycin, (Invitrogen, Cergy Pontoise, France). IEL, CD25-LPL and peripheral CD4+CD25-T subsets (10 5 /well) were plated on 96-well plates coated with anti-CD3 antibodies (UCHT1, BD Biosciences) at 2µg/ml and added with 1 or 0.25 x10 5 peripheral Tregs per well in a final volume of 200µl for 5 days. In most experiments cocultures were performed in autologous conditions. In two experiments, heterologous Tregs from controls or active CD were co-cultured with IEL, CD25-LPL and peripheral CD4+CD25-T subsets (10 5 /well) from active CD and controls, respectively.

Proliferative responses were assessed by measuring the uptake of [3H] thymidine (Amersham, Saclay, France) 18 hours after adding 0.4µCi/well. IFN-γ production was analyzed on supernatants of cells using Human IFN-γ ELISA Set (BD Biosciences) according to manufacturer's instructions.

Analysis of FOXP3 mRNA expression by real time RT-PCR

Total RNA was extracted from duodenal biopsies using RNeasy Mini Kit (Qiagen) according to the manufacturer's procedure. The extracted RNA was then reverse transcribed using the Murine-Mooloney Leukemia Virus (MMLV) reverse transcriptase and random hexamers (Promega) according to standard procedure. FOXP3 mRNAs were quantified by real time PCR using available gene expressed assay® and Taqman PCR Master Mix (Applied Biosystems). Amplification was performed in cycles of denaturation at 95°C for 15 seconds and annealing and extension at 60°C for 1 minute using an ABI PRISM 7500 sequence detection system. Data were normalized referring to the expression of an endogenous gene RPLP0 (ribosomal Protein, Large, PO) by calculating 2 -∆CT, with ∆CT the difference in threshold cycles for target and reference.

Statistical Analysis

Data obtained from the different groups of patients and healthy controls were compared by the non parametric Mann-Whitney U test. Statistical significance was assigned to a value of p < 0.05.

RESULTS AND DISCUSSION

CD4+CD25+FOXP3+ T cells are increased in the lamina propria of active CD patients

Real-time PCR analysis of intestinal biopsies demonstrated a significant increase in FOXP3 mRNA levels in active CD compared to controls (p<0.0001) and patients on a glutenfree diet (p<0.01) (Figure 1A). Consistent with this finding, multicolor flow cytometry analysis showed a significantly higher percentage of CD4+CD25+FOXP3+ T lymphocytes among lamina propria CD45+ cells isolated from active CD patients than from controls (p=0.005) (Figure 1, panels B andC). In contrast, the percentage CD4+CD25+FOXP3+ lymphocytes remained comparable in peripheral blood CD45+ cells from CD and controls (p> 0.05) (Figure 1B). The increased proportion of lamina propria lymphocytes with a Treg phenotype is in keeping with previous reports in CD [START_REF] Tiittanen | Infiltration of forkhead box P3expressing cells in small intestinal mucosa in coeliac disease but not in type 1 diabetes[END_REF][START_REF] Vorobjova | Increased FOXP3 expression in small-bowel mucosa of children with coeliac disease and type I diabetes mellitus[END_REF][START_REF] Brazowski | FOXP3 Expression in Duodenal Mucosa in Pediatric Patients with Celiac Disease[END_REF][START_REF] Westerholm-Ormio | Infiltration of Foxp3-and Toll-like receptor-4-positive cells in the intestines of children with food allergy[END_REF] and argues against the hypothesis that a defect in the recruitment or in the de novo generation of intestinal Tregs may play a part in the pathogenesis of CD. These results are also consistent with very recent data showing that increased numbers of functional Tregs can be isolated from the lamina propria of patients with active CD [START_REF] Zanzi | IL-15 Interferes With Suppressive Activity of Intestinal Regulatory T Cells Expanded in Celiac Disease[END_REF].

Intestinal effector T cells fail to respond to regulatory T cells in CD patients.

The contrast between the intestinal expansion of CD4+CD25+FOXP3 T cells and the rupture of tolerance to dietary gluten in the intestine of active CD suggested that the latter cells may be impaired in their capacity to down-regulate local effector T cell functions or, conversely, that effector T cells may fail to respond to Tregs. To test whether intestinal lymphocytes from patients with CD were responsive or not to the suppressive effects of regulatory lymphocytes, blood samples and duodenal biopsies were obtained from 9 celiac disease patients and 9 controls. Peripheral blood CD4+CD25+ T cells (T regs) were then separated from CD4+CD25-peripheral lymphocytes (PBL) while IEL and LPL were isolated from endoscopic biopsies and CD25+ T cells removed from LPL to obtain a fraction of Pre-Print Version 10 CD25-LPL. The suppressive effects of autologous peripheral Tregs were tested on the proliferation and IFN-γ production of IEL, and of CD25-LPL and PBL stimulated with immobilized anti-CD3 antibody. With the idea in mind that the responses to Tregs may be variable within subsets of patients, we defined a "threshold of resistance" when the percentage of inhibition was below the 5th percentile of the control group. In two additional experiments, co-cultures were performed in heterologous conditions.

In all tested controls and CD patients, CD25-PBL and LPL proliferated and produced IFN-γ in response to anti-CD3 stimulation (Figure 2 and Figure 3). In controls, these responses were efficiently inhibited by peripheral autologous Tregs (Figure 4). In contrast, suppression of proliferation and IFN-γ production was significantly less when LPL from CD patients were co-cultured with autologous peripheral Tregs (Figure 4). Moreover, the level of inhibition varied depending on the presence or not of intestinal lesions. Thus, in the 6 CD patients with villous atrophy, no suppression was observed in co-cultures of LPL with autologous T regs while suppression was detected in the three CD patients on GFD who had recovered a normal villous architecture (Figure 4). Interestingly, inhibition of proliferation and IFN-γ production of CD25-PBL by autologous Tregs was also impaired in active CD patients. In addition, in one CD patient who did not adhere strictly to GFD and remained with partial villous atrophy, Tregs were unable to inhibit IFN-γ production by peripheral CD25-PBL despite efficient inhibition of their proliferation (Figure 4).

IEL proliferation and more particularly cytokine production in response to coated anti-CD3 antibody varied between individuals, a variability previously ascribed to the lack of accessory signals in this in vitro assay [START_REF] Sarnacki | Enhancement of CD3-induced activation of human intestinal intraepithelial lymphocytes by stimulation of the beta 7-containing integrin defined by HML-1 monoclonal antibody[END_REF] or to the release of immunosuppressive cytokines by epithelial cells [START_REF] Ebert | Inhibitory effects of transforming growth factor-beta (TGF-beta) on certain functions of intraepithelial lymphocytes[END_REF]. Yet, no significant difference was observed between groups of patients and controls (p> 0.05). (Figure 4 and data not shown). In controls, the sensitivity of IEL to the inhibitory effect of autologous Tregs was variable and overall less than that of PBL and LPL. Yet a striking finding was that, in all tested CD patients, IEL were completely resistant to the inhibitory effects of Tregs and the difference was highly significant when compared to controls (p = 0.0005). Altogether, these results indicated that, although the numbers of CD4+CD25+FOXP3+ T cells were increased in the intestine of active CD patients, these cells could not efficiently down-regulate effector T cell functions in the intestine but also in the periphery.

The fact that the suppressor effect of Tregs on LPL and PBL was comparable in patients on GFD with normal histology and in controls suggested that the defect was not primary but secondary to the inflammatory process. Moreover, that Tregs from patients on GFD and with normal histology could suppress LPL and PBL but not IEL, rather pointed to an abnormal response of effector cells. It was, however, difficult to ascertain that the defect lied at the level of effector T cells, since immuno-suppression had been tested in autologous conditions. To confirm this hypothesis, co-cultures were performed in heterologous conditions. As shown in figure 5, Tregs from active CD patients could efficiently downregulate proliferation and IFN-γ production of PBL, LPL and IEL from controls. In contrast, Tregs from controls were unable to suppress effector T cells from active CD patients (Figure 5) while they could efficiently suppress autologous PBL (data not shown). Altogether these results are in keeping with a recent article that shows that Tregs isolated from the lamina propria of patients with active CD are functional [START_REF] Zanzi | IL-15 Interferes With Suppressive Activity of Intestinal Regulatory T Cells Expanded in Celiac Disease[END_REF] and confirm that effector cells from patients with active CD fail to respond to Tregs either autologous or heterologous. We and others have previously shown that IL-15, a cytokine overproduced in CD patients, prevents the response of effector T cells to the suppressive effects of Tregs [START_REF] Ahmed | IL-15 renders conventional lymphocytes resistant to suppressive functions of regulatory T cells through activation of the phosphatidylinositol 3-kinase pathway[END_REF][START_REF] Peluso | IL-21 counteracts the regulatory T cell-mediated suppression of human CD4+ T lymphocytes[END_REF]. The lack of inhibitory effect of Tregs in CD may thus depend on the production of IL-15. In favor of this hypothesis, we observed that the serum levels of IL-15 were significantly increased in CD patients (4.9 pg/ml; 0.8 to 22.4 pg/ml) compared to controls (0.49 pg/ml; 0 to 2.79 pg/ml) (p<0.001) [START_REF] Ahmed | Increased serum level of IL-15 in celiac disease: a role in the loss of peripheral immune homeostasis ?[END_REF]. IL-15 is known to reverse the anergic state of Tregs and to allow their proliferation in response to anti-CD3 stimulation [START_REF] Karakhanova | Highly efficient expansion of human CD4+CD25+ regulatory T cells for cellular immunotherapy in patients with graftversus-host disease[END_REF]. The presence of circulating IL-15 may thus explain the small but significant proliferative response to anti-CD3 stimulation of peripheral Tregs from CD patients but not from controls (Figures 2 and5 and data not shown). Similarly, a small secretion of IFN-γ by the latter cells was observed (Figures 3 and

and data not shown). This finding is reminiscent of the recent demonstration by

McClymont et al. that a subset of human Tregs from patients with type I diabetes produced IFN-γ while preserving their suppressive capacity [START_REF] Mcclymont | Plasticity of human regulatory T cells in healthy subjects and patients with type 1 diabetes[END_REF]. It will be interesting to define whether IL-15 participates in the appearance of this T cell subset since we have previously found that IL-15 was particularly increased in the serum of CD patients with type I diabetes [START_REF] Ahmed | Increased serum level of IL-15 in celiac disease: a role in the loss of peripheral immune homeostasis ?[END_REF]. As already described [START_REF] Ahmed | Increased serum level of IL-15 in celiac disease: a role in the loss of peripheral immune homeostasis ?[END_REF], serum concentrations of IL-15 depended on disease activity (Figure 6) and were correlated with levels of anti-transglutaminase antibodies (data not shown). The fact that serum levels of IL-15 varied between patients may explain why two previous studies using co-culture of autologous peripheral Tregs and CD25-CD4+ T cells reported conflicting results when testing the immunosuppressive effect of peripheral T regs on autologous conventional T cells [START_REF] Frisullo | Increased CD4+CD25+Foxp3+ T cells in peripheral blood of celiac disease patients: correlation with dietary treatment[END_REF][START_REF] Granzotto | Regulatory T-cell function is impaired in celiac disease[END_REF]. It is also noticeable that CD8+ T cells are much more sensitive to the effect of IL-15 and become thereby more easily unresponsive to the effect of Tregs after pre-incubation in IL-15 [START_REF] Ahmed | Increased serum level of IL-15 in celiac disease: a role in the loss of peripheral immune homeostasis ?[END_REF]. IEL contain both CD8+ TcRαβ+ cells and TCRγδ+ cells also responsive to IL-15. The high sensitivity of IEL to IL-15 together with the fact that IL-15 can remain increased in the epithelium of CD patients on GFD [START_REF] Mention | Interleukin 15: a key to disrupted intraepithelial lymphocyte homeostasis and lymphomagenesis in celiac disease[END_REF], might explain the lack of response of IEL to Treg suppression even in treated CD patients whose CD25-LPL and peripheral T cells responded to the inhibitory effect of autologous peripheral Tregs.

In conclusion, we observe that peripheral Tregs from active CD display normal suppressive functions despite partial loss of their anergic state, a possible consequence of their in vivo exposure to IL-15. More strikingly, we demonstrate that intestinal but also peripheral

Pre-Print Version

13

T lymphocytes become resistant to the suppressive effects of Tregs during active CD and that the defective response persists in IEL even after gluten eviction. Together with our previous studies showing that, due to IL-15 overexpression, intestinal T lymphocytes become unresponsive to the immunoregulatory cytokine TGF-β (29), these data provide a rationale for the loss of intestinal tolerance to gluten [START_REF] Meresse | Celiac disease: from oral tolerance to intestinal inflammation, autoimmunity and lymphomagenesis[END_REF]. Our demonstration of the inability of regulatory T cells of CD patients to control the expansion of lymphocytes using a polyclonal stimulus (anti-CD3 antibody) further suggests that such defect may underlie the loss of tolerance towards different antigens and the frequent occurrence of autoimmunity in CD [START_REF] Viljamaa | Coeliac disease, autoimmune diseases and gluten exposure[END_REF][START_REF] Cosnes | Incidence of autoimmune diseases in celiac disease: protective effect of the gluten-free diet[END_REF]. The persistent resistance of IEL to Treg suppression in treated CD might also explain why the latter cells remain increased and abnormally activated despite GFD [START_REF] Olaussen | Reduced chemokine receptor 9 on intraepithelial lymphocytes in celiac disease suggests persistent epithelial activation[END_REF]. Together with the anti-apoptotic effect of IL-15 [START_REF] Mention | Interleukin 15: a key to disrupted intraepithelial lymphocyte homeostasis and lymphomagenesis in celiac disease[END_REF][START_REF] Malamut | IL-15 triggers an antiapoptotic pathway in human intraepithelial lymphocytes that is a potential new target in celiac diseaseassociated inflammation and lymphomagenesis[END_REF], the lack of effective retro-control of IEL activation may also, on the long term, promote the onset of IEL-derived lymphomas, a situation recapitulated in IL-15 transgenic mice which develop multi-organ lymphocytic infiltrates, aggressive autoimmune skin lesions and, ultimately, CD8+/NK T cell lymphoma or leukemia [START_REF] Fehniger | Fatal leukemia in interleukin 15 transgenic mice follows early expansions in natural killer and memory phenotype CD8+ T cells[END_REF]. Restoring the response of effector T cells to the regulatory effects of Tregs is likely central to prevent the onset of CD autoimmune complications. The normalization of LPL and PBL responses after GFD may explain why GFD can prevent the later complications. It will therefore be interesting to investigate whether unresponsiveness to Tregs persists or resumes despite GFD in patients developing refractory celiac disease.

Guarantor of the article: Mélika Ben Ahmed. .

Specific author contribution:

Pre-Print Version

  Nadia Belhadj Hmida performed suppression assays and flow cytometry analyses and contributed to data analysis. Mélika Ben Ahmed performed quantitative RT-PCR analyses, supervised suppression assays and contributed to study design, data analysis and drafting of the article. Amel Moussa, Majd Ben Rejeb and Yosra Said helped in patient's recruitment and performed duodenal biopsies for celiac disease patients and controls. Nadia Kourda performed histological analyses for celiac disease patients and controls. Bertrand Meresse contributed to flow cytometry analysis. Maha Abdeladhim helped for suppression assays. Hechmi Louzir contributed to drafting of the article. Nadine Cerf-Bensussan contributed to study design, data analysis and drafting of the article Financial support : INSERM UMR 989 is supported by grants from INSERM, Fondation Princesse Grace, Association pour la Recherche Contre le Cancer, Ligue Contre le Cancer, Agence Nationale pour La Recherche, Fondation pour la Recherche Médicale-Equipes 2007 and Association Française des Intolérants au Gluten. N. Belhadj Hmida was supported by a grant from Le Réseau International des Instituts Pasteur. Potential competing interests: None.

Figure 1 :

 1 Figure 1: Intestinal CD4+CD25+FOXP3 T lymphocytes are increased in active CD.

Figure 2 :

 2 Figure 2: Proliferation of peripheral and intestinal lymphocytes of CD patients is not

Figure 3 :

 3 Figure 3: Interferon gamma secretion by peripheral and intestinal lymphocytes of CD

Figure 4 :

 4 Figure 4: Global comparison of the responses of peripheral and intestinal lymphocytes

Figure 5 :

 5 Figure 5: Lack of suppression of effector lymphocytes from active CD patients by

Figure 6 :

 6 Figure 6: Increase in IL-15 serum levels in active CD.