S Ferré
email: ferre@irisa.fr

A Hermann
email: alice.hermann@irisa.fr

Reconciling Faceted Search and Query Languages for the Semantic Web

Keywords: semantic web, faceted search, query language, exploratory search, navigation, expressiveness ??-???

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. We formalize the navigation of faceted search as a navigation graph, where navigation places are queries, and navigation links are query transformations. We prove that this navigation graph is safe (no dead-end), and complete (every query that is not a dead-end can be reached by navigation). In this paper, the LISQL query language generalizes existing semantic faceted search systems, and covers most features of SPARQL. A prototype, Sewelis, 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

A key issue of the Semantic Web is 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 the second mode exploratory search, following [START_REF] Marchionini | Exploratory search: from finding to understanding[END_REF]. Exploratory search is often associated to faceted search [START_REF] Hearst | Finding the flow in web site search[END_REF], Sacco & Tzitzikas 2009), 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 1 . There are semantic faceted search systems 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], VisiNav [START_REF] Harth | VisiNav: A system for visual search and navigation on web data[END_REF]). For instance, none of them allows for cycles in graph patterns, unions of complex graph patterns, or negations of complex graph patterns.

Languages for querying 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. 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], the SCRIBO Graphical Editor 2 ) 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. 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, 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 gives preliminaries about the Semantic Web and Faceted Search. Section 3 discusses the limits of set-based faceted search by formalizing the navigation from selection to selection. Section 4 introduces LISQL queries and their transformations. In Section 5, navigation with QFS is formalized and proved to be safe and complete w.r.t. LISQL, as well as efficient. Section 6 provides details about our prototype implementation Sewelis. Section 7 reports about a user study that demonstrates the usability of our approach. Our approach is also compared in Section 8 to other works in faceted search and query languages for the Semantic Web. Finally, Section 9 concludes.

Preliminaries

Semantic Web

The Semantic Web (SW) is founded on several representation languages, such as RDF, RDFS, and OWL, which provide increasing inference capabilities [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF]). The two basic units of these languages are resources and triples. A resource can be either a URI (Uniform Resource Identifier), a literal (e.g., a string, a number, a date), or a blank node, i.e., an anonymous resource. A URI is the absolute name of a resource, i.e., an entity, and plays the same role as a URL w.r.t. web pages. Like URLs, a URI can be a long and cumbersome string (e.g., http://www.w3.org/1999/02/22rdfsyntaxns#type), so that it is often denoted by a qualified name (e.g., rdf:type). We assume pairwise disjoint infinite sets of URIs (U ), blank nodes (B), and literals (L). The set of resources is then defined as R = U ∪ B ∪ L.

A triple (s, p, o) is made of 3 resources, and can be read as a simple sentence, where s is the subject, p is the verb (called the predicate), and o is the object. For instance, the triple (ex:Bob,rdf:type,ex:man) says that "Bob has type man", or simply "Bob is a man". Here, the resource ex:man is used as a class, and rdf:type is used as a property, i.e., a binary relation. The triple (ex:Bob,ex:friend,ex:Alice) says that "Bob has friend Alice", where ex:friend is another property. The triple (ex:man,rdfs:subClassOf,ex:person) says that "man is subsumed by person", or simply "every man is a person". The set of all triples of a knowledge base forms a RDF graph.

Definition 2.1: An RDF graph is defined as a set of triples (s, p, o) ∈ (U ∪ B) × U × (U ∪ B ∪ L)
, where s is the subject, p is the predicate, and o is the object.

A vocabulary is a set of resources having a meaning defined by convention. RDF(S) is a vocabulary used to represent the membership to a class (rdf:type), subsumption between classes (rdfs:subClassOf), subsumption between properties (rdfs:subPropertyOf), the domain (rdfs:domain) and range (rdfs:range) of properties, the meta-class of classes (rdfs:Class), the meta-class of properties (rdf:Property), etc. OWL introduces additional vocabulary to represent complex classes and properties: e.g., restrictions on properties, intersection of classes, inverse properties. The variant OWL-DL is the counterpart of Description Logics (DL) (Baader et al. 2003), where resources are individuals, classes are concepts, and properties are roles. A RDF graph that uses the OWL vocabulary to define classes and properties is generally called an ontology. Each vocabulary comes with a semantics, and the richer the vocabulary is, the more expressive and the more complex inference is.

Vocabulary for genealogy. For illustration purposes, we consider RDF graphs about genealogical data. To this purpose, we introduce a custom vocabulary for genealogy. The URIs of this domain are associated to a namespace (gen:). This prefix is omitted if there is no ambiguity. Resources can be persons, events, places or literals such as names or dates. Persons belong either to the class of men or to the class of women, may have a firstname, a lastname, a sex, a father, a mother, a spouse, a birth, and a death. A birth or a death is an event that may have a date and a place. Places can be described as parts of larger places. The classes of men and women are declared as subclasses of the class of persons. Properties father and mother are declared as subproperties of property parent. The transitive closure of property parent is obtained by defining property ancestor as transitive, and a super-property of parent. For illustration purposes, we use genealogical datasets converted from GED files 3 . In particular, we use a small dataset about the ascendancy of George Washington, which we also used in our user evaluation, reported in Section 7. This dataset has about 400 resources, including 79 persons, and about 4000 triples.

Query languages provide on semantic web knowledge bases the same service as SQL on relational databases. They generally assume that implicit triples have been inferred and added to the base. The most well-known query language, SPARQL, reuses the SELECT FROM WHERE syntax of SQL queries, using graph patterns in the WHERE clause. For instance, pairs of siblings can be retrieved by the following query:

SELECT DISTINCT ?x ?y FROM <mygen.rdf> WHERE { ?x gen:mother ?m. ?x gen:father ?f. ?y gen:mother ?m. ?y gen:father ?f. FILTER ?x != ?y }

Figure 1 shows a graphical representation of the graph pattern of this query, where arrows represent triples oriented from the subject to the object. The query reads "two persons ?x and ?y are siblings if they share a same mother and a same father, and are different". The FILTER condition is necessary because nothing prevents two variables to bind to a same resource. SPARQL provides a number of relational algebra operators to combine basic graph patterns: join, set union (UNION), left join (OPTIONAL), named graphs (GRAPH), and filtering by various constraints (FILTER). SPARQL 1.1 extends its expressiveness with set difference (MINUS), negation (NOT EXISTS), subqueries, aggregations, and expressions.

Faceted Search

Faceted Search [START_REF] Hearst | Finding the flow in web site search[END_REF], Sacco & Tzitzikas 2009) covers a family of user interfaces for browsing a collection of items. It is becoming a de facto standard in e-commerce websites, and its scope of application is wide (see Chap. 9 in (Sacco & Tzitzikas 2009)). It is suitable for retrieval search, i.e., the quick retrieval of an item already known to the user. It is also suitable for exploratory search [START_REF] Marchionini | Exploratory search: from finding to understanding[END_REF], i.e., the discovery of the objects that best suits the needs of the user, who has no prior knowledge of the item collection. An example of the later is when users want to buy a new camera. They do not know which models exist and what their features are, but they have constraints and preferences such as low cost, high resolution, or brand. Faceted search systems guide users through the item collection, and give them the feeling to have considered all the possibilities. At each navigation step, users only have to make a choice among a set of alternatives that are suggested by the system.

The data model underlying faceted search is simple. Each item is described along a set of facets, or dimensions. Each facet has a range of values. Therefore, each item is described by a set of pairs facet-value, which we call features. Conversely, each feature f has a set of items, noted items(f ). A facet is not necessarily defined on all items. At any navigation step, the current selection is defined as a set of items S. The initial selection S 0 is generally the whole item collection. From the current selection S, a set of restrictions are computed and displayed to the user. A restriction is a feature f that matches at least one item of the current selection, i.e., the intersection between S and the set of items items(f ) is not empty (S ∩ items(f ) = ∅). Each restriction is generally accompanied by the number of items it matches ( S ∩ items(f ) ). Restrictions are organized by facets, and for the sake of conciseness, most facets are initially collapsed, and expanded on demand. On the one hand, restrictions provide a summary of the current selection. On the other hand, each restriction is a selector for a subset of the selection. The summary plays a crucial role in exploratory search because for each facet it shows only and all of the relevant values for the current selection. This allows for the informed choice of a restriction: e.g., the lowest price or the highest resolution that is available given previous selected restrictions.

Exploration in faceted search is based on set operations between selections and restrictions. At each navigation step, a new selection is derived by applying a set operation between the current selection S and a restriction f chosen by the user. Typically, the set operation is intersection, i.e. S := S ∩ items(f ). Extensions of faceted search may allow for the exclusion of a restriction (S := S \ items(f )), or the union with a restriction (S := S ∪ items(f )). After a navigation step, a new set of restrictions is displayed to reflect the new selection. The list of chosen restrictions is generally displayed, and any of them can be removed by users, leading to a larger selection. This is useful to relax a constraint, for example in order to get more items and restrictions. The list of chosen restrictions can be seen as a query, which, in general, is limited to a conjunction of features, while restricted forms of negation and disjunction are sometimes available.

Dynamic Taxonomies (DT) [START_REF] Sacco | Dynamic taxonomies: A model for large information bases[END_REF], 2006, Sacco & Tzitzikas 2009) are a model of faceted search, where a multidimensional taxonomy is used instead of facets and values. In fact, facets and values form a two-level taxonomy, with facets at the first level, and values at the second level. Using taxonomies of arbitrary depth allows for features at different granularity levels. For instance, a facet of date can be used at the levels of days, weeks, months, years, etc. Weeks and months can be combined because taxonomies need not be trees but can be directed acyclic graphs. Features are called concepts, and the generalization ordering between features is called subsumption. Taxonomies are multidimensional, in that several features, even under a same facet, can be attached to a same item. This is useful with a facet of topics as a same item can match several topics. The term "dynamic taxonomy" stands for the fact that the summary is now a subset of the taxonomy, which dynamically adapts to the selection.

Logical Information Systems (LIS) [START_REF] Ferré | A file system based on concept analysis[END_REF], 2004[START_REF] Ferré | Camelis: a logical information system to organize and browse a collection of documents[END_REF]) are another model of faceted search that has been developed in our team since 1999, on the basis of Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF] and logic-based information retrieval [START_REF] Van Rijsbergen | A new theoretical framework for information retrieval[END_REF]. For what concerns us here, logical information systems can be defined as an extension of dynamic taxonomies, where features are the formulas of an ad-hoc logic, and subsumption is defined by logical inference rather than explicitly [START_REF] Ferré | Logical information systems: from taxonomies to logics[END_REF]. Using logics enhances the expressiveness of features and queries, as well as the design and engineering of complex taxonomies (see Chapter 8 in (Sacco & Tzitzikas 2009)). In LIS, the selection is defined as the set of answers, called extension, of the query, and changes of the selection are done through changes to the query. In addition to navigation, LIS provide direct querying for expert users, and query-by-examples to find items similar to a given set of examples.

3 Limits of Set-based Faceted Search for the Semantic Web

The notions of faceted search can be transposed to the Semantic Web. Items and values are resources (URIs or literals), and facets are properties. The association between an item and a facet-value is a triple, where the subject is the item, the predicate is the facet, and the object is the value. Because of the relational nature of semantic data, new kinds of features 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], VisiNav [START_REF] Harth | VisiNav: A system for visual search and navigation on web data[END_REF]). In addition to facet-value pairs, a feature can be the name of a resource, a class as a type, the domain of a property, or the range of a property (e.g., BrowseRDF). The syntactic form of selections in Table 2 implicitly defines the language of queries (q) that can be reached by set-based faceted search:

q → ? | q and f | q and not f | q or f | p : q | p of q
This grammar already defines a rich language of accessible queries, but it has strong limits in terms of flexibility and expressiveness. This can be seen at first sight by the fact that the right-hand side of intersection, difference, and union are restricted to features, instead of arbitrary queries. This linearly recursive definition of queries comes from the linear navigation of set-based faceted search. The consequence of this linearity is that not all combinations of intersection, union, and crossings are reachable, which is counter-intuitive and limiting for end users. For example, the following kinds of selections are not reachable, where the R i represent the set of items of some features:

• unions of complex selections, e.g., (R 1 ∩ R 2 ) ∪ (R 3 ∩ R 4 );
• or intersections 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.

Existing approaches to semantic faceted search often have additional limitations, which are sometimes hidden behind a lack of formalization. In some systems (e.g., BrowseRDF, gFacet), a same facet (a property) cannot be used several times, which is fine for functional properties but not for relations such as "child": p : (f 1 and f 2 ) is reachable but not (p : f 1 ) and (p : f 2 ). In other systems (e.g., /facet), a property whose domain and range are the same cannot be used as a 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 expressiveness of faceted search, while retaining its properties of safeness (no dead-end), and ease-of-use. The key idea is to define navigation links at the syntactic level as query transformations, rather than at the semantic level as set operations. Indeed, the syntactic expression of a query retains more information than its semantics (a set of items) because a query has a single set of items, but a set of items can be the semantics of many different queries.

The navigation from selection to selection, as well as the computation of restrictions related to the current selection, are retained because a set of items of the current query can be computed at any time.

In Section 4.1, we first define the syntax and semantics of LISQL (LIS Query Language). LISQL generalizes in a natural way the query language behind set-based faceted search (see Section 3), by allowing for the free combination of features, intersection, difference, union, and crossings. We then define in Section 4.2 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 4.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 expressiveness achieved by LISQL.

4.1 The LIS Query Language (LISQL)

query syntax semantics q items(q) name r {r} type 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
Table 3 Syntax and semantics of LISQL queries.

LISQL is obtained by merging the syntactic categories of features and queries in the grammar of Section 3, so that every query can be used in place of a feature.

Definition 4.1: The syntax and semantics of the LISQL constructs is defined in Table 3, 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 ).

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 4.3, because it cannot be defined inductively, like in Table 3.

Syntactic constructs are given in increasing priority order (see Table 3), and brackets or indentation 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". The same LISQL query with indentation instead of brackets displays as follows (the and connectors are omitted). a person birth : year : 1601 or 1649 place :

?X part of England father : birth : place : not ?X This notation better renders the structure of the query, and is therefore used in our prototype Sewelis (see Section 6).

Query Transformations

We have generalized the query language by allowing complex queries in place of features: e.g., q 1 and q 2 instead of q and f . However, because the number of suggested restrictions in faceted search must be finite, it is not possible to suggest arbitrarily complex queries as restrictions. More precisely, the vocabulary of features must be finite. In QFS, we retain the same set of features as in Section 3 (i.e., names, types, pairs facet-value, domain, and range), 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. This notion allows our approach to escape the linearity of set-based navigation, and therefore to reach queries with arbitrary syntax trees. Definition 4.2: 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[φ].

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 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 3. Definition 4.3: A query transformation transforms a query q into the query q[φ := q 1 ] by replacing the subquery at focus φ ∈ Φ(q) by another query q 1 . One note q[t 1 ] . . . [t n ] if several transformations are successively applied. The also define the following abbreviations for common query transformations:

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

δ q[φ and δ] ? q p : q 1 q[φ and p : ? φ1 ][φ 1 and q 1 ] p of q 1 q[φ and p of ? φ1 ][φ 1 and q 1 ] not q 1 q[φ and not ? φ1 ][φ 1 and q 1 ] q 1 and q 2 q[φ and q 1φ1 ][φ 1 and q 2 ] 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: The classical facet-value features (p : r and p of r) appear to be redundant for navigation as their intersection can be decomposed, but they are still useful for visualization in a faceted search interface.

Sequences of query transformations are analogous to the use of graphical query editors, but the key difference is that a valid query, answers, and restrictions will be returned at each navigation step, providing feedback, understanding-at-a-glance, no dead-end, and all benefits of exploratory search. Despite the syntax-based definition of navigation steps, they 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 5, 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).

Translation to and Comparison with SPARQL

We propose a (naive) translation of LISQL queries to SPARQL queries. It involves the introduction of variables that are implicit in LISQL queries. This translation provides an alternative way to compute LISQL query answers, in addition to Table 3. As this translation applies to LISQL queries with co-reference variables, it becomes possible to compute their set of items.

Definition 4.4: 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 an 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 a 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 ) }

The graph pattern S 0 (x) may depend on the application. By default, it is defined as (?x a rdfs:Resource.), and allows to select all kinds of resources, including classes, properties, and literals. The use of S 0 (x) in graph patterns ensures that variables are bound in filters and negations.

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 from 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.

The translation sparql (q ex ) of the above 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 is the following. gen:England gen:part ?X. ?p gen:father ?f. ?f gen:birth ?bf. ?bf gen:place ?pf. FILTER (?pf != ?X) }

SELECT

This example shows that LISQL is more concise, and makes a minimal use of variables. It also replaces a number of logical and algebraic symbols (curly brackets, dot, UNION, FILTER, =, !=, &&, ||, and !) by keywords for the 3 Boolean operators (and, or, not) plus brackets or indentation. The LISQL syntax follows the usual syntax for expressions (infix operators and brackets/indentation to fix priorities), and we think that this makes it easier to read and learn.

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 set of restrictions for that selection. A navigation link is defined by a query transformation and, possibly, a focus change. We prove the safeness of navigation graphs in Section 5.1, and their completeness in Section 5.2. Finally, we discuss the efficiency of our approach relative to set-based faceted-search in Section 5.3. 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, φ), which 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.1: The flip of a query q at a focus φ ∈ Φ(q) is defined as flip(q, φ) = flip ′ (q, φ, ?). The function flip ′ inductively deconstructs the query q until reaching the focus φ, and uses the additional (third) argument k as an accumulator for the resulting flipped query. In the following equations, the subquery that contains focus φ is underline.

flip ′ (p : q 1 , φ, k) = flip ′ (q 1 , φ, p of k) flip ′ (p of q 1 , φ, k) = flip ′ (q 1 , φ, p : k) flip ′ (q 1 and q 2 , φ, k) = flip ′ (q 1 , φ, k and q 2 ) flip ′ (q 1 and q 2 , φ, k) = flip ′ (q 2 , φ, k and q 1 ) flip ′ (q 1 or q 2 , φ, k) = flip ′ (q 1 , φ, k) flip ′ (q 1 or q 2 , φ, k) = flip ′ (q 2 , φ, k) flip ′ (not q 1 , φ, k) = flip ′ (q 1 , φ, k) flip ′ (q φ , φ, k) = q and k
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 removing the second alternative in the current query. 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 5.2: The 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 5.3: 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 5.4: Let D be a RDF dataset. The navigation graph G D = (P, L) of D has its set of navigation places (vertices) defined by

P = {(q, φ) | q ∈ LISQL, φ ∈ Φ(q)},
and its set of navigation links (edges) defined by Table 4 for every place p = (q, φ). The notation p ′ = p[l] denotes the navigation place obtained by traversing the navigation link l from the navigation place p. One can note p[l 1 ] . . . [l n ] when several links are traversed.

The number of navigation places is infinite because there are infinitely many LISQL queries, but the number of outgoing navigation links 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 p 0 = (? φ , φ).

Before stating and proving safeness and completeness of the navigation graph, we state a few useful lemmas. The first lemma relates the flip of transformed queries to the transformation of flipped queries.

Lemma 5.1: For every query q, focus φ ∈ Φ(q), and query q ′ , we verify:

1. flip(q[φ and q ′ φ ′ ], φ ′ ) = flip(q, φ) and q ′ , 2. flip(q[φ and not q ′ φ ′ ], φ ′ ) = flip(q, φ) and q ′ , (see remarks after Definition 5.1) 3. flip(q[φ or q ′ φ ′ ], φ ′ ) = flip(q[φ := ?], φ) and q ′ .

The second lemma states that intersection navigation links behave as in standard faceted search: intersection with a feature f leads to a navigation place, whose set of items is the intersection between the previous selection and the set of items matching that feature f . Lemma 5.2: For every query q, focus φ ∈ Φ(q), and feature f , the following equality holds: items((q, φ)[and f ]) = items(q, φ) ∩ items(f ).

Proof: items((q, φ)[and f ]) = items(q[φ and f φ ′ ], φ ′ ) (Definition 5.4) = items(flip(q[φ and f φ ′ ], φ ′ )) (Definition 5.2) = items(flip(q, φ) and f ) (Lemma 5.1) = items(flip(q, φ)) ∩ items(f ) (Definition 4.1) = items(q, φ) ∩ items(f ) (Definition 5.2)

The third lemma states that deletion navigation links can only make the set of items larger, and therefore cannot lead to dead-ends.

Lemma 5.3: For every query q, focus φ ∈ Φ(q), the following equality holds: items((q, φ)[delete]) ⊇ items(q, φ).

Safeness

Safeness is an important property to be retained from faceted search. A navigation graph is safe if no navigation path leads to a dead-end, unless it starts with a deadend. Safeness prevents frustation in user experience. We prove that navigation graphs are safe, apart from the use of focus change (see discussion below).

Theorem 1: 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 ′ , φ ′ ) = ∅.

Proof: It suffices to prove that every navigation link l that is not a focus change is safe, i.e., that items((q, φ)[l]) = ∅ assuming that items(q, φ) = ∅. The proof is based on Definitions 5.2, 5.3, 5.4 and Lemmas 5.1, 5.2.

intersection: items((q, φ)[and f ])

= items(q, φ) ∩ items(f ) (Lemma 5.2) = ∅ because f ∈ restr (q, φ) (Definition 5.3).

exclusion: items((q, φ)[and not ?]) = items(q[φ and not ? φ ′ ], φ ′ ) (Definition 5.4) = items(flip(q[φ and not ? φ ′ ], φ ′ )) (Definition 5.2) = items(flip(q, φ) and ?) = items(flip(q, φ)) (Lemma 5.1) = items(q, φ) = ∅.

union: items((q, φ)[or ?]) = items(q[φ or ?

φ ′ ], φ ′ ) (Definition 5.4) = items(q[φ := q[φ] or ? φ ′ ], φ ′ ) (Definition 4.3) = items(q[φ := ? φ ], φ) (? is absorbing for union) = items((q, φ)[delete]) (Definition 5.4) ⊇ items(q, φ) = ∅ (Lemma 5.3) = ∅. name: items((q, φ)[name ?v]) = items(q[φ and ?v φ ′ ], φ ′ ) (Definition 5.4) = items(flip(q[φ and ?v φ ′ ], φ ′ )) (Definition 5.2) = items(flip(q, φ) and ?v) (Lemma 5.1) = items(flip(q, φ)) (because v is a fresh variable) = items(q, φ) = ∅. reference: items((q, φ)[ref ?v]) = ∅ by Definition 5.4. delete: items((q, φ)[delete]) ⊇ items(q, φ) (Lemma 5.3) = ∅.
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 navigation link notation (l) target ((q ′ , φ ′ ) = (q, φ)[l]) 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 ′ , φ ′ ) = ∅ deletion delete (q[φ := ?], φ)

Table 4 Definition of the set of navigation links linking a navigation place (q, φ) to the target navigation place (q ′ , φ ′ ).

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 .

Completeness

Completeness is a key contribution of our approach, and is based on the explicit definition of a query language.

A navigation graph is complete if there is a navigation path to every query that is not a dead-end, starting from the initial navigation place p 0 . Completeness is important because it completely removes the need to manually edit queries, which makes guided navigation as expressive as the query language, here LISQL. This suggests that, in order to improve the expressiveness of semantic faceted search, one should first extend the query language, then extend the navigation graph with additional navigation links (i.e., query transformations), and finally prove safeness and completeness. To be precise, completeness is proved for safe queries, i.e., queries without an unsafe focus change.

Definition 5.5: A query q is said to be safe under φ ∈ Φ(q), which we note safe(q, φ), if for every focus φ ′ ∈ Φ(q) that is equal to or under φ in the syntax tree of q, we have items(q, φ ′ ) = ∅. Query q is said safe, which we note safe(q), if it is safe under its root focus. By extension, we say that a navigation place (q, φ) is safe if safe(q, φ) holds.

Before stating and proving the main theorem on completeness, we need a few lemmas on the conservation of the safeness of queries when they are simplified. The proofs, not given here, are based on the translation of queries to SPARQL (Definition 4.4).

Lemma 5.4: For every query q, and focus φ ∈ Φ(q), if safe(q, φ), then the following propositions hold:

1. safe(q[φ := ?], φ), 2. q[φ] = (q 1 and q 2 ) ⇒ safe(q[φ := q 1 ], φ), 3. q[φ] = (q 1 or q 2 ) ⇒ safe(q[φ := q 1 ], φ), 4. q[φ] = (p : q 1 ) ⇒ safe(q[φ := p : ?], φ), 5. q[φ] = (p of q 1 ) ⇒ safe(q[φ := p of ?], φ).

Theorem 2: 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 safe query q, there is a navigation path from the initial navigation place p 0 to the navigation place (q φ , φ).

Proof: Suppose we have a navigation link [and q] for every safe query q, with the same definition as intersection with a restriction [and f ] (Table 4). Then it would be possible to navigate (in one step) from the initial place p0 to the place (? and q φ , φ), which is equivalent to (q φ , φ).

Therefore, we can prove completeness by showing how the hypothetical navigation link [and q] can be decomposed into a valid and finite navigation path, for every safe query q.

The following table defines such a finite decomposition by induction on the structure of q. q [and q φ ] r

[and r] a c

[and a c] ?v It remains to prove that every navigation step of the decomposition is a valid navigation link, according to Table 4. The first step is to prove that every intermediate navigation place is safe. This can be done by recurrence, where the recurrence hypothesis says that for every subquery, the initial and final places are safe. This is true for the whole query q (the base case), because q is assumed safe under φ, and p0 is trivially safe. For subqueries that are decomposed into several navigation steps, the intermediate vertices can be proved safe by applying Lemma 5.4.

[name ?v] (if v is new) [ref ?v] (
Finally, every atomic navigation link can be proved valid. Focus change, exclusion, union, and deletion are always valid navigation links. For intersection and reference, we can use the fact that every intermediate place is safe, and therefore that every intermediate place has a non-empty set of items. This is enough for reference. For intersection, we can use Lemma 5.2 to prove that the feature f is a restriction.

This proof also provides an algorithm for finding a path from the initial navigation place to the target query q. It exhibits a linear complexity: the path has a length that is linear in the size of the target query.

The restriction of completeness to safe queries is not a problem in practice because every query q such that items(q) = ∅ (the query has answers) and not safe(q) (the query has no answer at some focus) can be simplified into a safe yet equivalent query. It suffices to delete from the query empty alternatives, and empty exclusions. An empty exclusion is a subquery (not q 1φ1 ) s.t. items(q, φ 1 ) = ∅; and an empty alternative is either q 1 or q 2 in a subquery (q 1φ1 or q 2φ2 ) s.t. items(q, φ 1 ) = ∅ or items(q, φ 2 ) = ∅. The simplified query is equivalent to the original query in that it has the same set of items at every remaining focus, and it is safe.

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 5.4. 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 5.2 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 engine, possibly reusing existing query engines for the Semantic Web (see Section 4.3).

Computing the set of restrictions is equivalent to setbased faceted search, i.e., amounts to compute set intersections between the set of items of the current navigation place 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 that 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.

User Interface and Interaction

Query-based Faceted Search has been implemented as a prototype, Sewelis 4 . Figure 2 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 transformations (QT), a suggestion area (S) that is mainly composed of a facet hierarchy (F), a set of value boxes (V), and an answer list (A). A query engine can be derived from Sewelis by retaining only the components Q and A. A standard faceted search system can be derived by retaining only the components A, F, and V.

The query box displays the current LISQL query q, where the current focus φ is rendered by highlighting the subquery q[φ]. In Figure 2, the whole query is highlighted because the current focus is the root focus. For a better readability of queries, we use indentation instead of brackets, URIs are represented by their labels if available or abbreviated as qualified names if possible, a concrete syntax is used for some datatypes (e.g., 42 instead of "42"ˆˆxsd:integer), and resources are colored according to their kind (orange for classes, purple for properties, blue for other URIs, and green for literals).

The suggestion area (S) contains the set of restrictions for the current set of items. In fact, that set of items is a subset of the restrictions, and is displayed in the answer list (A). The classic restrictions, pairs facetvalue, are found in value boxes (V), one for each applicable property (p : ?) and inverse property (p of ?). If that property is transitive (an instance of the class owl:TransitiveProperty), then the values are organized hierarchically accordingly. For instance, the value box of ancestor : ? displays a descendancy chart, while the value box of ancestor of ? displays an ancestry chart. Similarly, the value box of part of ? displays a taxonomy of locations. Other kinds of restrictions are placed in the facet box (F). This includes co-reference variables (e.g., ?X), classes as types (e.g., a man), and properties as domains (e.g., parent : ?) and ranges (e.g., child of ?). Classes and properties are hierarchically organized according to the rdfs:subClassOf and rdfs:subPropertyOf transitive properties. For instance, in Figure 2, the class a man is a subclass of a person; and the properties father : ? and mother : ? are subproperties of parent : ?, which is itself a subproperty of ancestor : ?. In order to increase user feedback about suggestions, each restriction is prefixed by the number of answers that match that restriction. If a restriction matches all answers, that number is highlighted like the focus. If two restrictions match the same subset of answers, this is indicated by highlighting the two numbers with a same color. Finally, a dim font is used for restrictions that are included in the current query, hence emphasizing the other restrictions as "new". For example, in Figure 2, the restriction a man (bold font) is a way to make the query more specific, while a person (dim font) is already in the query (at the current focus). The buttons "More" and "Less" are out the scope of this paper, and are mostly used when editing the RDF graph [START_REF] Hermann | Guided creation and update of objects in rdf(s) bases[END_REF].

Navigation links, i.e. the application of query transformations, are available on most components (T,Q,QT,S). Focus changes can be triggered by clicking on the subquery of interest in Q, by keystrokes (CTRL + arrows), or by pushing the button "Focus Up" in QT. Intersection with a feature and reference to a variable can be performed by double-clicking a restriction in the suggestion area (S). Other navigation links are available as buttons in the component QT (Query Transformations): " or ?" for union, " and not ?" for exclusion, "Name" for naming, and "Delete" for deletion. Other useful transformations are available in QT and T areas: "Back" and "Forward" for navigating in the history of navigation places, "Root" for jumping to the initial navigation place that contains all resources of the dataset, "Home" for jumping to the user-defined home query, "P and P ?" for adding a value to the same property (e.g., for describing a second child), "not " for (un)applying negation on the current subquery, "{ }" for (un)quoting the current subquery as a literal, "Describe" for replacing a resource by its full description in the query, "Select" for selecting the subquery and removing the rest of the current query, "Reverse" for reformulating the query from the current focus. Other buttons ("Assert", "Retract", "...") are used for edition.

The entry field at the top of the suggestion area (S) and below the focus in the query box (Q) enables to find and select a restriction by auto-completion. This is useful when the number of restrictions is high, and the user has a clue on the text of the restriction. Matching is performed on the syntax of restrictions as rendered in the user interface, which is based on labels (using rdfs:label). For instance, the URI of George Washington can be retrieved by entering any of "Georges Wash", "geo wa", or even "Wash ge". The list of possible completion is updated after every keystroke. The "Create" menu near entry fields gives access to domain-specific dialogs for choosing dates, times, and filenames.

In Sewelis, data can be loaded either by importing RDF files in various formats (RDF/XML, N-Triples, Turtle), or by dereferencing URIs according to the Linked Data 5 principles. The former is available in the "File" menu, and the latter is available on every restriction that includes a URI through the contextual menu. The same contextual menu also provides means to improve the presentation of restrictions by defining labels and namespaces. Sewelis supports RDFS inference, as well as some OWL inference on properties (owl:TransitiveProperty, owl:SymmetricProperty, owl:inverse).

Usability Evaluation

This section reports on the evaluation of QFS in terms of usability 6 . 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.

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, nor of US presidents. 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 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 (System Usability Scale [START_REF] Brooke | SUS: A quick and dirty usability scale[END_REF]) and open questions. The test was composed of 18 questions, with smoothly increasing difficulty. Table 5 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. The first category, Visualization, did not require the creation of a query. The exploration of the suggested restrictions 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 unions: e.g., "Which women have for mother Jane Butler or Mary Ball?". The fifth category, Negation, required to use exclusions: e.g., "How many women have a mother whose death's place is not Warner Hall?". The sixth category, Inverse, required the backward crossing of a property: e.g., "Who was born in the same place as Robert Washington?". In the seventh category, Cycle, required the use of co-references: e.g., "How many persons have the same firstname as one of their parent?".

Results. Figure 3 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 response 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, which we know from the navigation trace of subjects.

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. Among all questions, the worst success rate is 50 percent. 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 questions 2 and 3 (we know this from the navigation traces). 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 to solve the Inverse questions with a reasonable success rate, and a decreasing response time.

SUS Questionnaire. Table 6 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 SUS Question (polarity) 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 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

Related Work

We discuss other approaches for applying and extending faceted search to the Semantic Web. We also compare the expressiveness of LISQL with two expressive query languages of the Semantic Web: SPARQL and SPARQL-DL.

Faceted Search for the Semantic Web

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]), mSpace 7 , and Longwell 8 , do not claim for a contribution in term of expressiveness, and contribute either to the design of better interfaces and visualizations, or to methods for the rapid or usercentric configuration of faceted views [START_REF] Suominen | Usercentric faceted search for semantic portals[END_REF]). Therefore, their contributions are somewhat orthogonal to ours, and could certainly complement them.

Other approaches, such as 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], 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 has 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 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. On our case, the query is also important to specify focus changes. Of course, displaying the query in SPARQL would ruin those benefits: the display of the query is part of the design of the user interface. Now, when the expressiveness is raised to SPARQL with graph patterns, disjunction, and negation, it becomes necessary to introduce syntax. While, in Sewelis, 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). In our approach, LISQL is used to render the query in a way that fits query-based faceted search (see Section 4.1).

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 (e.g., not father : ?) in BrowseRDF. No other system allows to form cycles as we do with co-references.

The value boxes of SlashFacet can handle only one taxonomy of values, whereas we can use any transitive property that link the values together. For instance, when values are persons, we can use either ancestor : (descendancy chart), or ancestor of (ancestry chart).

Query Languages for the Semantic Web

We compare our query language LISQL to SPARQL, as the reference query language for the Semantic Web, and to SPARQL-DL [START_REF] Sirin | SPARQL-DL: SPARQL query for OWL-DL[END_REF] for the syntactic similarity of complex classes with LISQL queries.

Comparison with SPARQL

Haase et al. ( 2004) define a set of 14 use cases for comparing the expressiveness of RDF query languages. We use them to evaluate and compare the expressiveness of SPARQL and LISQL. First, a significant difference is that LISQL has mono-dimensional queries, i.e., LISQL queries are translated to SPARQL queries having a single variable after SELECT. This constraint comes from the nature of faceted search, not from LISQL itself as several foci could be selected to have several variables after SELECT. The facet hierarchy, the value boxes, and a highlighting mechanism compensate for this constraint. Assume users want to know who is the mother of each male Washington. They first navigate to the query a man and lastname : Washington. Then, they expand the facet mother : ? in the facet hierarchy, which opens a value box that lists the mothers of male Washingtons, and for each mother, tells how many children she has among them. The associations between male Washingtons and their mothers are accessible by a dynamic highlighting mechanism. When selecting a male Washington (in the extension box), his mother is highlighted in the value box. Symmetrically, when a mother is selected in the value box, her children are highlighted in the extension box.

The use cases that SPARQL and LISQL have in common are path expressions (e.g., "the name of the author of some publication X"), union, partial support for collections and containers, support for literals, and entailment through class and property hierarchies. Compared to SPARQL, LISQL has not the OPTIONAL construct because it is useless in one-dimensional queries. However, it covers the difference use case with the complement construct (not), and recursion through transitive properties. The difference use case is covered in extensions of SPARQL with the operator MINUS of [START_REF] Angles | The expressive power of SPARQL[END_REF], or the operator NOT EXISTS of SPARQL 1.1. The recursion use case is covered in nSPARQL [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF], an extension of SPARQL with nested regular expressions. The reification use case is covered by SPARQL: e.g., "the person who has classified the publication X". As defined in Section 4.1, LISQL does not cover it, but its implementation in Sewelis does. The LISQL query for the previous example is (a publication and ?X and topic [classifier : ?] : ?), where the subquery into square brackets after topic put a constraint on the reified triple whose predicate is topic. This query can be navigated to, in the same way as other queries.

In total, SPARQL scores 9.5/14, LISQL scores 8/14, as defined in Section 4.1, and scores 10/14, as implemented in Sewelis. In fact, SPARQL and LISQL have a similar expressiveness, and most differences can be removed by extending either language: adding difference and recursion to SPARQL; adding multiple foci and optional pattern to LISQL.

Comparison with SPARQL-DL

Syntactically, LISQL queries are similar to complex classes as defined in OWL-DL. This suggests that SPARQL-DL [START_REF] Sirin | SPARQL-DL: SPARQL query for OWL-DL[END_REF]) could be used instead of SPARQL to translate from the LISQL syntax. However, this is not possible because SPARQL-DL is restricted to conjunctive queries, and variables can-not occur in complex classes. On one hand, a LISQL query that contains unions and complements but no variables (hence no cycles) and the root focus, can be translated to a SPARQL-DL query in the form Type(?x,q), where q is a complex class that has the same abstract syntax as the LISQL query. For example, the LISQL query a man and birth : (year : (1601 or 1649) and place : not part of England) can be translated to Type (?x, and( man, some(birth, and( some(year, or({1601},{1649})), some(place, not(some(partOf, {England}))) )))).

On the other hand, a LISQL query that contains variables but neither union nor complement, can be translated in a similar way to SPARQL-DL, using in fact the common subset between SPARQL and SPARQL-DL. For example, the LISQL query a man and father : ?X and mother : spouse of ?X can be translated to Type(?z,man), PropertyValue(?z,father,?x), PropertyValue(?z,mother,?y), PropertyValue(?x,spouse,?y).

The two kinds of translations cannot be reconciled in the general case, in particular when variables occur in the scope of unions or complements.

In fact, SPARQL-DL and LISQL work at different levels, and might complement each other by benefiting from a comparable syntax. SPARQL-DL, like OWL-DL, works at the intentional level, whereas LISQL and SPARQL work at the extensional level. The intentional level is associated to open world assumption, and ontological reasoning. The extensional level is associated to closed world assumption, and query answering over a unique and finite interpretation, namely a RDF graph.

Conclusion

We have introduced Query-based Faceted Search (QFS) 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. Exploratory search is formalized as a navigation graph, where navigation places are queries, and navigation links are query transformations. The navigation graph is proved to be safe, because whatever the path of navigation links, the current set of items is never empty. It is also proved complete w.r.t. the query language, because for every safe query, there is a navigation path that leads to it. Finally, it is as efficient as standard faceted search w.r.t. the computation of facets and restrictions. The completeness proof is the key result here because it draws an equivalence between expressive querying and exploratory search, therefore totally freeing users from editing queries, even the most complex ones.

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 or to remove query parts. It also adds a few controls for applying some query transformations such as insertion/deletion of unions, complements, and co-references. Query transformations determines a new query language, LISQL, that is similar to SPARQL in terms of expressiveness, and with a more compact syntax. Beside the list of selected items, the user interface has a hierarchy of facets organizing classes and properties by subsumption, and value boxes that can be displayed as flat lists or as various taxonomies automatically derived from the dataset.

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 cycles. This means semantic faceted search retains the ease-of-use of other faceted search systems, while offering the expressiveness of query languages such as SPARQL.

We think that QFS is not tied to LISQL, and could be adapted to other query languages. Indeed, the definition of a navigation graph only requires the definition of the answers of a query, and the definition of query transformations. The hard part is then to prove that the resulting navigation graph is safe and complete, which we have successfully done here for LISQL.

As future work, our main objective is to fully match the expressiveness of SPARQL 1.1 by extending QFS to the few missing features: multi-dimensional queries and the OPTIONAL construct, aggregations and expressions, and built-in predicates. Other objectives are to integrate Sewelis with existing SW tools (e.g., Solr/Lucence-index for fast literal-indexing), and to perform more user evaluation in order to improve its user interface.

Figure 1

 1 Figure1A graphical representation of a graph pattern.

  ? φ0 [φ 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].

Figure 2 A

 2 Figure 2 A screenshot of the user interface of Sewelis. It shows the selection of "persons born in 1601 or 1649 somewhere in England, and whose father was born at another place".

Table 1

 1

	defines the syntax and

Table 1

 1 Syntax, semantics, and examples of the various kinds of features.

	Those operations can be used in addition to intersection,
	union, and exclusion (e.g., /facet, SOR, gFacet, Visi-
	Nav). The operation p(S, .) is crossing forward p from the
	selection S, while the operation p(., S) is crossing back-
	wards. For example, starting from a set S of persons,
	gen:lastname(S, .) returns their lastnames, while start-
	ing from a set of lastnames, gen:lastname(., S) returns
	the set of persons having one of those lastnames. Ta-
	ble 2 defines the various kinds of operations that can be
	used to navigate from one selection to another. Crossings
	apply to domain and range restrictions, while other oper-
	operation	syntax	semantics
	reset	?	S 0
	intersection	S and f	S ∩ items(f )
	exclusion	S and not f S \ items(f )
	union	S or f	S ∪ items(f )
	crossing backwards p : S	p(., S)
	crossing forwards	p of S	p(S, .)

ations apply to arbitrary restrictions. In order to better expose the limits of set-based faceted search, we introduce in the table a syntax for those operations, where S denotes the current selection.

Table 2

 2 Syntax and semantics of the various kinds of set-based operations.

Table 6

 6 Results of SUS questions.

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. We also thank the reviewers for their useful remarks.

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) Negation 10 How many men were born in the 1600 or 1700 years, and not in Norfolk? (12) 13 How many women have a mother whose death's place is not Warner Hall? ( 7) 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).


Alice Hermann
email: hermanal@irisa.fr

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

Mireille Ducassé
email: ducasse@irisa.fr

Guided Semantic Annotation of Comic Panels with Sewelis

UTILIS (Updating Through Interaction in Logical Information Systems), introduced in a research paper at EKAW'12, is an interactive process to help users create new objects in a RDF graph. While creating a new object, relaxation rules are applied to its current description to find similar objects, whose properties serve as suggestions to expand the description. UTILIS is implemented in Sewelis, a system that reconciles the expressiveness of querying languages (e.g., SPARQL), and the benefits of exploratory search found in faceted search. The same interaction principles are used for both exploration and creation of semantic data. We illustrate the UTILIS approach by applying Sewelis to the semantic annotation of comic panels, reusing the dataset that was used for a user evaluation.

Motivation

Authoring Semantic Web (SW) data is crucial to take into account information that cannot be extracted automatically from existing documents (e.g., multimedia data, subjective judgements). This is, however, tedious and in practice data from the SW are rarely directly produced by users. In the Web 2.0, users, nevertheless, significantly contribute to the production of data, thus, motivation is not a problem. Models exist to bridge the gap between the SW and the Web 2.0, for example by linking tags created by users with SW vocabulary [START_REF] Passant | Meaning of a tag: A collaborative approach to bridge the gap between tagging and linked data[END_REF][START_REF] Limpens | Sémantique des folksonomies: structuration collaborative et assistée[END_REF]. There are, however, still difficulties to integrate the Web 2.0 data in SW, for example to automatically align users tags and resources of the SW. Moreover, SW data is richer than user tags. SW indeed allows a more complex representation of data, as well as more elaborate queries. It is therefore important to allow users to directly create data in a SW format.

There exists a number of editors that can guide users in the production of semantic data. They can be dedicated tools (e.g., Protégé, OKM, Gino, QuiKey) or integrated into Wiki environments (e.g., SMW (Semantic Media Wiki), KiWI, ACEWiki). Their interface can be based on forms (e.g., Protégé, OKM, SMW), on natural language (e.g., Gino, ACEWiki), or only allow for the creation of one triple (or semantic link) at a time (e.g., KiWI, Quikey). Those editors have a number of limits regarding their applicability or their guiding. First, many editors require the definition of a schema or an ontology to make any suggestion (e.g., defining domains and ranges of properties). However, defining an ontology may be even harder than describing instances. Second, most editors only use the ontology axioms, not the facts, to compute suggestions. However, existing instances could serve as models for new instances, possibly in a more precise way than ontology axioms. Other editors hardly use known information about the new instance to compute suggestions. Fourth, most editors require users to enter at least a few letters to give suggestions, because their suggestions are not fine-tuned to the new instance.

The main contribution of our approach, UTILIS (Updating Through Interaction with Logical Information Systems), is to provide an interaction process that helps users to consistently create new objects by suggesting properties and values finely adapted to the very object being created. The already known properties of a new object are used to suggest others. Let us assume that a user annotates a new comic panel, and has already specified its collection. It is likely that this panel and those of the same collection have characters in common, which should then be suggested before other characters. The process uses a set of relaxation rules, inspired by the work of Hurtado et al. [9], and an efficient algorithm for computing suggestions. An advantage of our approach is that the definition of an ontology is not necessary to compute the suggestions, although UTILIS may use ontology axioms to improve its suggestions when they are available.

UTILIS : An Interactive Guidance

UTILIS searches for objects similar to the description of a new object, i.e., objects having common properties and values. Figure 1 illustrates the interactive process to refine the description of a new object. The initial query is obtained from the current description of a new object and from a focus which is an element of the description that the user wants to complete. This description is transformed into a query. That query is used as a starting point to obtain generalized queries using relaxation rules. The initial and generalized queries allow similar objects to be retrieved. Those objects and their properties are used as suggestions to complete the new description. After refinement, the new description will be used to define a new query and so on. For more information on the approach, and a user evaluation, please look at the related research paper at EKAW'12 [START_REF] Hermann | An interactive guidance process supporting consistent updates of RDFS graphs[END_REF].

Implementation in Sewelis

UTILIS is implemented in Sewelis3 . Sewelis has been designed for the exploration of a RDF base, and is based on Query-based Faceted Search (QFS) [START_REF] Ferré | Semantic search: Reconciling expressive querying and exploratory search[END_REF]. It guides users in the construction of complex queries by suggesting query transformations that play the role of navigation links. The guidance avoid users to fall in deadends (i.e., empty results), and offers an expressiveness close to SPARQL.

When Sewelis is used to edit of a RDF base, the current query becomes the current description of the new object, and suggested transformations are computed according to the UTILIS approach, as presented in the previous section. To present suggestions to the user and allow him to complete the description of the new object, the interaction mechanisms of Sewelis, initially dedicated to navigation, have been reused to support creation. By default, only the suggestions at the smallest distance are displayed, then the list can be enlarged to bigger distances upon user's request, until all objects compatible with the searched element are proposed. At any time, users can manually enter what they want to add. That is necessary for the new values. An alternative way to find existing values is through an auto-completion.

Figure 2 shows the user interface. The current description is on the left side, here the panel K is a panel from the Ma vie à deux Collection, with Missbean and Fatbean as characters, it has a speech bubble said by someone. On the right side, suggested resources for the focus are listed, here the speakers. Suggested classes and properties are in the middle part. Above that area, the number of similar objects is displayed and a More button allows them to be expanded to larger distances. From there on, the user can continue the description of the panel and when he decides that it is complete, he adds it to the base with the Assert button.

Demonstration

The demonstration develops an edition scenario of a comics knowledge base that is only partially annotated. It consists of 362 individuals, including 89 panels, divided into 16 classes and connected by 20 properties. The base describes a subset of the panels by their characters, bubbles, places, and other elements; and describes bubbles by their speakers, recipients, and text. In the user evaluation we organized, the subjects had to complete the knowledge base by annotating the not-yet-described panels along the lines of the already-described panels. The demonstration will consist in re-playing this task, and the participant will be able to put hands on. The various situations that can occur will be illustrated:

a description element (i.e., a class, a property or a value) is found in the set of suggestions, -a description element is found by performing a few enlargments of the set of suggestions,

a description element is found through auto-completion, -a new value is created, -a new class is created, -a new property is created. The UTILIS suggestions favor the reuse of existing elements upon the creation of new ones, which favors the consistency of the knowledge base by avoiding the creation of duplicates. It also favors the completeness of the base by encouraging users to fill all properties used for previous objects.

Fig. 1 .

 1 Fig. 1. Interactive refinement of the description of a new object.

Fig. 2 .

 2 Fig. 2. Screenshot of Sewelis. On the left side, the description of new object is shown, here the panel K is a panel from the Ma vie à deux Collection, with Missbean and Fatbean as characters, it has a speech bubble said by someone. On the right side, suggested resources for the focus are listed, here the speakers.

http://www.irisa.fr/LIS/softwares/sewelis