Motivation An increasing number of applications rely on RDF [2] and SPARQL 1.1 [3] for storing, publishing, and querying semistructured data. The functionality of many such applications is enhanced with OWL 2 ontologies [1], which are used to provide a conceptual layer on top of data and enrich query answers with implicit information. Although the growing popularity of RDF, OWL 2, and SPARQL 1.1 has been accompanied by the development of better and better query answering engines, writing SPARQL 1.1 queries is not well-suited for the majority of users. Thus, an important challenge is the development of simple yet powerful query interfaces that capture welldefined fragments of SPARQL 1.1. Faceted search is a prominent approach for accessing document collections that allows users to narrow down search results by incrementally applying filters, called facets, on the annotations associated to documents [18]. Faceted search has become a mainstream commercial technology, and it is ubiquitous in e-commerce websites. For example, hotel booking websites such as Booking.com allow users to refine search results by selecting suitable values in facets such as 'Price', 'Star Rating', or 'Facilities'. Faceted search has been proposed as a suitable paradigm for querying document collections annotated with RDF, and several RDF-based faceted search systems have been developed [4, 6, 8, 13, 16, 9-11, 14, 12]. Existing approaches are, however, rather systems-oriented, and there is a lack of rigorous theoretical underpinnings. Furthermore, existing works have focused mostly on RDF, thus essentially disregarding the role of OWL 2 ontologies. In particular, the following key questions have not been satisfactorily addressed in the literature: (Q1) What fragments of SPARQL 1.1 can be naturally captured using faceted search as a query paradigm? (Q2) What is the complexity of answering such queries? (Q3) What does it mean to generate and interactively update an interface according to a given ontology? Our goal is to provide such solid foundations. We have formalised faceted interfaces tailored towards graph-based data models, and identified a fragment of first-order logic capturing the underlying queries. We have studied the complexity of answering such queries for RDF and ontologies expressed in the OWL 2 profiles. Moreover, we have devised practical and generic algorithms for recomputing faceted interfaces in response to user actions. Finally, we have implemented and tested our faceted search algorithms ? Work supported by the Royal Society, the EPSRC projects Score!, Exoda, and MaSI3, and the FP7 project OPTIQUE.
in a prototype system [
Technical Approach To illustrate our definitions and make our discussion concrete, we
consider an excerpt of Yago [
We model facets as pairs consisting of a predicate (or facet name) and a set of values (typically documents represented by URIs or literals). Examples of facet names are the binary relations ‘gradFrom’ and ‘dateOfBirth’, and examples of values for these facets are specific documents such as ‘ds’ (Stanford) and literals such as ‘1858-10-27’. Selection of multiple values within a facet can be interpreted either conjunctively or disjunctively, and hence we distinguish between conjunctive and disjunctive facets. Furthermore, we distinguish a special facet type, whose values are categories (i.e., unary predicates) rather than specific documents or literals. Finally, we also allow for a special value any which denotes the set of all values compatible with the facet predicate. We assume that C, UP and BP are pairwise disjoint infinite sets of constants, unary predicates and binary predicates.
Definition 1. Let type and any be symbols not occurring in C [ UP [ BP. A facet is a pair (X; ), with 2 f^; _g, a non-empty set, and either (i) X = type and
UP, or (ii) X 2 BP, any 2 and either C [ fanyg or UP [ fanyg. A facet of the form (X; ^ ) is conjunctive, and a facet of the form (X; _ ) is disjunctive. In a facet F = (X; ), X is the facet name, denoted by F j1, and contains the facet values and it is denoted by F j2.
The following facets could be of use when searching over these documents. F1 = (type; _fUSpres; president; person; country; universityg); F2 = (hasChild; _fany; dke ; dch g); F4 = (citizenOf; ^fdusa; dukg);
F3 = (gradFrom; _fany; dh; ds; dgg);
F5 = (citizenOf; _fdusa; dukg): F1 can be exploited to restrict types of entities, F2 to narrow down search results to entities with children, where ‘any’ can be used to say that we are not looking for a specific child, F3 to select an alma mater, and F4 and F5 to select a citizenship. Faceted Interfaces. A faceted interface represents an arrangement of facets that can be displayed for users, and captures the choices of facet values made by them. Thus, it encodes both a query, whose answers constitute the current search results, and the possible choices of facet values available to users for further refinement. In contrast to traditional faceted search, our notion of interface allows the user to ‘navigate’ across interconnected sets of documents and establish independent filters to each of them. Definition 2. A basic faceted interface (BFI) is a pair (F; ), with F a facet and F j2 the set of selected values. The set of faceted interfaces (or interfaces, for short) is given by the following grammar, where I0 and I1 = (F; ) are BFIs and F j1 2 BP:
I ::= path j (path ^ path) j (path _ path); path ::= I0 j (I1=I): A BFI encodes user choices for a specific facet, e.g., the BFI (F1; fUSpresg) selects the documents categorised as US presidents. BFIs are put together in paths: sequences of nested facets that capture navigation between sets of documents. With nesting ‘=’ we capture queries such as ‘people with a child who graduated from Stanford’ by using the interface (F2; fanyg)=(F3; fdsg) which first selects people having (any) children and then those children with a Stanford degree. Finally, two types of branching can be applied: (path1 ^ path2) indicates that search results satisfy the conditions in both path1 and path2, while (path1 _ path2) indicates that they satisfy those in path1 or path2. The following interface Iex encodes the query ‘return US presidents who graduated from Harvard or Georgetown and who have a child who graduated from Stanford’.
(F1; fUSpresg) ^ (F3; fdh ; dgg) ^ (F2; fanyg)=(F3; fdsg) :
Faceted Queries. Queries encoded in faceted interfaces can be captured by formulae
in the positive existential fragment of first-order logic with one free variable, where
in every disjunction '1 _ '2, the subformulae '1 and '2 share at most one variable.
Moreover, these queries involve predicates of arity at most two and are tree shaped. The
output variable of a faceted query is the root variable in the query graph. We also
considered extensions of faceted interfaces that allow us to choose different output variables (a
functionality typically referred to as refocusing [