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

Expressive and Scalable Query-based Faceted Search over SPARQL Endpoints

Linked data is increasingly available through SPARQL endpoints, but exploration and question answering by regular Web users largely remain an open challenge. Users have to choose between the expressivity of formal languages such as SPARQL, and the usability of tools based on navigation and visualization. In a previous work, we have proposed Query-based Faceted Search (QFS) as a way to reconcile the expressivity of formal languages and the usability of faceted search. In this paper, we further reconcile QFS with scalability and portability by building QFS over SPARQL endpoints. We also improve expressivity and readability. Many SPARQL features are now covered: multidimensional queries, union, negation, optional, filters, aggregations, ordering. Queries are now verbalized in English, so that no knowledge of SPARQL is ever necessary. All of this is implemented in a portable Web application, Sparklis 1 , and has been evaluated on many endpoints and questions.

Introduction

Linked data is increasingly available through SPARQL endpoints, but exploration and question answering is often tedious for SPARQL practitionners, and largely remains an open challenge for regular Web users. Semantic search can be evaluated according to a number of criteria such as expressivity or scalability. Maximizing any of those criteria in isolation is relatively easy, and what remains a challenge is to reconcile them as far as possible. We consider such a reconciliation as a key to the effective access to semantic data, and hence to the wide adoption of semantic data. Indeed, an easy-to-use system may not satisfy advanced users with more complex information needs, and everybody can become an advanced user in some domain (e.g., profession, hobby). Similarly, an expressive system that does not scale is only of limited use. We shortly define the criteria that motivated this work, and identify for each of them the existing approach that seems to best fulfill it.

Expressivity measures the diversity and complexity of questions that can be answered. It seems clear that the leading approach for maximizing that criteria is formal query languages, and prominently SPARQL.

Guidance measures the level of assistance given to users in their search. It involves interactivity, suggestion, immediate feedback, and dead-ends prevention. We here retain Faceted Search (FS) [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]. First, FS is increasingly adopted in e-commerce and multimedia collections. Second, FS has already been adapted to semantic search (see Section 2). Readability measures the ease for users to read and understand the textual components and controls of the user interface. Natural Language (NL) is obviously more readable than formal languages like SPARQL. If formal queries are used in a system, they should therefore be verbalized into NL, which has already been proposed for SPARQL [START_REF] Ngomo | Sorry, I don't speak SPARQL: translating SPARQL queries into natural language[END_REF]. Scalability measures the ability of a system to be responsive on large datasets.

Most of the scalability effort in the semantic web has gone into RDF stores and SPARQL engines. It therefore seems reasonable to leverage their power. Portability measures the cost of applying a system to a new dataset. Some systems require manual configuration, and others need an appropriate ontology. SPARQL endpoints have the advantage to provide a standard API.

Guidance and readability are two aspects of usability that we address in this paper. Other aspects that we do not consider here are a smooth learning curve or personalization. Another important criteria for semantic search that is not addressed in this paper is openness. It measures the ability to explore distributed linked data (querying several endpoints, following owl:sameAs links). In a previous work, we have introduced Query-based Faceted Search (QFS) [START_REF] Ferré | Reconciling faceted search and query languages for the Semantic Web[END_REF][START_REF] Ferré | Semantic search: Reconciling expressive querying and exploratory search[END_REF] as a way to reconcile the expressivity of formal query languages with the guidance of faceted search. The obtained user interaction is similar to query builders that guide users in the construction of queries, but with a more fine-grained guidance that is based on actual data rather than on syntax and data schema.

The first contribution of this paper is to further reconcile QFS with the readability of NL. Questions and system suggestions are verbalized in (a fragment of) English so that no knowledge of SPARQL is ever necessary for users. This makes QFS a kind of Natural Language Interface (NLI) except that questions are not freely input by users, but produced through a user-system dialog. The second contribution is to further reconcile QFS with the scalability and portability of SPARQL endpoints. Question answers and system suggestions are entirely computed by generating and sending SPARQL queries to the endpoint. Portability is ensured by strictly conforming to the SPARQL standard. Compared to previous work, we also improve QFS expressivity. In addition to arbitrary basic graph patterns, unions, and negations, we now also cover multidimensional queries (tables as results), optionals, common filters, aggregations, and orderings. All those contributions are implemented in a Web application, Sparklis, that only needs the URL of the desired endpoint as input.

The main limitation to our work is that it only provides bare views of linked data, without any pre-or post-processing, and therefore exposes any data noise and heterogeneity to users. It uses neither linguistic knowledge (e.g., lexicons), nor external resources (e.g., full-text indexes) to make it more readable and efficient. We made this choice for the sake of portability, genericity, and sim-plicity, but nothing prevents to customize and improve our approach by using dataset-specific knowledge and resources.

Section 2 is an overview of different approaches and systems in semantic search (Section 2). Section 3 recalls the key principles of QFS to reconcile expressivity and guidance. Section 4 and 5 present the contributions of this paper: NL verbalization and QFS over SPARQL endpoints. Section 6 provides the results of a few evaluations of Sparklis w.r.t. the above criteria. Finally, Section 7 concludes and sketches future work.

Related Work

There are mainly two approaches to make semantic search more usable: user interaction (UI) and natural language (NL). UI systems reuse and adapt UI paradigms to semantic data: hypertext browsing (e.g., Fluidops Information Workbench2 ), query builders (e.g., SemanticCrystal [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF]), faceted search (FS) [START_REF]Dynamic taxonomies and faceted search. The information retrieval series[END_REF], or OLAP [START_REF] Codd | Providing OLAP (On-line Analytical Processing) to User-Analysts: An IT Mandate[END_REF]. Query builders generally offer more expressivity, but lack readability because based on formal languages. Moreover, their guidance is mostly based on syntax, and sometimes on a data schema, but not on actual data, like in FS. Most FS-based systems do not claim for a contribution in term of expressivity, and contribute either to the design of better interfaces and visualizations, or to methods for the rapid or user-centric configuration of faceted views: e.g., Ontogator [START_REF] Mäkelä | Ontogator -a semantic view-based search engine service for web applications[END_REF], mSpace3 , Longwell4 . Similarly, OLAP-based systems emphasize visualization, and require substantial amount of configuration to extract cubic views over RDF graphs: e.g., Cubix [START_REF] Melo | Cubix: A visual analytics tool for conceptual and semantic data[END_REF], Linked Data Query Wizard [START_REF] Hoefler | Linked data query wizard: A tabular interface for the semantic web[END_REF]. Therefore, their contributions are somewhat orthogonal to ours, and could certainly complement them. A few FS-based systems extend faceted search expressivity: 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], 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], SemFacet [START_REF] Arenas | SemFacet: Semantic faceted search over YAGO[END_REF], OpenLink FS5 , Vinge Query&Explore6 . While more expressive than classical FS, those systems are still much less expressive than SPARQL 1.1, and approximately cover basic graph patterns. None of them support union, negation, or aggregation. All except Vinge Query&Explore present only lists of results, rather than tables. That expressivity is reflected by the frequent choice to use trees and graphs to represent the query. Those representations have a good match with SPARQL graph patterns, but do not scale well to express union, negation, or aggregations, unlike natural language.

Natural Language Interfaces (NLI) [START_REF] Lopez | Is question answering fit for the semantic web?: A survey[END_REF] use NL in various forms, going from full natural language (e.g., PowerAqua [START_REF] Lopez | PowerAqua: Supporting users in querying and exploring the semantic web[END_REF]) to mere keywords (e.g., NLP-Reduce [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF]) through controlled natural languages (e.g., Ginseng [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF], SQUALL [START_REF] Ferré | SQUALL: a controlled natural language for querying and updating RDF graphs[END_REF]). Systems based on full NL or keywords devote the most effort to bridging the gap between lexical forms and ontology triples (mapping and disambiguation), and process only the simplest questions, i.e., they generate SPARQL queries with only one or two triples. Most of them support none of aggregations (e.g., counting), comparatives, or superlatives, even though those features are relatively frequent. Some systems integrate the UI approach in NLIs to alleviate the habitability problem [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF], in which users have not a precise knowledge about what can be understood by the NLI system, and therefore can be frustrated by syntax errors or empty results. Those systems (e.g., Ginseng [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF], Atomate [START_REF] Van Kleek | Atomate it! enduser context-sensitive automation using heterogeneous information sources on the web[END_REF]) can be seen as query builders based on a controlled natural language. They improve the former with readability, and the latter with guidance, but they still lack the fine-grained guidance of FS that is necessary to fully solve the hability problem.

Query-based Faceted Search

In this section, we recall the key principles of Query-based Faceted Search (QFS) [START_REF] Ferré | Reconciling faceted search and query languages for the Semantic Web[END_REF][START_REF] Ferré | Semantic search: Reconciling expressive querying and exploratory search[END_REF], and how they enable to reconcile expressivity and guidance. QFS guidance relies on the interaction loop of Faceted Search (FS). FS guides users in the iterative refinement of a set of items. The key to QFS expressivity is to replace the set of items by a structured query, and to define the focus as a syntactic part of the query. System suggestions at each navigation step are therefore defined as query transformations, rather than as set-based operations. 1.

In short, we propose query-based FS as a generalization of classical set-based FS. It is a generalization because a set of items can be derived unambiguously from a query and focus (by query evaluation), while many queries may correspond to a given set of items. We have previously demonstrated that set-based FS has strong limits in terms of expressivity, which disappear with query-based FS [START_REF] Ferré | Reconciling faceted search and query languages for the Semantic Web[END_REF]. In particular, it becomes possible to navigate to arbitrary Boolean combinations of elementary queries.

Table 1 shows the successive queries, as verbalized in Sparklis (see Section 4), of a QFS navigation scenario that leads the user in 12 steps to a list of "Russian writers born since 1800, and ordered by decreasing number of written books". That scenario is only one of several possible scenarios leading to the same results: e.g., the birth date could have been constrained before the nationality. At each step, the bold part represents the newly inserted query element, chosen by the user at the previous step among system suggestions, and the underlined part represents the query focus that is used for the next query transformation. The query focus is moved simply by clicking on different parts of the query. The query elements that are suggested for insertion at query focus can be entities (e.g., Russian), classes (e.g., a Book), properties in both directions (e.g., is the author of, has birthDate), filters (e.g., after 1800), and various modifiers (e.g., number of, or). Figure 1 is a Sparklis screenshot at step 11, during the specification of an alternative nationality for the writer (Russian Empire as a synonym of Russians). The user interface is made of three parts: top, middle, bottom. The top part shows the current query, and highlights the current focus, here something. The first branch of disjunction is transparent to reflect the fact that it is ignored during the construction of the second branch. The bottom part is the result table of the current query, with a column for each entity/value in the query (here: writer, nationality, birth date, and number of books). Note that QFS has relational results (tables) whereas classical FS has sets (lists). The focus column, here the nationality, is highlighted. The middle part contains relevant query elements for insertion at the query focus. It is split in three lists. The first list contains entities (URIs) and values (literals) found in the focus column. It also enables the construction of filters over values. The second list contains concepts (classes and properties) that apply to entities/values found in the focus column. The third list contains modifiers that are applicable to the query focus, such as Boolean connectors, aggregation operators, and ordering. Each list provides auto-completion for quickly locating a query element (see Section 5.2). In addition to selecting a query element to insert it at query focus, the query part under focus can be deleted by clicking the red cross in the query.

NL Verbalization and SPARQL Translation

In this section, we improve previous work on QFS by verbalizing queries in NL for user display, and by translating them in SPARQL for evaluation by SPARQL endpoints. The current query and focus play a central role because they represent the full state of the navigation process. Results and suggestions are entirely computed from them. Their internal representation must be designed to facilitate three processes: (1) NL verbalization, (2) SPARQL translation, and (3) application of query transformations. Using SPARQL for internal representation would make (2) trivial, but (1) difficult as shown by previous work [START_REF] Ngomo | Sorry, I don't speak SPARQL: translating SPARQL queries into natural language[END_REF]. Using NL for internal representation would make (1) trivial, but (2) and (3) would be tedious because of the many peculiarities of NL. Our choice, inspired by state-of-the-art in the compilation of high-level programming languages, is to use Abstract Syntax Trees (AST) as an intermediate representation between NL and SPARQL. AST leaves are entities, values, and concepts. AST nodes correspond at the same time to NL syntactic structures, such as noun phrases (NP) or verb phrases (VP), and to SPARQL features, such as triple patterns or unions. The query focus, as a syntactic part of the query, is represented as a distinguished node of the AST of the query.

NL verbalization is performed by mapping AST leaves and nodes to NL expressions. Entities and concepts are verbalized by the local name of their URI, i.e. the part after the last sharp or slash. This choice was made for the sake of portability and efficiency, but future work will consider the use of RDFS labels and lexicons, e.g. represented in Lemon [START_REF] Mccrae | Linking lexical resources and ontologies on the semantic web with lemon[END_REF]. One or a few syntactic patterns are associated to each type of AST nodes. For example, syntactic patterns for relative clauses based on a property p are: that has p NP , whose p VP , and that is Fig. 2. SPARQL translation for the last query in the scenario of Table 1.

the p of NP . The choice of the pattern can depend on whether the object of the property is better verbalized as a NP or a VP . An example of that is visible in Table 1, when comparing steps 5 and 6: that has a birthDate becomes whose birthDate is after 1800 after the insertion of the filter. To render the correct precedences of Boolean connectors, indentation is used in the display of the verbalized query (see Figure 1). That makes the query more readable, and avoids the use of brackets. Finally, syntax coloring is used to differentiate the different kinds of query elements: class names (orange), property names (purple), entity names (blue), values (green), modifiers (red).

SPARQL translation is based on Montague grammars [START_REF] Dowty | Introduction to Montague Semantics[END_REF], which were invented to bridge the gap between NL and formal languages. Those are founded on lambda calculus, and are fully compositional in the sense that the meaning of a sentence is the direct result of the composition of the meaning of its parts. Here, the "meaning" of a sentence or any of its parts is represented with SPARQL patterns. For example, a VP is translated to a function from entities to graph patterns, while a NP is translated to a function from graph patterns to graph patterns. Note that, unlike translating from SPARQL to NL, translating from ASTs to SPARQL is deterministic, and can be performed very efficiently. Figure 2 shows the SPARQL translation of the final query in the above navigation scenario, as produced by Sparklis. Table 2 maps elements of Sparklis queries to SPARQL features, and hence provides an overview of the expressivity of Sparklis compared to SPARQL. Remember that QFS interaction loop allows to build arbitrary combinations of those query elements, provided that those combinations make sense in the dataset, i.e. results. For example, it is possible to use two aggregations in a same query, to perform ordering on an aggregated value, to follow arbitrary long property paths, or to define Boolean combinations of filters on a same variable. The main missing features compared to SPARQL 1.1 are: arbitrary expressions, only simple filters are available; subqueries, which are for example necessary to express nested aggregations; iterated property paths (operators + and *); named graphs (GRAPH) and federated search (SERVICE); CONSTRUCT and DESCRIBE queries; updates. Technical details about query/focus internal representation and SPARQL translation can be found in a research report [START_REF] Guyonvarch | Scalable Query-based Faceted Search on top of SPARQL Endpoints for Guided and Expressive Semantic Search[END_REF].

Scalable QFS over SPARQL Endpoints

In this section, we improve previous work on QFS by entirely defining the computation of results and suggestions on top of SPARQL endpoints, rather than with in-memory RDF stores. We also take care to make it scale to the largest endpoints by limiting the number of results and suggestions. To preserve guidance completeness, results and suggestions beyond that limit can be found with an intelligent auto-completion mechanism.

NL verbalization, SPARQL translation, and the application of query transformations are computationally cheap, and are all done entirely on the client side. The computation of results from the SPARQL query uses one HTTP request to the SPARQL endpoint at each step, and therefore costs the same as when using a classical query editor in an incremental way. Therefore, the only significant additional cost of QFS, compared to direct querying in SPARQL, is the computation of suggestions, i.e. the three lists in the middle of Figure 1. Indeed, the three lists must be computed at each navigation step.

Computation of Suggestion Lists

The first suggestion list contains possible entities/values at the focus. For example, in the query Give me a Writer that has a nationality (step 3), nationalities of a writer are possible entities. Those entities/values are exactly those in the focus column of the result table, and can therefore be computed efficiently on client side. The third list contains applicable modifiers. There are only a dozen modifiers, and their applicability can be decided efficiently by looking at the query/focus. The second list contains concepts that possibly apply to entities/values in the first list. Here, a client-side computation is incompatible with portability, because it would require a client-side knowledge of the dataset, such as an ontology or indices. Moreover, ontology-based suggestions would be less precise because they would provide general rules (e.g., "books generally have authors"), rather than concrete facts (e.g., "only 10 of those 200 books have a defined author"). In heterogeneous datasets, like DBpedia, ontology-based guidance would often lead to empty results, and hence user frustration. Computing suggested concepts therefore require to query the SPARQL endpoint, and is actually the main issue for the scalability of QFS.

Assuming SPARQL variable ?f is bound to a possible entity or value at focus, the possible classes can be obtained as the bindings of variable ?c in the triple pattern ?f a ?c. Similarly, possible properties can be obtained with the triple pattern ?f ?p [], and inverse properties with the pattern [] ?p ?f. The question is how to use those triple patterns into SPARQL queries so as to efficiently get lists of suggestions. There are several ways to do it. For the binding of ?f, the SPARQL translation of the query can be reused, or the entities/values of the focus column can be used into a large UNION pattern. Relative to the three kinds of suggestions (classes, properties, inverse properties), three queries can be used, or a single query using an UNION pattern. We made extensive experiments [START_REF] Guyonvarch | Scalable Query-based Faceted Search on top of SPARQL Endpoints for Guided and Expressive Semantic Search[END_REF] to compare the efficiency of the different options, and came to the conclusion that the best option is generally to use three queries, one for each kind of suggestion, and to avoid the recomputation of the main query by using an UNION pattern over all focus entities/values: f1, f2, . . . . In principle, each triple pattern is efficiently evaluated by RDF stores using classical indices, because it contains one resource (URI or literal), and one unbound variable.

It remains to define the computation of suggestions at the initial step, when the query is still empty, and therefore no focus entity/value is available. That computation is crucial to provide guidance from the beginning. In a first stage, we use the following efficient SPARQL queries to retrieve classes and properties: Q1: SELECT DISTINCT ?c WHERE { ?c a rdfs:Class } Q2: SELECT DISTINCT ?p WHERE { ?p a rdf:Property } In SPARQL endpoints whose RDF graph does not contain the schema itself, the above queries return empty results. We then resort to the following queries which are less efficient, but have the advantage to reflect actual data.

Q1': SELECT DISTINCT ?c WHERE { [] a ?c } Q2': SELECT DISTINCT ?p WHERE { [] ?p [] }

Although not mentioned for the sake of generality, all above SPARQL queries come in practice with a LIMIT clause to better control response times. We discuss in the next section the impact on the completeness of the guidance, and how it is addressed in Sparklis.

Intelligent Auto-Completion

There are two important properties for QFS guidance: safeness and completeness. A safe guidance avoids dead-ends (i.e., empty results) by providing only relevant suggestions, i.e. suggestions that match actual data. A complete guidance fulfills the expressivity potential by providing all relevant suggestions. In a previous work [START_REF] Ferré | Reconciling faceted search and query languages for the Semantic Web[END_REF], we formally proved the theoretical safeness and completeness of QFS. However, in practice, scalability requires to put limits on the number of query results and suggestions, and SPARQL endpoints also enforce such limits. Therefore, partial results and suggestions are unavoidable with large datasets. A previous work [START_REF] Guyonvarch | Scalable Query-based Faceted Search on top of SPARQL Endpoints for Guided and Expressive Semantic Search[END_REF] has shown that partial results have generally a small impact on frequent concepts, but a high impact on infrequent concepts and entities/values. That impact is significant at the beginning of a search when result sets are large, and tends to disappear when the query becomes specific.

Our objective is to reconcile scalability in the computation of suggestions, and completeness in guidance. The solution that we have found and implemented in Sparklis is based on intelligent auto-completion. Auto-completion is a well-known user interface mechanism that provides guidance and feedback, and has already been adapted to semantic contexts [START_REF] Hyvönen | Semantic autocompletion[END_REF][START_REF] Haller | QuiKey -an efficient semantic command line[END_REF]. Sparklis auto-completion is directly available at the top of each suggestion list, and dynamically filters suggestion lists at each keystroke for immediate feedback. It is intelligent in two ways. First, the filter condition depends on the user-selected filter operator. If that operator is matches all, then the suggestion must contain all keywords, in any order and insensitive to the case. If that operator is between, then the suggestion must be between the two given values, using numerical comparisons. Second, Sparklis auto-completion uses a cascade of three stages to ensure completeness. At stage 1, the partial list of suggestions is filtered on the client side, which can be done efficiently. At stage 2, if the filtered list gets empty, the list of suggestions is re-computed by sending to the SPARQL endpoint a new query that includes the user filter (depending on the filter operator). This means that the same partial query results are used, but a constraint is put on the expected classes and properties. At stage 3, when the filtered list is still empty, new queries are again sent to the SPARQL endpoint, using the full SPARQL query instead of the partial results, in addition to the user filter. This ensures that all query results are used in the computation of suggestions. Given the increasing cost of stages 2 and 3, they are triggered only when the user has entered a full keyword (trailing space), so as not to do it at every keystroke.

We present three evaluations to assess the portability, the expressivity and scalability, and the usability of QFS, based on its implementation as a Web application: Sparklis. The experimental data of those evaluations are available at http://www.irisa.fr/LIS/ferre/pub/iswc2014/.

Sparklis: QFS as a Web Application

Sparklis is entirely based on Web standards. It uses SPARQL endpoints for RDF storage and querying, HTTP requests to query them, JavaScript (JS) for the application code, and HTML5/CSS3 for the user interface. Queries to SPARQL endpoints are sent directly from the client browser, using AJAX requests. It makes Sparklis independent from a server, hence trivial to deploy, and efficient because all application code runs on the client. For code safety and development speed, the JS code is compiled from a high-level language (OCaml using js of ocaml7 ). The source code counts about 4000 lines of code, and the minimized JS code weights about 260k.

Portability to SPARQL Endpoints

We first assess the portability of Sparklis on permanent SPARQL endpoints found on the Web. The web site SPARQL endpoints status8 maintains a list of SPARQL endpoints, along with dynamic information about their availability, performance, and expressivity. We took a sample of 57 active endpoints, and tried Sparklis on each of them. We report on three aspects: success/failure of the connection, performance, and usability. Out of the 57 endpoints, 3 connections failed because of the endpoint server (e.g., HTTP 500 error, POST requests not accepted), 24 were successful, and surprisingly 30 connections failed because of the same-origin policy. That policy, enforced by Web browsers, forbids scripts to send HTTP requests to other origins (e.g., http://dbpedia.org/) than the script origin (http://www.irisa.fr/ for Sparklis). It is crucial for the security of many Web applications, but it is not relevant for SPARQL endpoints, which act as public web services. Fortunately, there is a simple solution, but it is the responsability of each endpoint administrator to apply it. It suffices to add the line Access-Control-Allow-Origin: * in the HTTP response headers.

Out of the 24 successful connections, 22 were responsive enough to allow for fluid exploration of the dataset. The initial step typically took between 1 and 3 seconds, and 7 seconds in the worst case. In terms of contents, 10 endpoints contained only facts about concepts, ontologies, and datasets; 10 endpoints contained concrete facts about various topics (e.g., Austrian skiers, Chile administration, Nobel prizes); and 4 endpoints appeared empty. The 4 latter endpoints appeared empty because of a bug in some rkbexplorer-based endpoints related to UNION: an union of empty results is not empty, and contains unbounded bindings. On a few endpoints, our random explorations have led to interesting results. For example, on http://data.ox.ac.uk/sparql/, we got the list of Oxford colleges along with their logo, and a picture. On http://data.nobelprize.org/sparql, we found the laureates of the Peace Nobel prize in decreasing year, people with several prizes (e.g., Marie Curie had 2), and the shocking gender imbalance (44 women vs 803 men). For 6 endpoints, URI local names of entities are opaque codes (e.g., numbers) that hinder the readability of suggestions and results. It does not prevent to access and use the real names of entities, but it requires additional navigation steps.

Expressivity and Scalability over DBpedia QALD Questions

We here assess the practical expressivity and scalability of Sparklis using questions from the QALD-3 challenge9 . QALD (Question Answering over Linked Data) primarily targets Natural Language Interfaces (NLI) where natural questions are answered in one interaction step. We instead use QALD questions as the expression of information needs that are satisfied through multi-step interaction (QFS). For each of the 100 training questions over DBpedia, we evaluated the minimum interaction time to answer the question, when possible, starting from the empty query (Give me something). Because we here evaluate the scalability and efficiency of Sparklis, and not the usability (see next section), we strived to minimize the exploration and thinking user time by using the gold standard SPARQL queries provided by QALD as a guide in the selection of suggestions. Therefore, the measured times represent the optimal interaction time for a trained and focused user. In real use, interaction times will increase according to unfamiliarity with Sparklis and the dataset, and to lack of focus in search (exploratory search).

Expressivity. With Sparklis, we could answer 90/100 questions. Out of the 10 failed questions, 9 correspond to missing information in DBpedia (aka. OUT OF SCOPE questions). The other failed question is because a YAGO class could not be found due to timeouts from the endpoint. Unlike DBpedia classes that are quickly found among suggestions, YAGO classes are numerous and difficult to get. A few gold standard queries could not be constructed, but the answer was still easy to get. For example, the question asking whether Natalie Portman was born in the US cannot be reached because she was born in Israel, but as Sparklis immediately shows the actual birth place, the answer was obviously No.

Scalability. Figure 3 shows the distribution of the wall-clock interaction time for the 90 successful questions 10 . Half of the questions can be answered in less than 27s (median time). The most complex QALD questions can be answered in less than 2min. We found those results quite satisfactory given the billions of triples of DBpedia. The simplest questions generally involve an entity and a property (e.g., Give me the homepage of Forbes), or a class, a property, and a value (e.g., Give me all books written by Danielle Steel). The more complex questions combine unions, string matching, numerical comparisons, counts, or ordering. For example, question (Which telecommunications organizations are located in Belgium?) has 3 unions and 2 string matching because there are different ways to express telecommunications and located in Belgium due to data heterogeneity, and it requires 14 navigation steps.

For comparison, we shortly describe the performance of the best NLI participant to the QALD-3 challenge: CASIA [START_REF] He | CASIA@QALD-3: A question answering system over linked data[END_REF]. CASIA produced correct answers for 29 questions, and partially correct answers for 8 questions. The average computation time over the 100 questions is 83s. With regard to faceted search, we found no system capable of exploring DBpedia and responsive enough.

First Usability Experiments

We have so far conducted three usability experiments of QFS. In the first experiment [START_REF] Ferré | Reconciling faceted search and query languages for the Semantic Web[END_REF], we asked 20 graduate students to answer 18 questions about genealogical data using Sewelis, a desktop version of QFS. The dataset was small, but the questions already involved complex graph patterns, disjunction, and negation, and the subjects had no previous knowledge about SW technologies. The results showed that, after a short training, all subjects were able to answer simple questions, and most of them were able to answer complex questions. The average time per question ranged from half a minutes to six minutes. The main observed difficulty was in understanding the notion of focus. The SUS questionnaire showed that subjects did not find the system unnecessarily complex, and that they would learn to use it very quickly.

In the second experiment [START_REF] Guyonvarch | Scalable Query-based Faceted Search on top of SPARQL Endpoints for Guided and Expressive Semantic Search[END_REF], the developer of the former version of Sparklis, Scalewelis, took part in the QALD3 challenge on DBpedia questions. He was of course expert in the use of Scalewelis, but he was unfamiliar with the DBpedia dataset. He tried to answer the 100 test questions, and submitted them. Because Scalewelis was less expressive than Sparklis, he could answer "only" 70 questions. Out of them, 32 were correct and 1 was partially correct. Most errors were because there are often several representations of the same meaning in DBpedia, which produce different answers: e.g., "being an actor" is represented either by the pattern ?x a dbo:Actor or by [] dbo:starring ?x. Also, most properties come in two versions: one in DBpedia ontology, and one among DBpedia properties. Scalewelis was ranked third out of six participants, with recall (33%) and precision (33%) very similar to best NLI approaches. This experiment demonstrated that QFS is a promising approach for question answering, albeit it is based on interaction rather than on NL understanding.

In the third experiment, which is still ongoing as an online survey we ask anonymous Web users to try and answer 12 questions over DBpedia, after viewing a tutorial video 11 . Only 6 people have filled the survey yet, but they have different profiles, and results are already instructive. On average, they have built correct queries for 7.8 questions. For non-IT people (2/6), the average goes only slightly down to 7. For people having some knowledge of SPARQL (2/6), it goes up to 10 questions. An expert user, who can write SPARQL queries, had 9 correct answers, made 2 errors related to disjunction, and skipped a single query (which was skipped by all users). (S)he found Sparklis much easier to use than SPARQL, and declared: "I like use this system and I find it is easy to use unlike other semantic web search engines". An advanced user, who can do some programming but never heard about SPARQL, had 8 correct answers, made 2 errors by using string matching instead of numerical comparison, and skipped 2 queries. (S)he found it difficult to find the right concepts (classes and properties), but declared that "there are no inconsistencies in the suggestions", and that "the system is really usable". A regular user, who know neither SPARQL nor programming, had still 6 correct answers (involving comparisons, negation, and ordering), 3 incorrect answers, and 4 skipped queries. (S)he expressed difficulties with focus position and interaction logic, but declared that "for some questions, it would take me hours to do the same in Excel, while here a few clicks are enough!". No user managed to answer the question Which U.S. states do not possess gold minerals? because it requires to find one among the many YAGO classes (see Section 6.3). Most expert and advanced users (4/5) managed to answer the complex question Give me all bridges crossing the Saint Lawrence river, ordered by decreasing length, and with an optional depiction. whose answer is an ordered three-dimensional table (bridge, length, and depiction). The SUS questionnaire gives results consistent with our first experiment, and answers mostly differ on the expected amount of learning depending on user background.

Conclusion

We have improved Query-based Faceted Search (QFS) with NL verbalization for readability, and with SPARQL endpoint-based computation of results and suggestions for scalability and portability. This makes it an appealing approach for semantic search as it reconciles the expressivity of formal languages, the guidance of query builders and faceted search, the readability of natural language interfaces, the scalability of the most powerful RDF stores and SPARQL engines, and the portability to many SPARQL endpoints thanks to a strong conformance to W3C standards. Our evaluations have shown that our QFS implementation, Sparklis, can be used effectively on various endpoints, without configuration, can answer most QALD questions and more, and was evaluated positively in first usability experiments.

Our priorities for future work concern expressivity, readability, and visualization. We aim to cover all SPARQL features while avoiding to make user interaction more complex. Note that union, negation, aggregation, and ordering all simply add modifiers as suggestions, and we expect the same for other SPARQL features. User interaction in QFS is FS + query + focus so that usability is mostly a matter of readability and visualization. We plan to improve readability by using ontology lexicons [START_REF] Mccrae | Linking lexical resources and ontologies on the semantic web with lemon[END_REF] in NL verbalization, when available, and visualization by producing graphical views (e.g., diagrams, charts, maps) from tables of results [START_REF] Melo | Cubix: A visual analytics tool for conceptual and semantic data[END_REF][START_REF] Hoefler | Linked data query wizard: A tabular interface for the semantic web[END_REF].

Fig. 1 .

 1 Fig.1. Sparklis screenshot at step 11 of scenario in Table1.

  Q1: SELECT ?c WHERE { {f1 a ?c} UNION {f2 a ?c} UNION ... } Q2: SELECT ?p WHERE { {f1 ?p []} UNION {f2 ?p []} UNION ... } Q3: SELECT ?p WHERE { {[] ?p f1} UNION {[] ?p f2} UNION ... }

Fig. 3 .

 3 Fig. 3. Histogram of wall-clock interaction times for 90/100 QALD-3 questions.

Table 1 .

 1 Navigation scenario in Sparklis over DBpedia.

	step query
	1 Give me something
	2 Give me a Writer
	3 Give me a Writer that has a nationality
	4 Give me a Writer that has nationality Russians
	5 Give me a Writer that has nationality Russians and that has a birthDate
	6 Give me a Writer that has nationality Russians and whose birthDate
	is after 1800
	7 Give me a Writer that has nationality Russians and whose birthDate is after
	1800 and that is the author of something
	8 Give me a Writer that has nationality Russians and whose birthDate is after
	1800 and that is the author of a Book
	9 Give me a Writer that has nationality Russians and whose birthDate is after
	1800 and that is the author of a number of Book
	10 Give me a Writer that has nationality Russians and whose birthDate is after
	1800 and that is the author of the highest-to-lowest number of Book
	11 Give me a Writer that has nationality Russians or something and whose
	birthDate is after 1800 and that is the author of the highest-to-lowest number
	of Book
	12 Give me a Writer that has nationality Russians or Russian Empire and
	whose birthDate is after 1800 and that is the author of the highest-to-lowest
	number of Book

Table 2 .

 2 Mapping from Sparklis query elements to SPARQL features.

	query element	SPARQL feature
	concept name, relation	triple pattern
	entity name	URI in triple pattern
	value	literal in triple pattern
	a, the	variable in triple pattern, and after SELECT
	any	variable not put after SELECT
	and, that	join
	or	UNION
	optionally	OPTIONAL
	not	FILTER NOT EXISTS
	matches	REGEX()
	higher than, after, between, ... comparators (<, ≤, ...)
	language	lang()
	datatype	datatype()
	highest-to-lowest	ORDER BY DESC()
	lowest-to-highest	ORDER BY ASC()
	number of	COUNT()
	list of	GROUP CONCAT()
	total, average, ...	SUM(), AVG(), ...
	PREFIX n1: <http://dbpedia.org/ontology/>
	PREFIX n2: <http://dbpedia.org/resource/>
	SELECT DISTINCT ?Writer_1 ?birthDate_3 (COUNT(DISTINCT ?Book_4) AS ?number_of_Book_5)
	WHERE { ?Writer_1 a n1:Writer .
	{ ?Writer_1 n1:nationality n2:Russians . }
	UNION { ?Writer_1 n1:nationality n2:Russian_Empire . }
	?Writer_1 n1:birthDate ?birthDate_3 .
	FILTER ( str(?birthDate_3) >= "1800" )
	?Book_4 a n1:Book .
	?Book_4 n1:author ?Writer_1 . }
	GROUP BY ?Writer_1 ?birthDate_3
	ORDER BY DESC(?number_of_Book_5)

Sparklis http://www.irisa.fr/LIS/ferre/sparklis/osparklis.html

Fluidops Information Workbench http://iwb.fluidops.com/

mSpace http://mspace.fm/

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

OpenLink FS http://dbpedia.org/fct/facet.vsp

Vinge Query&Explore http://www.vingefree.com/querybyexplore/

http://ocsigen.org/js of ocaml/

http://sparqles.okfn.org/

http://www.sc.cit-ec.uni-bielefeld.de/qald/

Note that the responsiveness of DBpedia endpoint may vary over time.

Survey form and video are online at http://tinyurl.com/kxozx9r

Acknowledgement We are grateful to Joris Guyonvarc'h for his master work that contributed to this work by designing, implementing, and experimenting a first version of QFS over SPARQL endpoints. Interesting technical details not present in this paper for space reasons can be found in a technical report [7]. We also thank the reviewers for their thorough analysis, and encouraging comments.


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

Sparklis: a SPARQL Endpoint Explorer for Expressive Question Answering

.

Motivation

A wealth of semantic data is accessible through SPARQL endpoints. DBpedia alone contains several billions of triples covering all sorts of topics (e.g., people, places, buildings, species, films, books). Although different endpoints may use different vocabularies and ontologies, they all share a common interface to access and retrieve semantic data: the SPARQL query language. In addition to being a widely-adopted W3C standard, the advantages of SPARQL are its expressivity, especially since version 1.1, and its scalability for large RDF stores thanks to highly optimized SPARQL engines (e.g., Virtuoso, Jena TDB). Its main drawback is that writing SPARQL queries is a tedious and error-prone task, and is largely unaccessible to most potential users of semantic data.

Our motivation in developing Sparklis1 , shared by many other developers of Semantic Web tools and applications, is to unleash access to semantic data by making it easier to define and send SPARQL queries to endpoints. The novelty of Sparklis is to combine in an integrated fashion different search paradigms: Faceted Search (FS), Query Builders (QB), and Natural Language Interfaces (NLI). That integration is the key to reconcile properties for which there is generally a trade-off in existing systems: user guidance, expressivity, readability of queries, scalability, and portability to different endpoints [START_REF] Ferré | Expressive and scalable query-based faceted search over SPARQL endpoints[END_REF].

Principles

Sparklis re-uses and generalizes the interaction model of Faceted Search (FS) [START_REF]Dynamic taxonomies and faceted search. The information retrieval series[END_REF], where users are guided step-by-step in the selection of items. At each step, the system gives a set of suggestions to refine the current selection, and users only have to pick a suggestion according to their preferences. The suggestions are specific to the selection, and therefore support exploratory search [START_REF] Marchionini | Exploratory search: from finding to understanding[END_REF] by providing overview and feedback during the search process.

To overcome expressivity limitations of FS and existing extensions for the Semantic Web (e.g., 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], SemFacet [START_REF] Arenas | SemFacet: Semantic faceted search over YAGO[END_REF]), we have generalized it to Query-based Faceted Search (QFS), where the selection of items is replaced by a structured query. The latter is built step-by-step through the successive choices of the user. This makes Sparklis a kind of Query Builder (QB), like SemanticCrystal [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF]. QBs have the advantage to allow for a high expressivity while assisting users about syntax, e.g. avoiding syntax errors, listing eligible constructs. However, the FS-based guidance of Sparklis is more fine-grained than in QBs. Sparklis avoids vocabulary errors by retrieving the URIs and literals right from the SPARQL endpoint. It needs not be configured for a particular dataset, and dynamically discovers the data schema. In fact, Sparklis only allows the building of queries that do return results, preventing users to fall on empty results. That is because system suggestions are computed for the individual results, not for their common class. In fact, Sparklis is as much about building answers as about building questions.

To overcome the lack of readability of SPARQL queries for most users, Sparklis queries and suggestions are verbalized in natural language so that SPARQL queries never need to be shown to users. This makes Sparklis a kind of Natural Language Interface (NLI), like PowerAqua [START_REF] Lopez | PowerAqua: Supporting users in querying and exploring the semantic web[END_REF]. The important difference is that questions are built through successive user choices in Sparklis instead of being freely input in NLIs. Sparklis interaction makes question formulation more constrained, slower, and less spontaneous, but it provides guidance and safeness with intermediate answers and suggestions at each step. Moreover, it avoids the hard problem of NL understanding: i.e., ambiguities, out-of-scope questions. A few NLI systems, like Ginseng [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF], are based on a controlled NL and autocompletion to suggest the next words in a question. However, their suggestions are not fine-grained like with FS, and less flexible because they only apply to the end of the question. In Sparklis, questions form complete sentences at any step of the search; and suggestions are not words but meaningful phrases (e.g., that has a director), and can be inserted at any position in the current question.

User Interface and Interaction

Figure 1 is a Sparklis screenshot taken during an exploration of book writers in DBpedia. From top to bottom, the user interface contains (1) navigation buttons and the endpoint URL, (2) the current question and the current focus as a subphrase (highlighted in green), (3) three lists of suggestions for insertion at the focus, and (4) the table of answers. The shown question and answer have been built in 10 steps (8 insertions and 2 focus moves): a Writer/that has a birthDate/after 1800/focus on a Writer/that is the author of something/a Book/a number of/the highest-to-lowest/focus on a Writer/that has a nationality. Note that different insertion orderings are possible for a same question. Navigation buttons allow to move backward/forward in the construction history. A permalink to the current navigation state (endpoint+question) can be generated at any time. To switch to another SPARQL endpoint, it is enough to input its URL in the entry field. The query focus is moved simply by clicking on different parts of the question, or on different table column headers. Every suggestion in the three lists, as well as every table cell, can be inserted or applied to the current focus by clicking it. The first suggestion list contains entities (individuals and literals). The second list contains concepts (classes and properties). The third list contains logical connectives, sorting modifiers, and aggregation operators. Each suggestion list is equipped with an immediate-feedback filtering mechanism to quickly locate suggestions in long lists. With the first list, filters can be inserted into the query with different filter operators listed in a drop-down menu (e.g., matches, higher or equal than, before). Questions and suggestions use indentation to disambiguate different possible groupings and improve readability, and syntax coloring to distinguish between the different kinds of words.

Performances and Limitations

Portability. Sparklis conforms to the SPARQL standard, and requires no preprocessing or configuration to explore an endpoint. It entirely relies on the end-point to discover data and its schema. The main limitation is that URIs are displayed through their local names, which is not always readable.

Expressivity. Sparklis covers many features of SPARQL: basic graph patterns (including cycles), basic filters, UNION, OPTIONAL, NOT EXISTS, SELECT, ORDER BY, multiple aggregations with GROUP BY. Almost all queries of the QALD2 challenge can be answered. Uncovered features are expressions, named graphs, nested queries, queries returning RDF graphs, and updates.

Scalability. Sparklis is responsive on the largest well-known endpoint: DBpedia. Among the 100 QALD-3 questions, half can be answered in less than 30 seconds (wall-clock time including user interaction and system computations).

Demonstration

The demonstration has shown to participants how QALD questions over DBpedia can be answered in a step-by-step process. Those questions cover various retrieval tasks: basic facts (Give me the homepage of Forbes), entity lists (Which rivers flow into a German lake?), counts (How many languages are spoken in Colombia?), optimums (Which of Tim Burton's films had the highest budget?). More complex analytical question answering has also been demonstrated (Give me the total runtime, from highest to lowest, of films per director and per country). Participants were also given the opportunity to explore any SPARQL endpoint of their choice.

Fig. 1 .

 1 Fig. 1. Sparklis screenshot: a list of writers with their birth date (after 1800), nationality, and (decreasing) number of written books. Current focus is on writer's nationality.

Online at http://www.irisa.fr/LIS/ferre/sparklis/osparklis.html

http://greententacle.techfak.uni-bielefeld.de/~cunger/qald/