Repositorio Institucional de Documentos

2013 134 Carlos Bobed Lisbona Semantic Keyword-based Search on Heterogeneous Information Systems Departamento Director/es Informática e Ingeniería de Sistemas Mena Nieto, Eduardo Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Carlos Bobed Lisbona SEMANTIC KEYWORD-BASED SEARCH ON HETEROGENEOUS INFORMATION SYSTEMS Director/es Informática e Ingeniería de Sistemas Mena Nieto, Eduardo Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Semantic Keyword-based Search on Heterogeneous Information Systems Carlos Bobed Lisbona Tesis Doctoral Departamento de Inform´atica e Ingenier´ıa de Sistemas Universidad de Zaragoza Octubre 2013 “There’s a sign on the wall but she wants to be sure ’Cause you know sometimes words have two meanings” Stairway to Heaven - Led Zeppelin “Sanity can be the toll - leading to the core of your soul.” Avantasia - Avantasia “I’ve got to keep going, be strong Must be so determined and push myself on” The Loneliness of the Long Distance Runner - Iron Maiden Acknowledgements First of all, I want to thank my advisor, Eduardo Mena, who, apart from being there anywhere and anytime to help me with my thesis1, has had the patience needed to get the best out of my efforts. This work would not have been possible without the priceless help of my colleagues of the SID group which are also my co-authors: Sergio Ilarri, Raquel Trillo, Jordi Bernad, and the latest acquisitions, Fernando Bobillo, Roberto Yus, and Guillermo Esteban. Thank you all for the efforts and all those long nights trying to reach all those unforgiving deadlines. Thanks also to all my laboratory mates (I will not try to name all of them, as it has been quite a long time and I do not want to miss anyone) for all the great moments shared, specially at coffee breaks. To finish with the academic staff, I also want to thank Francisco Ser´on, whose phone calls, along with Eduardo’s ones, have become one of my strongest fears (you both will fight later for whom scares me the most, calm down ,). After this, where to start? I want to thank my friends, Luis Carlos and Estefan´ıa, Ra´ul and Sheila, Santi and Javi (Mr. Paquito), for all those moments of laughs that have reminded me that there is life beyond the thesis. Thanks also to my handball mates, after quite a few ball hits I have finally got my PhD (it was not a joke, I was really taking a PhD ,). Last but not least, I want to thank my parents (Javier and Conchita) for all their support; my brothers (Javier and Jorge), always there for suggesting me new games which waste my time with ,; and, specially, my girlfriend, Elena, because of all the patience she has had with me, encouraging me to go on, and being there in highest and lowest moments, I love you. 1Specially anytime behind the email: at first, I thought he had some kind of bot answering all the emails I sent him. List of Tables 2.1 Syntax and interpretation for ALC DLs............. 15 2.2 RDF-Selements. ......................... 17 2.3 OWL2concepts.......................... 18 2.4 OWL2axioms........................... 19 5.1 Properties of the operators of BACK language. . . . . . . . . 72 5.2 Operators of the inner specification language. . . . . . . . . . 73 5.3 Global conditions for BACK language. . . . . . . . . . . . . . 74 5.4 Queries and patterns generated for “person bus”. . . . . . . . 87 6.1 Rewriting rules applied by the DBpedia Adapter. . . . . . . . 97 6.2 Results for “fictional dogs” accessing DBpedia. . . . . . . . . 99 6.3 Annotated grammar for LOQOMOTION. . . . . . . . . . . . 113 7.1 Success rate of QueryGen against the QALD excerpt. . . . . 122 7.2 Details of the evaluation against QALD. . . . . . . . . . . . . 122 VII VIII Chapter 1 Introduction The work presented in this thesis belongs to the broad context of Information Systems, understanding them as systems that help users to fulfill their information requirements. Delving into this context, our work is closely related to Semantic Search,Semantic Web,Knowledge Representation, and even Ontology Engineering. In particular, this thesis focuses on exploiting the different mechanisms that Semantic Web technologies have provide us with to bridge the gap that there exists between the spread keyword-based interfaces and the formalisms that are used to access information. Taking into account the semantics of the different elements that take part in the search process, our approach is able to access and integrate data from different heterogeneous underlying information systems using plain keywords as initial input. We focus on this kind of input as the popularity of keywordbased interfaces has grown along with the spread of Web Search engines. Its simplicity allows users to express their information needs easily; however, they introduce the high cost of ambiguity. Our work aims at reconciliating this ease of use of keyword-based interfaces with the expressive power of structured query languages. This issue has been studied by other research groups, achieving solutions that are attached to the underlying information system by both the query language and the data model used. In this thesis, we generalize the problem and provide a flexible solution that enables us to get rid of these limitations. Our work builds on previous research works of our group on keyword senses disambiguation, a crucial step in our approach as we will see. In this chapter, we first present the motivation for this thesis. Then, we detail the different semantic levels that our proposal takes into account to achieve its goal. Finally, we present the structure of this thesis. 1 2Chapter 1. Introduction 1.1 Motivation In the last few years, with the upcoming of the World Wide Web, a huge amount of information has made been available for users in several forms. Moreover, this information is more easily accessible than ever thanks to the increasing levels of connectivity that the users are provided with: On the one hand, users can access to the Internet via broadband Internet connections at their homes; on the other hand, technological advances of mobile devices and wireless networks (e.g., 3G, Wi-Fi) allows them to be connected all the time via their smartphones. All this information has a sheer potential value. . . if filtered and accessed properly according to the user’s needs. The excess of information can be as harmful as the lack of it, as users might be overwhelmed and not be able to process it. Besides, this information might be behind different sources or sites, thus forcing users to actively search for the appropriate place to search for particular data. The information systems that effectively provide users with this information are of such a different nature that users would have to be aware of each of their particularities to be able to exploit them. For example, compare the direct use of a Web Search engine with a Linked Data [BHBL09] endpoint: In the case of the former, users can pose their queries directly expressed in terms of keywords; while, in the case of the latter, users need to know both the underlying data schema and the query language itself to be able even to build a query. This heterogeneity becomes greater when we consider any possible information service as source of potential relevant information for the user (e.g., location-dependent services, databases exported via Web Services, etc.). As the amount of information and the heterogeneity of the systems holding it is so high, the integration of such information systems should be performed externally, providing methods to access them transparently as it occurs, for example, in federated database systems [HM85,SL90]. The trend to integrate all the possible services can be easily seen in the Google search main page: The user’s search can be posed almost transparently to different search services (e.g., search for Web pages, images, maps, etc). The actual search service used gives a global meaning to the kind of searches that are performed, but at least they are all integrated in one site. Regarding the integration of information systems, the use of ontologies and mappings to the underlying systems’s data schemas has been of great help [MI01]. They can be used to provide a global view of the integrated systems, and to store information needed to actually access them. 1.2. Overview of the Approach 3 Apart from integrating these systems, we have to provide users with an easy method to express their information needs. This method needs to be independent of any particular system (independent of its data model, its query language, and its query processing model) in order to be adaptable enough to integrate them under its unifying view. Regarding this issue, keyword-based interfaces have spread thanks to its adoption by the most popular Web Search engines. They provide a simple way to express queries, but it comes at the cost of lack of expressivity, and ambiguity. So far, several approaches have addressed the problem of performing keyword-search on different information systems. However, they are usually bounded to its data model and query languages, which makes them nonflexible solutions. Moreover, they do not provide a single entry point to the different information services that might be relevant for the user’s needs. Therefore, in this thesis, we propose an approach to integrate all these heterogeneous information systems under the unifying view of a semantic keyword-based search that: 1. Provides users with an easy way to express their queries that they are used to, i.e., keyword-based search; 2. Avoids the ambiguity of plain keyword-based search by discovering the exact meaning that users have in mind when posing their queries; 3. Adapts itself to the answering capabilities of each of the underlying systems. Our system encapsulates the different systems attached to it, adapting their query languages, data models, and query execution models, and providing users with a simple way of expressing their searches. 1.2 Overview of the Approach As we have introduced in the previous section, our approach aims at providing the benefits of keyword search, while avoiding ambiguity and integrating different heterogeneous information systems. To do so, we advocate for a semantic keyword-based search, where the semantics of the input are well established firstly, to then access only the semantically relevant data. For this task, several approaches (e.g., [RS06,TGEM07]) advocate starting with the discovery of the meaning of each keyword among the different possible combinations. These approaches consult a pool of ontologies (which offer a formal, explicit specification of a shared conceptualiza- 4Chapter 1. Introduction tion [Gru93,Gru95]) and use disambiguation techniques to discover the intended meaning of each user keyword. So, plain keywords can be mapped to ontological terms (concepts, roles, or instances). In this thesis, we delve into that line and present a system that performs semantic keyword-based search on different data repositories. Our system: 1. Discovers the meaning of the input keywords by consulting a generic pool of ontologies and disambiguates them taking into account their context (the rest of the keywords in the input set); i.e., each keyword in the input has influence on the rest of the keyword’s meanings. 2. Then, as a given set of user keywords (even when their semantics have been properly established) could represent several queries, the system finds all the possible queries using the input keywords in order to precisely express the exact meaning intended by the user. This is done considering different formal query languages (the use of formal languages avoids ambiguities and expresses the user information in a precise way), and avoiding inconsistent and semantically equivalent queries with the help of a Description Logics (DL) reasoner [BCM+03]. During this process, our system considers the addition of virtual terms. These virtual terms represent missing keywords that users had in their mind but did not input1. This way, our system can explore further meanings when the user has given an incomplete input. 3. Finally, once the user has validated the generated query that best fits her/his intended meaning, our system routes the query to the appropriate structured data repositories that will retrieve data according to the semantics of such a query. The architecture of our system is flexible enough to deal with different ontologies, formal query languages, and query processing capabilities of underlying data repositories. In the following section, we discuss the different semantic aspects that are taken into account in our approach. 1.3 Semantic Levels of Our Approach The main feature of our approach is that it is completely semantics guided. In Figure 1.1, we can see how the three main steps align with the different semantic levels that are taken into account during the whole process. 1For example, a user looking for movies whose genre is “horror” could enter “horror movie”, omitting the keyword “genre”. 1.3. Semantic Levels of Our Approach 5 Relevant Data Plain Keywords USER Query Languages Discovery of Meanings Interpretation and Translation into Formal Languages Access Data Semantics of the Input Semantics of the Query Execution Semantics of the Figure 1.1: Main steps of our approach and the semantic levels involved. Semantics of the Input The semantics of the input set of keywords are treated at two different levels: •First, our system discovers and disambiguates the meaning of each of the keywords that conforms the input. For instance, the keyword “book” could mean “a kind of publication” or “to reserve a hotel room”. To determine the meaning of each input keyword, it takes into account its context (the rest of the keywords in the input set); i.e., each input keyword has influence on the rest of the keyword’s meanings. •Second, once each keyword has an exact meaning, our system considers the semantics of the whole set of keywords to build possible interpretations according to the different query languages of the integrated systems. The use of ontologies and formal languages to express the information needs enables our system to get rid of the ambiguity of the input composed by plain keywords. Semantics of the Query Languages In our approach, the syntax of the different query languages that are used is left aside to focus on the semantics of their different operators. On the one hand, via the use of extended grammars, we make it possible to specify 6Chapter 1. Introduction query languages taking into account their operators: The arguments that they take as input, their returned values, their properties, etc. On the other hand, we extend further this semantic specification by using Description Logics [BCM+03] to express different semantic conditions that both the operators and their operands must satisfy to build not only syntactically valid queries, but also semantically. Semantics of the Query Execution Last but not least, our system considers the different semantics that are behind the different execution models offered by the systems. Different user information needs might require different types of queries and execution schemas, each with its own semantics. For example, information needs about static knowledge require a snapshot query execution (e.g., a user looking for the list of taxi companies in a city); while information needs about volatile knowledge require a continuous query processing as the answer might be continually changing (e.g., a user looking for a cab nearby in a rainy day requires considering continually their position -user and cabs positionsas the answer gets obsolete quickly). These three semantic levels (input, query languages, and query execution ones) are integrated in our approach to develop a highly flexible system that enables users to perform keyword-based searches over heterogeneous information systems. Our approach is capable of adapting itself to the query capabilities of the underlying systems, providing users with a single entry point to all of them, while retrieving the appropriate answer for their information needs. 1.4 Structure of the Thesis This thesis is composed of eight chapters, including this one. In Chapter 2, we present the technological context of this thesis, focusing on what ontologies are and what benefits their use provides us with; and on the differences among the informal and formal query languages relevant to this thesis. We finish Chapter 2 with an analysis of the main works related to this thesis. In Chapter 3, we present a lightweight approach to perform semanticsoriented keyword search on Linked Data repositories. Then, we introduce the problems of translating queries expressed using the keyword query model into other more expressive query models, and present QueryGen, our approach to achieve a generalized keyword interpretation where the semantics of all the elements involved in the process are taken into account. 1.4. Structure of the Thesis 7 In Chapter 4, we explain how QueryGen obtains the meaning of each of the input keywords taking into account their query context. In this step, the information retrieved during the disambiguation process is integrated into a multi-ontology sourced ontology, which contains the user’s intended meanings. We explain also how we have used external sources and modularization techniques to enrich the available information. In Chapter 5, we focus on the query generation process that QueryGen performs to translate the keyword queries into more expressive query languages. We detail how we can specify different query languages using specially annotated grammars, and how QueryGen uses these language specifications to generate the queries guided by the semantics of the input keywords and the operators. We also present how QueryGen uses the integrated knowledge to filter out inconsistent queries, and to react to insufficient inputs by performing a semantic enrichment of the input. Last but not least, we present the semantic techniques that QueryGen uses to reduce the search space that a generalized keyword interpretation implies. In Chapter 6, we explain the solution adopted to make QueryGen capable of handling different underlying data models. It is an architecture based on wrappers, which can be attached on the fly. These wrappers provide QueryGen with information about their underlying information systems (the query languages used, data formats, and execution models). We present and detail two successful use cases already implemented (DBpedia [BLK+09] and LOQOMOTION [IMI06]). As a result of working in the field of location-dependent queries, we also propose two different semantic models for representing location granularities that extend the semantics of the queries that can be handled with LOQOMOTION. In Chapter 7, we test QueryGen from a qualitative and a quantitative point of view. In particular, using a third-party query set, we evaluate the semantic capabilities of our approach regarding the discovery of the user’s intended meaning. Then, we focus on the performance of the system, paying special attention to execution times and the impact of the query reduction techniques used by QueryGen. Finally, in Chapter 8, we present the conclusions as well as our main contributions; we finish with the future research topics. 8Chapter 1. Introduction 2.1. Knowledge Representation 15 C, D →A∈NC|A is a concept name > | >I= ∆I ⊥ | ⊥I=∅ ¬C|(¬C)I= ∆I\CI CuD|(CuD)I=CI∩DI CtD|(CtD)I=CI∪DI ∀R.C |(∀R.C)I={a∈∆I| ∀b, (a, b)∈RI→b∈CI} ∃R.C |(∃R.C)I={a∈∆I| ∃b∈CI,(a, b)∈RI} Table 2.1: Syntax and interpretation for ALC DLs. •Concept satisfiability: Checks if a concept can have instances i.e., if it does not necessarily denotes the empty set. •Entailment: Checks if a given fact is a logical consequence which can be derived from the axioms in the ontology. •Subsumption: Checks if a concept/property Ccan be considered more general than (or subsumes) a concept D. •Classification: Computes a concept/property hierarchy based on the relations of concept/property subsumption. In this thesis we have used two different reasoners, Pellet2[SPG+07] and HermiT3[MSH07, MSH09], both of which support OWL 2, the representation language proposed by W3C for ontology specification, which is overviewed in the following subsection. 2.1.3 Representation Languages As we have seen in Section 2.1.1, and, in particular, in Figure 2.2, once we have selected what to model (the ontology) and the underlying formalism (DLs) to express it, we have to implement it in a representation or implementation language. In this section, we present the most important languages adopted and used in the context of the Semantic Web: RDF (along with RDF-S) and OWL. 2http://clarkparsia.com/pellet, last accessed October 3, 2013. 3www.hermit-reasoner.com, last accessed October 3, 2013. 16 Chapter 2. Technological Context 2.1.3.1 RDF and RDF-S RDF (Resource Description Framework) [MM04] is a language for representing information about resources on the World Wide Web. At first, it was intended for representing metadata (title, date of creation, authorship, etc.) about Web documents; however, by generalizing the notion of resource, it can be used to represent information about anything that can be identified in the Web by a URI (Uniform Resource Identifier). In RDF, the most basic representation data unit is the triplet, < a R b >, which represents an statement where ais the subject, bthe object, and Ris the property that links them. This simple data model provides flexibility to represent the information about the resources as a graph of nodes and arcs which represent the resources, their properties, and their values. In Figure 2.3, we can see an example of an RDF graph comprising information about myself. We have a URI representing myself as subject of a set of different statements. Summing up, the nodes of the RDF graph can be: Other resources identified by their own URIs (e.g., my PhD. advisor); blank nodes, which makes it possible to have composite values (e.g., an address) without having to give them an identifier; or literals, typed or not (e.g., my age and my hobby). Figure 2.3: RDF example: information about myself. The structure of the information enables it to be automatically shared and processed by different programs; however, they have to speak the same language, i.e., use the same vocabulary. RDF-S (RDF Schema) [BG04] was developed to ease the definition and sharing of these vocabularies that enable interoperability. It allows to define classes, along with their properties (see Table 2.2). Despite of the fact that its expressiveness is quite low, it provides a formal implementation language for simple ontologies. 2.1. Knowledge Representation 17 Classes Properties Utility Properties rdfs:Resource rdfs:domain rdfs:seeAlso rdfs:Class rdfs:range rdfs:isDefinedBy rdfs:Literal rdf:type rdfs:Datatype rdfs:subClassOf rdf:XMLLiteral rdfs:subPropertyOf rdf:Property rdfs:label rdfs:comment Table 2.2: RDF-S elements. In the following subsection, we present OWL, which builds on RDF-S, extending further its expressiveness. 2.1.4 OWL: Web Ontology Language OWL (Web Ontology Language) [HKP+12] is the current W3C recommendation for ontology specification. OWL is based on the DL SROIQ(D). In this subsection we will only describe the syntax of the language, but more details about the underlying logic, including the semantics, can be found in [HKS06]. OWL provides several syntaxes, among which, we will use Manchester syntax [HP12], specifically designed to be easily understood by humans. OWL ontologies have five elements: Individuals, concepts (or classes), datatypes (or concrete domains), object properties, and data properties. Essentially, concepts are sets of individuals, datatypes are sets of values defined over a concrete domain (such as integers or dates), object properties are binary relations between individuals, and datatype properties relate individuals and datatypes. Table 2.3 shows the supported concept constructors in OWL 2, its latest version. Using these constructors, we can build complex concepts from simpler ones inductively. On the other hand, Table 2.4 summarizes the main axioms in OWL 2. The top part of the table (with 7 axioms) contains the axioms concerning the ABox, and the lower part contains the axioms concerning the TBox. Some of the axioms are just syntactic sugar and can be represented using equivalent class axioms (such as disjoint classes, disjoint union of classes, and domain and range axioms). In these tables, Cis a concept, Ris an object property, nis a natural number, iis an individual, Tis a datatype property, vis a datatype value, and Dis a datatype. In order to guarantee the decidability of the logic, there are some restrictions in the role hierarchies axioms and some roles are required to be simple ones. The interested reader may find the formal specification at [HKS06]. 18 Chapter 2. Technological Context AAtomic/primitive concept C1or C2Disjunction C1and C2Conjunction not CNegation T hing Universal concept Nothing Empty concept {i1,...,in}Nominals/Enumeration Ronly CUniversal restriction Rsome CExistential restriction Rvalue iValue restriction Rself Self concept Rexactly n[C] [Qualified] Exact cardinality restriction Rmax n[C] [Qualified] Maximal cardinality restriction Rmin n[C] [Qualified] Minimal cardinality restriction Tonly DUniversal restriction Tsome DExistential restriction Tvalue vValue restriction Texactly n[D] [Qualified] Exact cardinality restriction Tmax n[D] [Qualified] Maximal cardinality restriction Tmin n[D] [Qualified] Minimal cardinality restriction Table 2.3: OWL 2 concepts. Figures 2.4 and 2.5 show an example of an OWL ontology (proyectos.owl4) visualized with our ontology viewer OntView5. In this example, we can visualize the following definitions (among others): jefes EquivalentTo personas and (ocupacion value "jefe") superPro EquivalentTo proyectos and (miembros min 3 personas) The aim of our viewer is to capture visually the exact meaning of the loaded ontology. To do so, it uses a DL reasoner to classify the ontology and to obtain all the relevant information about it. Depending on the ontology size and amount of visual information that the user wants to be displayed, we can visualize the ontology in two different modes: •Not expanded (Figure 2.4), where the definitions and expressions are presented in a compact way. 4http://sid.cps.unizar.es/ontology/proyectos.owl, last accessed October 3, 2013. 5http://sid.cps.unizar.es/OntView/, last accessed October 3, 2013. 2.1. Knowledge Representation 19 iTypes CConcept assertion i1Facts R i2Property assertion i1Facts not R i2Negated property assertion iFacts T v Property assertion iFacts not T v Negated property assertion SameIndividual i1i2Equality assertion DifferentIndividuals i1i2Inequality assertion C1SubClassOf C2Subclass axiom C1EquivalentTo C2Equivalent classes C1DisjointWith C2Disjoint classes C1DisjointUnionOf C2. . . CnDisjoint union of classes [R1|T1] SubPropertyOf [R2|T2] Subproperty axiom R0SubPropertyChain R1. . . RnSubproperty chain axiom [R1|T1] EquivalentTo [R2|T2] Equivalent properties [R1|T1] DisjointWith [R2|T2] Disjoint object |data properties [R|T] Domain C Domain of an object |data property RRange CRange of an object property TRange DRange of a data property R1InverseOf R2Inverse properties [R|T] Functional Functional object |data property RInverseFunctional Inverse functional property RTransitive Transitive property RReflexive Reflexive property RIrreflexive Irreflexive property RSymmetric Symmetric property RAsymmetric Asymmetric property Table 2.4: OWL 2 axioms. Figure 2.4: OWL example: simple ontology about project management. 20 Chapter 2. Technological Context Figure 2.5: OWL example: expanded visualization. •Expanded (Figure 2.5), where each of the expressions in the ontology are expanded to show their semantics visually. In the following section, we turn our focus to the notion of query language and present the most relevant ones in the context of this thesis. 2.2 Query Languages In Computer Science, query languages are computer languages that are used to query databases and information systems. Note the difference that exists between information need and query [MRS08]: An information need is the topic about which the user desires to know more, and is differentiated from a query, which is what the user conveys to the computer in an attempt to communicate the information need. Depending on their formality degree, we can classify query languages as informal or formal ones. Informal query languages are more related to information retrieval tasks, where the semantics of the query are not formally defined. Users express with these query languages their information needs, so these languages imply an intermediate step to establish their semantics (query construction) and adapt the query to the underlying data model. On the other hand, formal query languages have their semantics strictly defined and users express with them queries with a univocal interpretation. In this section, we present the query languages that appear in this thesis: Informal query languages (natural language and keyword queries), and for- 2.2. Query Languages 21 mal ones (SQL-like languages, SPARQL, and logic based ones –in particular, conjunctive and DL queries). 2.2.1 Informal Query Languages Under this denomination, we can find our natural languages and the keyword query language, which is a strong simplification of the former. Natural Language Natural Language (NL) enables users to express their information needs in their own language. Its ease of use makes it always a possible choice for casual users [KB10], but processing it correctly is still an open problem. Among others, NL as query language faces the following problems: •It is inherently ambiguous: The meaning of the query depends heavily on its context (the discourse), and, even when the context has been perfectly established, different aspects such as polysemy or the flexibility of the language might make impossible to interpret correctly the query. Among other linguistic problems, we could find the following challenges (examples taken from [ART95]) when dealing with NL queries: –Modifier attachment: When modifiers appear in the sentence, it is not always clear which clause they are modifying. For example, in List all employees in the company with a driving license,“with a driving license” could modify the company or the employees as well. While one could infer that a company could not have a driving license, this is not straightforward at all. This another example (taken from [PG88]) is even more ambiguous, List all employees in the division making shoes. –Nominal compound problems: Dealing with English language, nouns are often modified by other nouns and the resulting meaning is quite difficult to be foreseen. For example (based on [PG88], taken from [ART95]), city department could mean a department located in a city or a department responsible for the city, research department probably means a department carrying out research, and research system is probably a system used in research, and not a system carrying out research. –Conjunction and disjunction: Users tend to use and to denote disjunction instead of conjunction. For example (fitted from [TB83]), 22 Chapter 2. Technological Context for List all applicants who live in Zaragoza and Madrid, all the applicants living either in Zaragoza or Madrid should be returned instead of those living in both cities at the same time. –Other linguistic features, such as anaphora (the use of pronouns and noun phrases to denote entities already mentioned before), ellipsis (the use of incomplete sentences, very common in oral communication), quantifier scoping (similar to the modifier attachment problem, but this time concerning logical quantifiers), etc. •It is language-dependent: The techniques applied to process NL depend directly on the language being processed as they differ at syntactic, grammatical and semantic levels. Assuming that you could process and correctly interpret one language solving the linguistic problems associated to it, moving to another language would require to remake the interpretation process almost from the beginning as the interpretation rules would have change completely. Natural Language was used firstly as interface to databases [ART95]. This kind of interfaces has evolved into what is currently named Query Answering systems, which are not only focused on accessing databases, but on accessing different information systems. In particular, in the last few years, the Semantic Web community has turned its attention to this kind of techniques to be used to query semantic resources [LUSM11]. While they are still far from being perfect, there has been a lot of research in the Natural Language Processing (NLP) field that would help us and vice versa. Keyword Query Language Keyword queries are a simplification of the queries that can be expressed using Natural Language. They consist of a set of plain keywords that represents the user’s information need. For example, a user could express horror movie to ask for the latest movies that correspond to the horror genre. The success and adoption of keyword-based search interfaces have come along with the success of the main Web search engines, such as Google, which adopted it as their main query language. The different search techniques used in the field of Information Retrieval, such as the bag of words representation of Web documents, make keyword queries especially easy to answer statistically (using different ranking methods) while keeping the process scalable enough to deal with huge amounts of information. Moreover, 2.2. Query Languages 23 users have found in keyword queries a quick and easy way to express their information needs. However, the ease of use of keyword search comes from the simplicity of its query model, whose expressivity is low compared with other more complex query models [KB10]. Moreover, keyword queries are in fact projections of the user’s actual information need. This leads to a much more ambiguous context, where polysemy and lack of information are always present. Revisiting some of the examples for the NL queries, a user could write the following queries6: •List all employees in the company with a driving license could be expressed as employees driving license, which although gets rid of the modifier problem, introduces new ambiguity problems: Must the returned employees have a driving license? Must they not? Is there any other kind of license and we should retrieve the employees that are currently driving? •List applicants who live in Zaragoza and Madrid could be expressed as applicants Zaragoza Madrid: Which applicants should we retrieve? Those who are living/working in Zaragoza, in Madrid? However, despite of its inherent ambiguity, keyword-based search interfaces have been adopted by different information systems other than Web search engines as the benefits that they provide in terms of user-friendship and language independence are worthy enough to do so. In this thesis, we aim at overcoming their drawbacks with the help of semantic techniques. 2.2.2 Formal Query Languages We now turn our attention on formal languages, which make it possible to express the information needed unambiguously thanks to the adoption of different formalisms. 2.2.2.1 SQL-like Languages The notion of SQL-like language is quite broad. SQL-like languages are languages whose syntax resembles the syntax of SQL (Structured Query Language) [ISO11b], which is the most extended language for querying and managing data stored in relational databases [Cod70]. 6We assume three keywords for the examples as the average number of keywords used in keyword-based search engines “is somewhere between 2 and 3” [MRS08]. 24 Chapter 2. Technological Context SQL has its formal foundations on relational algebra [Cod71,EN11], and consists of a data definition language (to create and manage the database schema) and a data manipulation language (to insert, update, and query the data in the database). Focusing on SQL as a query language, and independently of the underlying schema, a SQL query has the following general structure: SELECT ListOfProjections FROM ListOfTables WHERE ListOfConditions where: •ListOfProjections is the list of attributes that have to be retrieved as an answer for the query. •ListOfTables is the list of the tables that are involved in the query. •ListOfConditions is the list of the conditions that the attributes have to meet to form part of the answer. This conditions can include different kind of relational operators between tables such as the different kinds of JOIN operators that exist. For example, assuming that the appropriate tables exist, the examples from the previous section would look like the following in SQL: •The list of the employees of a given company that have a driving license: SELECT EmployeesTb.employeeID FROM EmployeesTb, CompaniesTb WHERE CompaniesTb.companyID = exampleCompanyID AND EmployeesTb.employeeID = CompaniesTb.employeeID AND EmployeesTb.hasDrivingLicense = TRUE •The list of applicants for a position that live in Zaragoza or Madrid: SELECT ApplicantsTb.applicantID FROM ApplicantsTb WHERE ApplicantsTb.applyFor = examplePositionID AND (ApplicantsTb.livesIn = Zaragoza OR ApplicantsTb.livesIn = Madrid) 2.3. Systems Related to QueryGen 31 two ones. Once they had the nodes in the graph that corresponded to the denotations, they applied different heuristics to retrieve related resources and enrich the search results. With one anchor term, they focused on retrieving the resources that were connected to it by different relationships, applying different selection criteria such as the amount of resources retrieved so far via that relationship, or the provenance of the data. With two anchor terms, before applying this heuristic, the possible subgraph connecting them was to be selected. SemSearch One of the first systems whose goal is building formal queries from keywords in the area of the Semantic Web is SemSearch [LUM06]. They offer a Googlelike user interface where the user has to mark the main subject of the search and mark the rest of the keywords as mandatory or optional ones. Then, the input is matched to semantic entities by means of text indexes. The subject keyword must be mapped to a concept entity (the focus of the user query, i.e., the type of the expected search results); otherwise, the system applies several fixed heuristic rules to interpret it correctly depending on the number of input keywords (for example, with two input keywords, if the subject keyword matches an instance and the keyword matches a property, the search results are the values of the matched property for the matched instance). The result of the matching process is passed to the Semantic Query Layer, where the system applies several predefined query templates to interpret the keywords and build formal queries (in particular, they use SeRQL query language, although SPARQL could also be used). This templatebased approach fixes the possible interpretations and, as not all the possible queries are considered in those templates, the system could fail generating the user’s intended query. Regarding Semantic Search on TAP, SemSearch goes one step further in the keyword interpretation process supporting complex queries (more than two keywords, although it is done via predefined templates attached to a single query model); however, they do not consider the vocabulary mismatch problem (the indexes SemSearch uses for the semantic entity mapping are preprocessed on the data repository to be accessed). 32 Chapter 2. Technological Context SPARK SPARK [ZWX+07] relies on graph construction on a semantic model equivalent to RDF-S to achieve a proper keyword interpretation. To do so, they focus on obtaining a query graph out from the keyword query. They equate semantic query to a query graph with constrained object nodes and property arcs, which is directly mapped to conjunctive queries. The interpretation performed in SPARK is constrained to just one given domain, which is provided in the form of an ontology. The resources of this ontology are indexed to perform the term mapping, which associates each of the input keywords to one or more resources (due to the possible ambiguity). They use morphological techniques (i.e., substring, stemming, etc.), and expands the mapping space semantically using general dictionaries such as WordNet [Mil95]. Once the terms are mapped, the query graph construction step explores the RDF data to construct complete query graphs applying Minimum Spanning Tree algorithm. If there are missing edges needed to connect the mapped terms, SPARK adds them by consulting the underlying semantic model. The result is a set of SPARQL queries that are ranked according two different perspectives: According to the keyword input, and according to the semantic model. Regarding the previous approaches, SPARK enables a higher level of expressivity (although it is constrained to simple conjunctive queries) as they can calculate all the interpretations that can be derived from the underlying RDF data. However, this comes at the cost of not scaling well with large data repositories. Moreover, they just work on one domain, and it has to be previously indexed (SemSearch also indexed the semantic entities, but it was multi-domain oriented). Q2Semantic and SemSearchPro Adopting a similar approach as SPARK, the works of Tran et al. [WZL+08, TWRC09,THL11] also advocate for graph construction on the RDF data to perform the keyword interpretation. Concerned by the scalability problems of general graph-approaches such as SPARK, they perform a clustering operation on the RDF data to “obtain a graph structure that corresponds to a only a summary of the original ontology”, a lightweight ontology. Once they have it, they focus on building the top-k queries that are the possible interpretations for the input keywords. Thus, they adopt a data-driven approach to obtain the semantics that are behind the keywords/ontologies used. The techniques were introduced in Q2Semantic [WZL+08], were de- 2.3. Systems Related to QueryGen 33 tailed and improved in [TWRC09], and finally a compilation of the whole pipeline was presented under the name of SemSearchPro in [THL11]. These approaches, instead of working directly with the underlying RDF graph as SPARK did, perform an offline preprocessing step to build the lightweight ontology out from the RDF data. The authors advocate for this dynamic construction instead of working with predefined ontologies due to the fact that large scale scenarios at Web scale have to deal with dynamic evolving generic data, and in that scenarios they argue that “a schema cannot be defined completely a priori but must also evolve with changes in usage requirements, and with changes in the underlying data”. This semantic model is built exploiting the structure similarity of the different RDF resources, which allows to group different elements. In SemSearchPro, it is obtained by applying the notion of bisimulation, originating from the theoretical analysis of state-based dynamic systems. As the authors state, “intuitively speaking, two vertices are bisimilar when they share the same structure found in the data graph”. The expressive power of this semantic model is lower than RDF-S. The interpretation process in these systems is comprised by two main steps: A keyword-to-resources mapping step, and a exploration and ranking step. The first step in Q2Semantic is similar to SPARK’s term mapping. It searches for the keywords in the RDF literals, which are enriched with Wikipedia’s terms to try to fill the gap between the RDF repository’s and user’s vocabularies. In [TWRC09] they improve this matching process by adding a keyword index that also takes into account the types of the resources that the keywords are matched against. The second step is performed on the built summarized graph/semantic model, which reduces the search space with respect to generic-graph approaches. They employ a top-k exploration algorithm [TWRC09] that starts from the matched elements and explores iteratively the graph looking for all the distinct paths from these elements. While traversing the graph, they score the paths according to different factors (such as the popularity of the graph elements, among others) to obtain a ranking of the created queries and focus the search. Eventually, paths are formed between the initial resources and are added as candidate queries. In both systems, the queries to be built are constrained to a restricted type of conjunctive queries, which are directly translated into query graphs in SPARQL. They achieve a more efficient interpretation method than SPARK. Moreover, they get rid of the need of an ontology describing the domain, as they build their own. However, this is done offline and it depends completely on the underlying data. Finally, they still rely mainly on syntactic techniques 34 Chapter 2. Technological Context for the initial matching (in spite of being partially enhanced), and are attached to just one data model (RDF with a subset of conjunctive queries as query language). CoSi CoSi [FA11, FGA11] adopts a summary graph solution as SemSearchPro does, using also the top-k approach to obtain the most probable interpretations for the input keywords. The main difference between both systems relies on the information that their summarization graphs hold. CoSi introduces the use of user’s query history to achieve a better semantic interpretation. Instead of building their own summarization graph from scratch directly from the underlying data, CoSi relies on a provided schema graph (with an expressivity less than RDF-S) to build a contextaware summary graph, which includes a query history dependent weighting function. This function takes into account the locality of the resources (region factor), and the query history (historical impact factor) to weight the nodes and edges during the top-k exploration. The interpretation process is similar as the performed by SemSearchPro, with an extra step to update the weights in the summarization graph. First, the keywords are matched to the underlying resources using an inverted index. Then, CoSi uses a graph exploration algorithm to generate the top-k interpretations. After this, the updating of the weights is carried out. The top-k exploration algorithm is also adapted to deal with dynamic weight values and to detect early termination conditions. QUICK Finally, QUICK [ZZM+09] adopts a schema-driven approach to perform the keyword interpretation, instead of a data-driven one as the previous systems did. Moreover, they involve the user in the keyword interpretation by allowing him to build the desired query incrementally. QUICK works on a predefined domain, which is provided by an RDF-S ontology. It uses this ontology to build the complete set of all possible semantic queries for the given set of input keywords. To do so, first, QUICK obtains the possible query patterns for that given schema without considering the input keywords. These query templates are compositions of schema elements, and their expressivity is limited to acyclic conjunctions of triple patterns. Then, the actual semantic queries are build by binding keywords to the appropriate query templates. The keyword matching is done using a 2.3. Systems Related to QueryGen 35 full-text index, extended with synonyms. Then, to help users to select the intended query, they propose an algorithm to iteratively build it by selecting different subqueries of the intended one. Working at schema-level makes QUICK not to be so dependent on the underlying data. However, QUICK still needs to build an enriched text index to perform the initial keyword matching, which does not take into account all the possible semantic aspects of the keywords. Moreover, their expressivity is constrained to just one data model (RDF with acyclic conjunctions of triple patterns as query formalism). Finally, they are constrained to just one domain at a time (their query search space grows directly with the size of the schema/s considered). 2.3.2 Keyword Search on Relational Databases There are also some works in the area of databases to provide a keywordbased interface for databases, i.e., translating a set of keywords into SQL queries, such as BANKS [BHN+02,ABC+02], DBXplorer [ACD02], and DISCOVER [HP02]. However, they focus on how to perform keyword searches efficiently on the relational data, overcoming the problem of having the relevant data distributed among several tables (mainly due to normalization). Moreover, as emphasized in [BDG+11], most of these works rely only on extensional knowledge obtained by applying IR-retrieval techniques, and so, they do not consider either the intensional knowledge (the structural knowledge), or the semantics of the input keywords. The graph-based approach adopted by BANKS [BHN+02,ABC+02] has strongly influenced another works such as SPARK or Q2Semantic. In this system, the database is modeled as a directed graph with each tuple being a node in that graph. The foreign-key-primary-key links are the edges between the different nodes. With this built graph in memory, BANKS uses disk resident indexes to search for the nodes that exactly match the search keywords. Once it has obtained them, it builds join-trees that connect all the matched nodes. These trees are rooted in a information node, which can be restricted to be from a selected set of nodes of the graph. Also considering the database as a graph of interconnected tuples, DBXplorer [ACD02] and DISCOVER [HP02] work with specially designed data structures stored in the same database. The former one builds a symbol table which indexes the database associating keywords with their locations within it. This makes it possible to determine where the query keywords appear efficiently (i.e., the tables, columns or rows, depending on the granularity level chosen). Then, it works out all the subsets of tables that, when 36 Chapter 2. Technological Context joined, might contain rows with all the keywords. Finally, for each of these combinations, they build an SQL statement to retrieve the rows with all the keywords. DISCOVER also relies on a keyword index (Master Index) at row granularity to perform the initial keyword search on the database. Then, it works at row level to create candidate networks, sets of tuples that cover the input keywords. As the authors state, this allows DISCOVER to consider more solutions than DBXplorer does (e.g., solutions that include two tuples from the same relation). More recently, Keymantic [BDG+11] proposes an approach that is the most related work to ours in this field. In this case, authors focus on mapping the keywords to entities of the relational schema of a database and interpret them as an SQL query to enable keyword based search over databases without having to process the extensional data, which is an important improvement when we only have access to the database schema. Moreover, when matching each input keyword to the database elements, they have also into account the influence that rest of the input keywords has in the query meaning. Then, once they have obtained the set of most feasible mappings, they apply a greedy algorithm to derive the whole set of possible Select-Project-Join (SPJ) queries to be posed to the database. This approach also helps the user to understand the database schema in a exploratory way. However, as we will see, our approach is more flexible as it is capable of: 1) obtaining the semantics of the keywords without specifying a target schema, 2) interpreting the queries into different query models, taking into account the semantics of all the elements (keywords, query language, operators, etc.), and filtering the inconsistent ones; and, finally, 3) accessing different underlying data models considering the previously well-established semantics. 2.3.3 Question Answering Systems Finally, we overview the broad field of Question Answering systems [ART95, LUSM11]. Although this kind of systems is traditionally more related to the processing of Natural Language (according to [HG01], their goal is “to allow a user to ask a question in everyday language and receive an answer quickly and succinctly, with sufficient context to validate the answer”), in essence, QueryGen shares their objectives. According to the classification given in [LUSM11], our system would fall into the category of ontology-based semantic QA systems, taking keywords as input. They are traditionally attached to a specific knowledge domain and/or underlying data source/model , which guides the translation process. 2.3. Systems Related to QueryGen 37 Using several different techniques, we tackle some of the traditional problems that these systems face [LUSM11]: 1. The vocabulary mismatch between the user’s vocabulary and the underlying repository. As we will see, QueryGen maps the vocabulary of the user to the vocabulary of the data sources (provided that the data sources are semantically described, and the ontology is made available). 2. As we have seen in Section 2.2.1, Natural Language is inherently ambiguous and, of course, language-dependent. When using keywords, in spite of introducing ambiguity due to the lack of expressivity of the keyword model, we provide users with a multilanguage way of expressing their information needs. Moreover, our approach disambiguates the different possible interpretations due to polysemy (and, in our case, also due to the lack of expressivity of the keyword model). 3. Many QA approaches present domain-specific limitations, a limitation that can be overcome by using techniques to consult and analyze a dynamic pool of ontological sources. 4. QA approaches usually need a well formed input to achieve good results (complete sentences). In this thesis, we deal with this lack of information by retrieving semantic information relevant to the query. 5. To the best of our knowledge, no QA approach exploits the semantic knowledge not only to interpret the query, but to filter inconsistent queries. However, we have to bear in mind that the premises which QA systems and QueryGen build on are quite different, and we are aware (and we are working on it) that we can introduce several techniques from these systems to improve the whole semantic keyword-search process that we are presenting in this work. 38 Chapter 2. Technological Context Chapter 3 Semantic Keyword-based Search In this chapter, we firstly present a lightweight approach to perform keyword search guided by the semantics of a domain on Linked Data repositories. Then, we move onto our main approach, where we introduce the problem of interpreting the keywords of the users, and give an overview of our approach to it. This problem (keyword interpretation) is an ill-posed one due to different difficulties, such as the lack of expressivity of the keyword query model, the ambiguity introduced by the polysemy of the keywords, and the possible omission of implicit keywords. Thus, we advocate for a semantic keyword-based search, which takes into account the semantics of all the elements that participate in the process to reduce the impact of the main problems of keyword query model. 3.1 Lightweight Semantic Keyword Search on Linked Data In this section, we give an overview of the lightweight semantic keyword search we have developed to enhance the underlying knowledge of Embodied Conversational Agents (ECAs) [CSPC00]. ECAs are graphical interfaces capable of using verbal and non-verbal modes of communication to interact with users in computer-based environments. The appearance of these agents varies depending on the application scenario: They might be as simple as just an animated talking face, displaying simple facial expressions; or they can be as complex as to have a sophisticated 3D graphical representation, with complex body movements, and emotional and facial expressions. 39 40 Chapter 3. Semantic Keyword-based Search In [BEM12,BEM13], we studied the possibility of using the sheer amount of information available behind Linked Data endpoints to enhance the information handled by this kind of agents, and, in particular, we focused on the case of DBpedia. The conversational nature of the interaction with the ECAs introduced an important constraint: We could not abuse of disambiguation dialogues to avoid annoying and distracting the user with them. As the speech recognition by itself might need disambiguation questions, we only could use as input the plain keywords that an ECA recognized and forwarded us without further information. Thus, having no control on any user’s feedback made us adopt a pragmatic approach. This approach is based on defining externally the search domain, which provides a view on the underlying data (similar to views on databases). This way, we allow the ECA to exploit the structure of the underlying data to focus its searches, only analyzing semantically related resources. The search domain is defined by using an annotated ontology provided by the administrator of the system (see Figure 3.1). This ontology provides an adaptable view on the underlying data and has to be aligned to the ontology that describes the actual data repository. In fact, although it can be built from scratch, we advocate for using ontology extraction techniques [JCS+08] to obtain a module and, then, make our system work directly with a subontology of the repository’s one. Once it has the Domain Ontology, our system offers two different but complementary kinds of search depending on the user’s input (see Figure 3.1): Admin Endpoint 1.a 1.b 4.a 3,5.b 2,6.b User Ontology 3.a 4.b 2.a 6.a 5.a Keywords SPARQL Lucene Domain DBpedia External Repository Query Engine URI DL Reasoner Figure 3.1: Our system provides two complementary search services: a) Keyword-based and b) URI refining services. 3.4. QueryGen: Architecture of the System 47 However, this is only a first step towards obtaining the semantics of the input. Several queries might be behind a given set of keywords, even when their semantics have been properly established individually. For example, given the keywords “fish” and “person” meaning “a creature that lives and can breathe in water” and “a human being”, respectively, the user might be asking for information about either biologists, fishermen, or even other possible interpretations based on those individual keyword meanings. 2. Semantic Query Generation: The output of the previous step is a set of keywords which has its meaning properly attached, which we call semantic keywords. The ontological information that has been considered for obtaining the meaning of each keyword comes along with each of them. Our system automatically integrates this information and, then, automatically builds a set of formal queries which, combining all the keywords, represents the possible semantics that could be intended by the user when s/he wrote the list of plain keywords. The semantic keywords obtained in the previous step are combined according to certain annotated abstract grammars (there is one for each query language made available to our system). These grammars lack syntax sugar and define how to combine the operators of a query language with typed gaps, i.e., they specify which kind of queries can be built using concepts, roles, and instances in the corresponding query language (e.g., And concept concept). The result is a set of abstract queries that the system materializes into a list of actual queries by substituting the typed gaps by input keywords. Finally, the set of (syntactically correct) generated queries are semantically filtered using a DL reasoner and the integrated information. When no query satisfies the user, our system performs a semantic enrichment of the input by adding virtual terms. They are generic typed gaps (to be replaced by concepts, roles, or instances) that represent the keywords that the user might have omitted, but without whom the intended query cannot be built. In a new query generation step, our system treats them as regular typed gaps but, instead of being replaced by input keywords, they are substituted by terms obtained from the ontologies which the input keywords were mapped to (during the previous discovery step). Thus, any query that the user could have in mind will be generated as a candidate interpretation as long as the available query languages are expressive enough. 48 Chapter 3. Semantic Keyword-based Search This query generation process has both a syntactic and semantic dimension: It generates only syntactically correct queries according to the grammar of each of the query languages, and it takes into account the semantics of the operators of each language and the semantics of the keywords to avoid generating either duplicated or incoherent queries. This process is performed in parallel for each available query language as their expressivity can differ from each other. 3. Access to Data Repositories: Finally, once the user has validated the generated query that best fits her/his intended meaning, the system forwards it to the appropriate underlying structured data repositories (databases, Linked Data endpoints, etc.) that will retrieve data according to the semantics of such a query. This is not a trivial task, as our system must be capable of adapting itself to their different query processing capabilities and access methods, and to their different data models and formats of the retrieved data. This is done via Adapters, an evolution of the notion of wrappers used in OBSERVER [MI01]. These Adapters encapsulate both the access methods and the actual syntaxis of the query languages and data formats, allowing QueryGen to abstract from them. Thus, we can add new information systems to feed QueryGen just by implementing and registering an appropriate Adapter in the system. In the following chapters, we include a detailed description of each of these three main steps. 3.5 Summary of the Chapter In this chapter, firstly, we have presented an approach that allowed to perform semantics-oriented keyword search on Linked Data repositories. This lightweight approach was motivated by the actual restrictions that the interaction with ECA’s and the parsed natural language interface imposed. Anyway, it gave us an important insight on how to exploit already available Linked Data repositories in a flexible way, without incurring on overloading the external endpoints. Then, we have moved onto our main proposal: We have introduced the problems of translating queries expressed within the keyword query model into other more expressive query models, the so-called keyword interpretation process. The current approaches that tackle this problem restrict 3.5. Summary of the Chapter 49 themselves to one target query and data model, due to the ill-posed nature of the problem. This is a limitation that we wanted to get rid of. Thus, we propose a generalized keyword interpretation approach where the semantics of all the elements involved in the process are taken into account. Firstly, the actual semantics behind of each of the keywords is discovered and associated separately. Then, using the semantic descriptions of the target query languages, our system generates the possible interpretations for the semantic keywords in the target query models. Finally, our system, via the use of Adapters, is able to access to the registered underlying information systems. 50 Chapter 3. Semantic Keyword-based Search Chapter 4 Discovery of the Semantics of the Keywords In this chapter, we explain how QueryGen obtains the meaning of each of the input keywords, which is the first step towards the correct input interpretation. First, we present the discovery and disambiguation method that our system uses to obtain the keyword meanings. In this step, the system builds the senses that are behind each keyword, which are used all along the process. Then, we explain the inner structure of the disambiguation module in detail to see how QueryGen keeps all the information updated in an efficient way. Finally, we introduce the method by which the system integrates all the information obtained during the process to make it available to the query generation module. 4.1 Disambiguating the Input Keywords To fully understand our approach, and before giving any further details, we have to introduce the exact meaning of sense in our system: A sense is the precise meaning of a keyword in a context, i.e., its surrounding keywords determine which meaning this keyword has. In particular, a sense is represented by a tuple formed by the term itself, an ontological context that comprises a list of possible synonyms (with their URIs) and ontological information about the term, and a description in natural language. Each ontological context is built by integrating information from different ontologies. Figure 4.1 shows some possible senses for user keyword star retrieved from online ontologies. So, the first step that our system performs is to discover and build these 51 52 Chapter 4. Discovery of the Semantics of the Keywords star as property WN3#principal star property s3 = < {TravelOntology#star}, star , "quality of a hotel"> domain(hotel) star class s2 = < { }, star , "an actor who plays a principal role"> star as class star class celestialBody supernova...binaryStar s1 = < {WN1#star}, star , "(astronomy) a celestial body of hot gases ..."> actor co−star ... filmStar WN5#star,WN7#lead Figure 4.1: Possible senses for keyword star. senses for the plain input keywords. This discovery of the semantics behind each one of the input keywords is done by taking into account their individual possible semantics as well as the possible semantics of its context (the rest of keywords), following the proposal in [TGEM07]. In particular, this process is divided into three substeps (see Figure 4.2): Web Lexical Database WordNet Other Lexical Resources Selected Semantic Keywords Ontologies not Indexed by Watson + Possible Keyword Senses Keyword Senses Keywords Discovery of Keyword Senses USER Traditional Search Engine Based on Syntactic Matching and Removal of Redundancy Keyword Sense Enrichment Disambiguation of Keyword Senses Extraction of Keyword Senses Figure 4.2: Discovery of keyword senses. •Extraction of Keyword Senses: The system extracts out the possi- 4.1. Disambiguating the Input Keywords 53 ble meanings of each keyword from a dynamic pool of ontologies (in particular, it queries Watson [dBG+07], DBpedia [BLK+09], WordNet [Mil95], and other ontology repositories to find ontological terms that syntactically match the keywords - or one of their synonyms). The system builds a sense for each matching obtained, and then, the extracted senses are semantically enriched with the ontological terms of their synonyms by also searching in the ontology pool. The result is a list of candidate keyword senses for each user keyword. In Figure 4.1, three possible senses (two as a class and one as a property) retrieved for user keyword star have been shown. •Keyword Sense Enrichment and Removal of Redundancy: As the obtained senses were built with terms coming from different ontologies, they could represent the same semantics. An incremental algorithm is used to align the different keyword senses and merge them when they are similar enough. To assess the sense similarity, our system calculates a synonymy probability that considers both linguistic and structural characteristics of the source ontologies: The linguistic similarity is calculated considering the different labels of each term as strings; and the structural similarity is calculated recursively exploiting the semantics of the semantic keywords (their ontological context, see Figure 4.1) until a certain depth. Finally, both similarity values are combined to obtain the resultant synonymy measure1. Senses are merged when the estimated synonymy probability between them exceeds a certain threshold2. Thus, the result is a set of different possible senses for each user keyword entered. •Disambiguation of Keyword Senses: A disambiguation process is carried out to select the most probable intended sense of each user keyword by considering the possible senses of the rest of keywords. The senses are compared by combining [GM09]: a) a Web-based relatedness measure, that measures the co-occurrence of terms on the Web according to traditional search engines such as Google or Yahoo!, b) the overlap between the words that appear in the context, and the words that appear in the semantic definition of the sense [BP03], and c) the frequency of usage of senses (when available, as in WordNet annotated 1The formulae for the synonymy for each type of senses (concepts, roles and instances) can be found in [TGEM07]. 2In [GdM09], the authors proposed several strategies to obtain this threshold and validated them via thorough experimentation. 54 Chapter 4. Discovery of the Semantics of the Keywords corpora). Thus, the best sense for each keyword will be selected according to its context. Note that this selection can require the user’s feedback to select the most appropriate sense for each keyword in a semi-automatic way. This discovery and disambiguation algorithm, which has been summarized here, is thoroughly described in [TGEM07], and has been applied successfully to very different tasks such as ontology matching [GM08], the integration of senses in semantic repositories [GdM09], or the construction of multi-sourced ontologies [BMT12]. So, the result of this disambiguation is a set of possible senses for each keyword, and the probabilities of each of them to be the correct one according to the rest of input keywords. In the following section, we explain how our system manages this information to expedite further searches while adapting itself to changes in the source ontologies (ontology evolution). 4.2 Architecture of the Disambiguation Module As we have seen in the previous section, the objective of the first step in QueryGen is to obtain senses out from the input keywords. As it might be a costly process, we also want QueryGen to store and manage these senses efficiently to speed up following interactions. In Figure 4.3, the inner architecture of the Disambiguation Module is shown. There are two main components: 1. Multi-Ontology Senses Library: When the user inputs its keyword query, the Multi-Ontology Senses Library is consulted with it. This library contains an index of sets of keywords with their possible meanings in the form of senses. An intelligent agent, Librarian, decides when to build a new entry for the senses or to update and integrate the possibly existing ones. If the Librarian has to disambiguate the meaning of the keywords ({ki}) or to widen the semantic information that it has for each one of them, it can use the Disambiguator and request the help of the user to choose the most appropriate meanings ({Si}). More details can be found in Section 4.3. 2. Ontology Library: Once the system has the senses attached to the input keywords, the Ontology Library stores an ontology associated to the set of senses. This ontology is integrated gathering all the semantic 4.3. Multi-Ontology Senses Library 55 Ontology Library External Onts + Other Resources Scarlet & ProSE URIs(Si) {ki} {Si} Disambiguator Input keywords {ki} {Si} <{Si}, > Librarian Library Multi−Ontology Senses Figure 4.3: Overview of the architecture of the Disambiguation Module. information regarding the senses together, which is extracted from the ontologies referenced in them. In this step, external services can be required to extract and discover more information (in particular, our system uses Scarlet [SdM08] and ProS` E [JCS+08]). In Section 4.4, the different possibilities to integrate these ontologies are detailed. In the rest of the section, we present both modules in detail. In the case of the Ontology Library, we also explain how the ontological information stored in the senses is exploited to integrate the ontologies used in QueryGen. 4.3 Multi-Ontology Senses Library The Multi-Ontology Senses Library is composed of two main blocks (as shown in Figure 4.4), and an intelligent agent Librarian which takes care of both. The first block is the Disambiguation Storage. It contains the different results of disambiguating a set of keywords along with their different probabilities of being the proper interpretation. When a set of keywords is looked up, it returns a probability-ordered list of tuples formed by the probability and a list of corresponding references to the senses. In this search, the information about the synonyms of the keywords is taken into 56 Chapter 4. Discovery of the Semantics of the Keywords account to avoid missing any possible interpretation. The library tracks the senses with unique IDs, so homonym senses cannot be mistaken (otherwise, the disambiguation process would be useless). The other block is the Sense Library. It is an storage for the senses maintained up to date by the Librarian. {Kj} L<{sj},prob> OntoCtxtSi OC book1 OC book2 OC price1 Sense Library {ki} sj Disambiguation Storage {book, price} {book1,price1}, 0’64 {book2,price1}, 0’36 book1 book2 price1 ...... Figure 4.4: Organization of the information managed by the agent Librarian. The system can consult this senses library in two ways: Using sense references or plain keywords as input. When using the former only the Sense Library is accessed, while when using the latter the Disambiguation Storage is. When working with keywords as input, if they do not fully match any keyword set, then partial coverages are considered, and, if the access fails again (or the user declines all the offered interpretations), then the Librarian starts a new disambiguation process and the newly obtained senses are inserted. To insert a new sense: 1. The Librarian obtains possible synonyms of the newly built sense (the one to be inserted). 2. Then, it looks in the ontological contexts of the already inserted senses for matches in the list of possible synonyms in order to avoid duplicates in the Sense Library. The result is a set of senses which are possibly equivalent. 3. In a parallel way, it checks whether the new sense and the candidates to be equivalent to it are so. If not all of them are, the new sense is inserted with a new unique ID. Otherwise: •The Librarian integrates the senses and inserts a new one in the Sense Library. 4.5. Summary of the Chapter 63 view on sense of keyword "offer" #PrintedMaterial SCH #CreativeWork SSUMO#Monograph SCH,PORT,SSUMO,PROT,... { }#Book SSUMO#Novel WN#best_seller WN#trade_book SSUMO#ScienceFictionBook SSUMO#Science−Fiction−Novel SSUMO#RomanticNovel SCH #AggregateOffer SCH #Intangible {WN,SCH}#Offer #counter_offer WN #contract_offer WN #AttemptWN OWLS−TC/protont.owl (PROT) OWLS−TC/simplified_SUMO.owl (SSUMO) OWLS−TC/portal.owl (PORT) WordNet (WN) schema.org (SCH) namespaces view on sense of keyword "book" SCH #CreativeWork SCH #CreativeWork SSUMO,PORT{ }#Publication SSUMO Figure 4.8: Excerpts of the senses obtained for “book” and “offer”. 4.5 Summary of the Chapter In this chapter, we have presented the details of how QueryGen uses the disambiguation techniques presented in [TGEM07] to obtain the meaning of the input keywords, which is the first step to obtain a correct keyword interpretation. The inner architecture of the module makes it possible to speed up the different disambiguation steps (as we will see in Chapter 7). Moreover, the Multi-Ontology Senses Library presented allows to keep the meanings updated, adapting them to the changes in the source ontologies and, thus, providing an automatic evolving mechanism. The information retrieved during the disambiguation process is used to integrate a multi-ontology sourced ontology, which contains the user’s intended meanings. This integrated information is further enriched using external sources and modularization techniques to fill the possible semantic gaps existing in the senses. Finally, apart from being used for the keyword interpretation process, these integrated ontologies can be written down and be used for different purposes, as we have seen in the presented example. 64 Chapter 4. Discovery of the Semantics of the Keywords Figure 4.9: Integrated ontology for “book” and “offer” (part 1). 4.5. Summary of the Chapter 65 Figure 4.10: Integrated ontology for “book” and “offer” (part 2). 66 Chapter 4. Discovery of the Semantics of the Keywords Chapter 5 Semantic Query Generation In this chapter, first, we overview the main steps that the Semantic Query Generation module in QueryGen performs to give the semantically possible interpretations of the input keywords. Secondly, we focus on how query languages are specified to be used by QueryGen. This is done via special grammars, which comprise semantic information about the operands of the query language and about how they can be combined to build formal queries out from a set of input tokens. Then, we detail how QueryGen uses these specifications to build the possible queries (interpretations) in the different available query languages. After this, we explain how QueryGen filters out the queries that are semantically inconsistent and attempts to discover possible missing information in the user’s input. Finally, as the search space of the possible queries is quite large, we explain the different semantic techniques QueryGen applies to reduce the candidate queries shown to the user. 5.1 Overview of the Semantic Query Generation Module Once the meaning of each keyword has been established, QueryGen automatically builds a set of formal queries which, combining all the keywords, represent the possible semantics that could be intended by the user. The main generation steps are shown in Figure 5.1: •Analysis Table Constructor: It constructs the analysis tables for the formal query languages that the generator uses to generate the possible queries. This is done off-line and just once for each language made available to our system. 67 68 Chapter 5. Semantic Query Generation DL Reasoner Insert Inconsistent Query Filter Admin Analysis Table Constructor abstract query language grammars User semantic keywords Generator Query 1..n queries possible user Paralellizable Step No No semantic queries Semantic Processor no queries analysis tableslang{1..n} Yes lang{1..n} Yes Removal Redundancy semantic query Yes No virtual terms valid queries? user agrees? Virtual Terms?Virtual Term Rendering Figure 5.1: Multi-language query generation process. •Query Generator: It builds the possible queries for each query language according to its syntax. During the generation process, Query- 5.2. Analysis Table Constructor 69 Gen takes into account the semantics of the different operators to avoid generating semantically equivalent queries. •Semantic Processor: Once the set of syntactically possible queries is obtained, the system is able to filter out the inconsistent ones with the help of a DL reasoner. During this step, it also performs a semantic enrichment to try to find possible implicit keywords that have been omitted due to the simplistic nature of the keyword query model. To do so, our system adds virtual terms (VTs) to the input. They are generic typed terms (they can be generic concepts, roles, or instances) that represent the keywords that the user might have omitted, but without whom the intended query cannot be built. Finally, when the system uses VTs, an extra step is carried out to substitute them with appropriate terms taken from the ontologies which the input keywords were mapped to. In the following sections, we detail these three main query generation steps plus a section dedicated to the semantic reduction techniques that are used to ease the selection of the intended query. 5.2 Analysis Table Constructor Our system has to be provided with a specification of the different formal query languages that it will use to express the semantics behind the user keywords. In our approach, the query languages associated to the query models that the underlying systems support are specified using extended contextfree grammars. These grammars have their “syntax sugar” removed, and are semantically annotated, on the one hand, to avoid generating duplicated queries; and, on the other, to build the expressions that have to be evaluated to conclude if a query is consistent or not according to the knowledge retrieved by the system. Moreover, instead of working with bare syntactical tokens, we consider three types of tokens: Concept (C),Role (R), and Instance (I), which correspond to the three main types of elements in ontologies. With these grammars, the system builds the analysis tables1that are used by the Query Generator (see Section 5.3) to build all the possible queries corresponding to the input keywords for each of the available query languages. Note that these tables are built only once for each new output query language that is made available to the system, and they are used every time a new query is posed to the system. 1It builds the Goto and Action tables, as defined in [ALSU07]. 70 Chapter 5. Semantic Query Generation 5.2.1 Specifying the Query Languages So, to make a new query language available to our system, its context-free grammar Gmust be transformed into an abstract context-free grammar G0, where the syntax sugar of such a language has been removed. In this grammar, operators become non terminals, and the right side of their productions are the operands they accept. Thus, the use of these abstract grammars makes the translation process independent of the syntax of the query languages. We define these abstract grammars as tuples G0=<Q,N,T,P>, where: •Qis the starting symbol of the grammar, and represents the root of the query. •N={Opi}∪{Qps}∪{Rtypes}, with {Opi}containing the set of operators of the query language; {Qps}being a set of auxiliary nonterminals needed to build up the different parts of the queries; and {Rtypes}being the types of the returning values of the query language operators. Each element Opiis a tuple < OpID,{propj}>, with the id of the operator and its associated properties. •Tis the set of terminals that we work with, and is conformed by C,R, and I(corresponding to concept, role, and instance tokens, respectively), plus the empty token symbol ξ. •P={< prodi, localCondi, globalCondi>}is the set of productions which define: a) if the left-side nonterminal is an operator, an ordered list of the types of operands it works with, and b) if it is a returning type ({Rtypes}), the operators that produce the returning values of that type; localCondiand globalCondiare expressions which define the semantic conditions that have to be checked to correctly apply the operator. We define them to be ambiguous on purpose, as we want to obtain all the possible derivations for a given input. To do so, we have modified the classical LR parsing algorithm [ALSU07] to deal with conflicts, as we will see later. These grammars makes the system able to, once it knows whether the input keywords are concepts, roles or instances, build semantically correct interpretations expressed as formal queries in the different query languages that are available. In Figure 5.2, the extended abstract grammar corre- 5.2. Analysis Table Constructor 71 sponding to a subset of BACK2query language [Pel91] is shown. b) |ε Projections ProjList Projections RestList RestList Concept Concept Concept Concept ε ’rf(’ Role ’)’ RestList ’[’ ProjList ’]’ ’for’ ε ’Fill’ ’(’ Role ’,’ Instance ’)’ ’All’ ’(’ Role ’,’ Concept ’)’ ’Some’ ’(’ Role ’,’ Concept ’)’ Projections ’getall’ Concept ’, rf(’ Role ’)’ RestList ’And’ ’(’ Concept ’,’ Concept ’)’ Fill Some All And Role Concept Projections Concept And | All | Fill | C | Some R Instance I Concept Concept Role Concept Role Instance Role Concept Query Projections Role Projections a) Query Figure 5.2: a) Simple BACK grammar, and b) the resulting abstract grammar (semantic annotations are not included). In particular, in the BACK example: •The initial symbol Qis Query. • {Opi}contains Projections, And, All, Fill, and Some nonterminals; {Qps}would be empty; and, {Rtypes}contains Concept, Role, and Instance nonterminals. •T, as we have defined before, contains C, R, I and ξtokens. •Pcontains each one of the productions in Figure 5.2.b. In the rest of the section, we explain the rest of the elements that complete the language definition, namely, the properties of the operators, and the semantic annotations for the productions. Properties of the Operators As we have seen in the description of the extended abstract grammars used in our system, there is a list of its properties along with each of the operators. In particular, the properties considered are associativity,involution,symmetry,restrictiveness and inclusiveness. The first three ones are well known properties, while restrictiveness and inclusiveness are defined in [BTMI10] as follows: 2Although it is obsolete (discontinued since 1998), we use BACK in the examples for didactic purposes as it almost lacks syntax sugar, and supports projections. 72 Chapter 5. Semantic Query Generation Definition 5.2.1 A binary operator op is restrictive if ∃f:K→C,K={R, C} | f(x)vy⇒op(x, y)≡op(x, f(x)). Definition 5.2.2 A binary operator op is inclusive if ∃f:K→C,K={R, C} | f(x)wy⇒op(x, y)≡op(x, f(x)). From these definitions, and according to the semantics of the operators in BACK, it directly follows that the And,Some, and All operators are restrictive, and Or is inclusive. Following with the specification of the excerpt of BACK language, a summary of the properties of the considered operators is shown in Table 5.1. Operator Properties And associativity, symmetry, restrictiveness Some restrictiveness All restrictiveness Fill none Projections associativity, symmetry Table 5.1: Properties of the operators of BACK language. In this example, we consider the Projection operator as associative as all the roles that are specified in the projections list are applied to the same concept. Thus, it does not matter the order in which we apply them. The same reasoning is applied to consider it symmetric. In the following sections, we will see how our system takes into account these properties to avoid generating duplicated queries in different steps of the interpretation process (generation and enrichment steps). Expressions for Semantic Checking Each production in the grammar can be annotated with semantic expressions that are checked with the help of a DL reasoner. These expressions are built using the operators shown in Table 5.2. There are two types of conditions for each production, local and global ones, depending on the information that they comprise: •A local condition locCondion a production prodidetails semantic constraints that the nonterminals on the right side of the production must satisfy for the production being eligible to be fired. This is used to perform an extended semantic type checking on the operands locally. 5.4. Semantic Processor 79 the retrieved knowledge, and b) when no query satisfies the user (or no query has been generated due to an incomplete input), enrich the input semantically to fill the gap between the user’s input and her/his information need. 5.4 Semantic Processor Once the system has obtained all the syntactically possible queries, the Semantic Processor comes into play. As aforementioned, it has two main tasks: To check the queries semantically according to the available knowledge; and to perform a semantic enrichment of the input to suggest further interpretations when the intended query cannot be found by the user (e.g., due to an incomplete input). In the rest of the section, we detail these processes. 5.4.1 Inconsistent Query Filtering During the previous steps, all the user keywords have been combined into queries that are syntactically correct according to the different available query languages. However, some of these queries might not be semantically correct according to the semantics of keywords. Fortunately, we have their semantic information integrated altogether in a local ontology. Our system takes advantage of capabilities of DL reasoners [BCM+03] to, once the available knowledge has been classified, detect the queries that are inconsistent according to it by testing their satisfiability. In mathematical logic, a formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true [BJ07]. Intuitively, and applied to DLs, a DL expression is satisfiable iff the concept that it defines can have instances. In our example, And(Person, Fish) would be removed in this step as it is classified as being inconsistent (Person and Fish are defined as disjoint classes in ontology Animals), and consequently will not lead to any result. This consistency evaluation is direct when dealing with DL languages as they can be directly translated into concepts and the reasoner can be asked about their consistency. However, when it comes to non-DL languages, we have to tell the system how to check them via the specification of the language. As seen in Section 5.2.1, there are two types of conditions associated to each of the productions, local and global ones: •Local conditions: They provide semantic checkings that have to be performed on the operands of the production. A query must hold all the local conditions constraints; otherwise, it must be filtered out as 80 Chapter 5. Semantic Query Generation inconsistent one because there would be any production that should not have been fired. In Figure 5.5, an example of a percentage operator is shown. SubClassOf(Male,Person) ? Concept Concept C C Instance ... PersonMale Percentage Percentage($1,$2) SubClassOf($1,$2) Figure 5.5: Example of semantic checking on the local conditions of a nonDL operator (only local conditions are shown). The definition of this operator tells the system that their operands must hold that the first one is subclass of the second one to be applicable. In this case, if Male was a subclass of Person then this part of the query would be locally consistent. All the nodes of a query have to be locally consistent for the query to be considered for global consistency. Note that, otherwise, there would be a part of the query that had been built incorrectly. •Global conditions: A query holding all the local conditions only probes that it is syntactically correct (by construction), and that all the operators have been correctly applied. However, the query might still be inconsistent due to its whole meaning. As mentioned before, the global meaning is obtained easily for DL-languages, as queries can be seen as concepts and therefore, directly translated and semantically checked. However, for non-DL languages (e.g., SQL-like languages) or for extensions of DL-languages (e.g., the projection operator of the simplified BACK language), this is not directly applicable. Global conditions provide a translation of each of the productions of the language to build a semantic expression that comprise the global meaning of the query. Our system translates the query into a checkable DL-expression by traversing recursively its associated query tree and applying the global conditions expressions to each node. This traversal is performed in a depth-first way. During it, our system applies the different condition 5.4. Semantic Processor 81 operators with the help of a DL-reasoner. Following with the example in the query generation, if we added the keyword owns to the input, mapped to the homonym term in ontology Animals, the system could form the query [owns](And(Person, Fish)), that is, the entities that are owned by a (Person and Fish). In Figure 5.6, an example of the global checking on this query involving a projection is shown. And($1,$2) C C Person Fish And( And(Dom(owns), Thing), And( Person, And(Person, Fish) ) And( And(Person, Thing), And(Person, Fish)) And(Person, Fish)) Query And($1,$2) ConceptProjections And(Dom($1), $2) Role $1 R owns Projections ε Thing And $1 Concept Concept $1 $1 Figure 5.6: Example of the global semantic checking on a DL-query involving projections (only global conditions are shown). Going from the leafs to the root node, our system is able to form the global expression applying the global conditions on the productions. In particular, the conditions on Projections operator establishes that, to be able to ask for the value of a property for the instances of a particular instance, the domain of the property must be compatible with the concept (i.e., not disjoint, which can be checked out by evaluating their conjunction). So, the system applies the specification to translate the query tree into And(Dom(owns), And(Person, Fish)). Resolving the different operators with the use of the DL reasoner, this expression leads to And(Person, And(Person, Fish)), which is inconsistent as we cannot ask for the properties of a concept that is not satisfiable. Note that all these checks cannot be performed before: Until the rendering step, the system is working just taking into account the structure of the queries. It is not until the system substitutes the typed gaps on the abstract queries with the input terms, that the actual query is built (along with its meaning). Due to the size of the query search space, we prioritized its reduction. Removing firstly all the possible abstract queries (each of which results on a set of actual queries after the query rendering step) 82 Chapter 5. Semantic Query Generation pruned the search space and lead to a lower number of queries to be checked than working with the actual terms from the beginning. Finally, the performance of this step is greatly boosted by the fact that the set of generated queries forms a conservative extension [CHKS08] of the original ontologies. Once an ontology has been classified, this property makes it possible to evaluate the satisfiability of the queries without reclassifying the ontology, as each query does not assert new knowledge into that ontology. 5.4.2 Semantic Enrichment When no query either is generated or satisfies the user, our system considers that something could be implicit in the user input. The average number of keywords used in keyword-based search engines “is somewhere between 2 and 3” [MRS08], so there is a high chance that the user might have simplified too much its information need, specially when it comes to expressing complex queries. To deal with this lack of information, our system adds virtual terms (VTs) to the original list of user keywords (Insert Virtual Terms step in Figure 5.1). These VTs represent possible keywords that the user may have omitted as part of her/his query, as a keyword query is a simplification of her/his actual information need. Then, the previous steps are executed again to generate queries considering these VTs. In our example, the extended inputs considered would be “person fish V Tconcept” and “person fish V Trole”, which allows the system to build, among others, the enriched abstract query And(Person (Some(V Trole, Fish))6(see Figure 5.7). This process is slightly different to query expansion [CR12], as our system works at structural level, aiming at building the exact query, instead of broadening/narrowing the search itself by adding actual keywords to the input. These queries with VTs have to be rendered again (Virtual Term Rendering step in Figure 5.1). Our system replaces any existing VT by compatible terms (i.e., terms of the same type: concept, role, or instance) extracted from the ontologies which the input keywords were mapped to in the disambiguation process (see Section 4.1). To build only semantically correct queries in an efficient way, the system narrows the set of candidate terms by using the ontology modularization techniques described in [JCS+08]. In the example, the previous enriched abstract query is rendered into And(Person (Some (is eaten by, Fish)), which actually represents 6Here, V Trole is the VT to be rendered with a compatible role. 5.4. Semantic Processor 83 R C VTR Insert Virtual Terms <C,C,C> <Person, Fish, VT > And Person And Fish ... <Person, Fish> Query Generation C And Person Some<C,C,R> <Person, Fish, VT > Fish ... VT Figure 5.7: Our system enriches the input set of keywords to generate underspecified queries. the exact semantics intended by the user when s/he entered the keywords “person fish”. This query enrichment process can be repeated iteratively by adding new VTs in order to deal with situations where the user did not enter a very descriptive set of keywords. Note that how, in the example, our system considered only VTs for concepts and roles. At first, we did not considered instances for the semantic enrichment as ontologies themselves usually do not have them (it happens frequently [WPH06]). Moreover, it seemed pretty safe to assume that when a user is looking for information about something very specific, the implicit keywords might be roles or concepts, rather than instances. For example, a user looking for information about terror movies (a possible query might be And(Movie, Fill(genre,terror)), will input “horror movies” instead of “movies genre”. However, our approach can effectively deal with instances as well, but we advocate for asking the user to explicitly fill the instance value when appropriate instead of showing her/him all the possibilities (which might be even unfeasible, for instance, when we are dealing with datatypes such as strings or integers). Anyway, a general keyword interpretation process that involves filling a semantic gap will generate many queries. Even when the meaning of each keyword has been perfectly established (and thus, its polysemy avoided), the number of possible interpretations will grow as the number of user keywords increases and the output query language allows to combine them in more ways. Besides, we do not want to limit our approach to provide the most popular results (syntactic search engines do that already), so we aim at not missing any possible interpretation (according to the accessible knowledge). We are aware that this may lead to the generation of a high number of queries (as there are many possible interpretations), and in the following section we propose different semantic techniques to deal with this problem. 84 Chapter 5. Semantic Query Generation 5.5 Reduction Techniques As stated in the previous section, the search space for the possible interpretations of a keyword query into a formal language grows quickly with the number of input keywords and the expressivity of the language. Fortunately, we can reduce this search space by applying several semantic techniques that allows our system to provide the user with an easier-to-handle set of possible interpretations. 5.5.1 Avoiding the Generation of Redundant Queries Trying to guess the user’s information need is a hard task due to the high number of possible interpretations. In our example, for the input “person fish” and one extra VT, there exist 780 syntactically possible queries for simplified BACK and 2832 for simplified DIG7. So, it is critical to reduce the number of generated queries. Apart from the number of input keywords, there are two main elements that lead to this high number of possible queries: The expressivity of the output query language, and the semantic enrichment step with VTs performed to fill the semantic gap. On the one hand, expressive query languages are very valuable, as they are more likely to be able to represent the user’s intended query. However, the higher the number of operators, the higher the number of possible queries (the operands can be combined in more different ways). On the other hand, adding new terms to the user’s input can help to discover the intention of the user. However, this will also increase the number of possible queries, mainly for two reasons: 1) new possible interpretations appear, and 2) there may be a high number of candidates to replace a given VT (some of them probably irrelevant). Along this section, we show how our system deals with these two issues. Then, in Section 5.5.2, we present a semantic technique that is applied to further simplify the output of the query generation. 5.5.1.1 Considering the Expressivity of the Query Language For expressivity of a query language, we understand its set of operators and the possible ways in which they can be combined to form a proper query. The more operators the language has and the more ways to combine them exist, the more queries will be possible. For example, if you add the Or operator to a language that had the And operator, the number of possible 7Simplified DIG is equivalent to simplified BACK plus the Or operator. 5.5. Reduction Techniques 85 queries for a user input considering both operators will be larger than the double. There is apparently no way to reduce this number because the different options express different queries. However, we can avoid building equivalent queries along the generation process by considering the semantic properties of the operators. In particular: •associativity: It is used by the Query Tree Generator to avoid, for example, building And(And(c1, c2),c3) if it has already generated And(c1,And(c2, c3)). •involution: It is used by the Query Tree Generator, for example, to avoid building Not(Not(c)), which is equal to c. •symmetry: It is used by the Query Renderer to avoid, for example, building And(c2,c1) if it has already generated And(c1,c2). Apart from those well-known properties, we saw in Section 5.2.1 that our system consider two other properties of the operators: Restrictiveness and inclusiveness. These properties are used in the Virtual Term Rendering step to avoid substituting the VTs by terms that would result in equivalent queries. For example, for the restrictiveness, if we have And(c1, concept), all the candidates that subsume c1 can be avoided as (any of them And c1) would result in c1. Following with the running example, let us suppose that a user enters “person fish” to find information about people devoured by fishes. Adding one VT to that input, the system generates 780 queries using simplified BACK and 2832 queries using simplified DIG, which are reduced to 72 queries (90,77% reduction) and 364 (87,15% reduction), respectively, by considering the semantics of the operators. In both cases the intended query Person And Some(is eaten by, Fish)) is among the final results. 5.5.1.2 Reducing the Number of Candidate Terms for Query Enrichment Usually, users simplify the expression of their information needs when they write keyword queries, which contributes to the semantic gap. Thus, a user may omit terms that form part of the actual information need. As we have seen before, to deal with the problem of possible information loss, some VTs can be added to the input, in order to generate the possible queries as if these VTs were proper terms introduced by the user. Then, the system performs a substitution of those VTs with actual terms extracted from the ontologies considered. 86 Chapter 5. Semantic Query Generation Following this idea, one can think about using each term of the same type as the inserted virtual one. For example, if the VT was a concept, the system could substitute it with all the concepts of the input ontologies (and generate one query for each different candidate concept). However, as the number of queries with VTs could also be high, considering all the terms of the input ontologies to render each VT for each query is too expensive. In order to reduce the number of candidates for rendering a VT while avoiding losing any possible related term, we apply the modularization and re-using techniques explained in [JCS+08]. More specifically, the system uses ProS´ E, which, given a set of terms of an ontology (signature), makes it possible to extract different modules that can be used for different purposes. Our system uses the user input terms as signature and extracts a module such that the same information can be inferred from the extracted module as from the whole ontology, as shown in [JCS+08]. This allows the discovery process to focus only on what is related to the input terms. After applying the modularization techniques for the user query “person fish”, the system generates 32 queries using BACK (15 after filtering, 98.07% less than the 780 original possible ones), and 148 queries using DIG (73 after filtering, 97.42% less than the 2832 original possible ones). The intended query is still among the final results, as the system does not miss any possible interpretation. Note that, in the example, we have used a single ontology to depict the impact of the technique. However, the modularization is already applied during the integration of the local ontology. Anyway, applying this technique again, with different parameters for ProS´ E, might lead to a further narrowing of the search space. 5.5.2 Extraction of Relevant Query Patterns Besides reducing the number of generated queries, the way in which they are presented to the user also makes a difference. Users’ attention is a capital resource and they can get easily tired if they are forced to browse over too many options to select their intended query. In this stage of the search process, recall seems to be crucial as only one interpretation will fit the user’s information need. Ranking the generated queries according to their probability of reflecting the user’s interest can be an approach to minimize the interaction with the user. However, it is not clear how to identify the query that a specific user had in mind when writing a set of keywords, even though the meanings of the individual keywords in the input have been identified previously. For example, with the input “person fish” the user might be looking for information about people devoured by 5.5. Reduction Techniques 87 fishes, but also about people who work with fishes (e.g., biologists, fishermen, etc.), among other interpretations. Besides, a statistics-based approach may be not suitable for ranking queries, as it would hide possible interpretations that are no popular in the community. Approaches based on semantic and graph distances would also hide possible meanings. Due to these reasons, we advocate a different and orthogonal approach to ranking. Our approach tries to minimize the amount of information that will be presented to the user by identifying query patterns, and could be combined with any query ranking approach if it is available. The semantic technique that we propose takes advantage of the syntactic similarity of the generated queries and of the ontological classification of the terms that compose the queries. A small example is shown in Table 5.4, where we can see that several queries may have a similar syntactic structure. Queries Patterns All(drives, Person) And bus All(Role, Concept) And Concept All(drives, Bus) And person ... Some(drives, Person) And bus Some(Role, Concept) And Concept Some(drives, Bus) And person ... All(drives, Bus And Person) All(Role, Concept And Concept) ... Some(drives, Bus And Person) Some(Role, Concept And Concept) ... Table 5.4: Queries and patterns generated for “person bus”8using BACK. Thus, the system analyzes the structure of the queries to extract common query patterns which lead to a compact representation of the queries. This is especially useful when the system tries to find out the user’s intention by adding VTs. A query pattern shows an expression with the VTs not substituted (i.e., with gaps) and the system maintains a list of potential candidates for each gap. At this point, a new challenge arises: How can the candidates for a gap be organized to facilitate their selection by the user? We advocate the use of a DL reasoner to show the candidates and allow users to navigate through their taxonomy. The interface shows a list of candidate terms and three buttons for each gap in each pattern (see Figure 5.8): 8Mapped to homonym terms in People+Pets,http://www.cs.man.ac.uk/~horrocks/ ISWC2003/Tutorial/people+pets.owl.rdf, last accessed October 3, 2013. 88 Chapter 5. Semantic Query Generation Figure 5.8: Example of query patterns for “person drives” and “person fish”. •Fix: Performs the substitution with the candidate term selected. •Subsumers: Enables the user to generalize the candidate term selected. •Subsumees: Enables the user to refine the candidate term selected. This allows to show a high number of queries in a really compact way and provide a navigation in a top-down style through the terms of the ontology. Thus, the most general terms are initially presented to the user, who can then move through the taxonomy by accessing each time a direct subsumers/subsumees level. Users are allowed to select only terms that are relevant for the corresponding gap, i.e., their selections will never lead to an inconsistent query. Thus, for example, for the input “person fish”, the system is able to show the 15 final queries obtained using BACK under 7 patterns, and the 73 obtained using DIG under 20 patterns. Moreover, this representation allows the system to establish an upper bound on the number of user clicks needed to select their query, which is equal to the depth of the taxonomy of the ontology multiplied by the number of substitutions to be performed (number of gaps). 5.6 Summary of the Chapter In this chapter, we have presented the core of our proposal for interpreting keywords in different query languages. First, we have detailed how we can specify different query languages through the use of specially annotated grammars, which comprise the semantics of the different operators of the language. These grammars lack syntax completely, and allow QueryGen to be completely syntax agnostic. Moreover, they allow to semantically 6.2. Accessing DBpedia from DL Queries 95 Figure 6.2: Articles in Wikipedia become resources in DBpedia, inheriting the URI of the article and its categorization. When moving from the article world of Wikipedia to the semantic resources in DBpedia, there are objects that might augment their descriptions as the new semantic model can represent more information about them. The articles extracted from Wikipedia, once in DBpedia, become resources. Each resource is represented by an URI and has a direct correspondence to its original Wikipedia’s article, inheriting its categorization. The whole taxonomy of article categories of Wikipedia is included as a SKOS ontology in DBpedia; thus, DBpedia provides a first view on the resources according to their category (see Figure 6.2). Class dbo:Person Class yago:Person10007846 Resource dbr:Albert_Einstein Resource dbr:Viscosity Category cat:Theoretical_physicists Category cat:Fundamental_physics_concepts Category cat:Viscosity dcterms:subject dcterms:subject rdf:type classifying resources categorizing articles dbo: yago: dbr: cat: http://dbpedia.org/ontology/ http://dbpedia.org/class/yago/ http://dbpedia.org/resource/ http://dbpedia.org/resource/Category: Namespace Figure 6.3: DBpedia excerpt of the descriptions of Albert Einstein and Viscosity resources. Depending on the content of its corresponding article, a DBpedia resource might also be representing an object (see Figure 6.3). The classification of this object dimension of the resources is done via several general 96 Chapter 6. Accessing Data domain ontologies, being DBpedia Ontology2and YAGO3the most important ones. In this way, independently of the article categorization, DBpedia offers a second different view based on the nature of the underlying resources. However, this view does not cover all DBpedia. There exist resources that, despite being categorized, do not have these descriptions as they are not defined in the used ontologies, as shown in Figure 6.3. Summing up, DBpedia organizes knowledge in two major ways: The SKOS categorization, and an ontological classification; and exposes this knowledge through an SPARQL endpoint. In this thesis, we have added this endpoint using the DBpedia ontology as entry point. However, the SKOS categorization could also be used without an adaptation effort. 6.2.1 DBpedia Adapter The Adapter for DBpedia we have developed is characterized by the following tuple: <{< SBack, SBackGrammar >}, Snapshot, {RDF }> That is, it supports the simplified version of BACK that we have used in the previous chapter, processes snapshots queries, and returns the data in RDF. As DBpedia offers a public SPARQL endpoint to access its data, the Adapter has to translate the DL queries into SPARQL to properly forward the possible queries. To do so, the Adapter traverses recursively the selected query (in fact, its associated query tree) applying the query rewriting rules4 shown in Table 6.1. For simplicity’s sake, only a binary version of And operator has been considered, altough the actual algorithm considers that And can have more than two operands. Moreover, during the traversal, new variable names are created to bind the resources appropriately. In these rules, obtainGraph is the entry point for the recursion, as it expands the concept expression that is passed as an argument until it reaches the leafs of the query tree. We assume that the underlying RDF repository has materialized, at least, the hierarchy inferences. Note how the translations of the operators that are applied on a role bind the answer resources 2The DBpedia Ontology, http://wiki.dbpedia.org/Ontology, last accessed October 3, 2013. 3YAGO Ontology, http://www.mpi-inf.mpg.de/yago-naga/yago/, last accessed October 3, 2013. 4We consider SPARQL v1.1, where the filter NOT EXISTS was added. The status of SPARQL v1.1 has changed from Proposed Recommendation to Recommendation during the writing of this thesis. Besides, repositories such as VirtuosoDB currently supports it. 6.2. Accessing DBpedia from DL Queries 97 And(C1,C2)⇒{?x a obtainGraph(C1,?x). ?x a obtainGraph (C2,?x)} Some(R1,C2)⇒  { { ?x a Dom(R1). ?x R1?y}. ?y a obtainGraph(C2,?y)} All(R1,C2)⇒       {?x a Dom(R1). F ILT ER NOT EXIST S {?x R1?y . F ILT ER NOT EXIST S {?y a obtainGraph(C2,?y)} } } Fill(R1,I1)⇒{?x a Dom(R1). ?x R1I1} C1⇒ { ?x a C1.} Table 6.1: Rewriting rules applied by the DBpedia Adapter. to belong to the domain of the role. If such an assumption cannot be made, we should relax these constraints. Otherwise, operators such as Some or All would return none results unless the direct assertions would have been made (the RDF statements of the resources belonging to the domain of a property would not be present, and therefore any subgraph would be matched). Finally, the obtained graph expression is extended by adding the different bindings needed to retrieve the properties that are considered in the Projections operator. In the following subsection, we present a complete example of accessing data from DBpedia. 6.2.2 A Complete Example with Data from DBpedia To illustrate how our system works, we will give a complete example from the input of the user to the data retrieved by our system from DBpedia5. We restrict the semantics to the different ontologies used in DBpedia for the sake of simplicity in the explanations. As an illustrative example, let 5The namespaces used in this section are dbpedia http://dbpedia.org/,dbo http: //dbpedia.org/ontology/, and dbpprop http://dbpedia.org/property/. 98 Chapter 6. Accessing Data us assume that a user watched old cartoons starred by a dumb tall black dog many years ago. S/he does not recall its name (in fact, s/he is thinking about Goofy, the Disney character), but s/he wants to know since when this character exists. As s/he cannot provide more specific input, s/he inputs the keywords “Fictional Dog Appearance”: 1. In the disambiguation process, our system offers the user several interpretations for each keyword: •For “Fictional”, one of the proposed meanings is the concept dbo:FictionalCharacter. •For “Dog”, one of the proposed meaning is an integrated sense containing DBpedia URL dbpedia:resource/Dog, considered as an instance of Animal in the DBpedia ontology. •For “Appearance”, one of the proposed meanings is the role dbo: firstAppearance. 2. In the generation process, the user cannot find the intended query, as no combinations of FictionalCharacter,Dog and firstAppearance represents her/his intended query. However, by considering one VT during the semantic enrichment step, the system can try adding the role dbpprop:species. This allows the system to find out the query intended by the user: [firstAppearance](F ictionalCharacter And (F ill species Dog)) which has to be read as “retrieve the first appearance of the fictional characters whose species is dog”. 3. The system detects that the query can be processed by the DBpedia Adapter as it supports the language of the query, so it forwards the query to it, which translates the query into the corresponding underlying query language (a SPARQL sentence): SELECT * FROM <http://dbpedia.org> WHERE { ?x a dbo:FictionalCharacter. ?x dbpprop:species <http://dbpedia.org/resource/Dog>. ?x dbo:firstAppearance ?y. } 6.2. Accessing DBpedia from DL Queries 99 which retrieves the first appearance of several fictional dogs (see Table 6.2), among which Goofy’s can be found6. Character FirstAppearance http://dbpedia.org/resource/Max_Goof http://dbpedia.org/resource/Goof_Troop http://dbpedia.org/resource/Max_Goof http://dbpedia.org/resource/Fathers_Are_People http://dbpedia.org/resource/Bolt_(character) http://dbpedia.org/resource/Bolt_(2008_film) http: // dbpedia. org/ resource/ Goofy http: // dbpedia. org/ resource/ Mickey’s_ Revue http://dbpedia.org/resource/Spike_and_Tyke_(characters) http://dbpedia.org/resource/Dog_Trouble http://dbpedia.org/resource/Huckleberry_Hound http://dbpedia.org/resource/Huckleberry_Hound_Meets_Wee_Willie http://dbpedia.org/resource/Droopy) http://dbpedia.org/resource/Dumb-Hounded Table 6.2: Results for the first appearance of fictional dogs returned by DBpedia (including Goofy’s). In this example, the system presented an average of five senses for each input keyword, which resulted in 14 query patterns representing 172 queries. If we search Google using the same input (“Fictional Dog Appearance”), it returns 12.800.000 results, without any reference to Goofy in the ten first pages. The first result returned by Google links a list of famous fictional dogs in Wikipedia. But in that list there is no answer to the user query (first appearance of Goofy): S/he has to browse the whole list of 65 dogs to find Goofy (and recall its name, hopefully), and click its page to look for the information inside the text. Notice that the list returned by our system contains the first appearances of dog characters, while the list in Wikipedia links to dog characters pages (not necessarily containing their first appearance). Thus, taking the same input as starting point, our system has performed a semantic search returning the first appearance of fictional dogs, while using a search engine we can just obtain information about dogs. If we replace in the input “Appearance” by “series”, our system is able to answer, for example, in which series Odie and Scrappy Doo appear. 6The amount of results that the public SPARQL endpoint of DBpedia provides depends on the current workload. The results presented are from June 21, 2013. 100 Chapter 6. Accessing Data 6.3 Accessing LOQOMOTION with Extended Semantics LOQOMOTION [IMI06] processes continuous location-based queries in a distributed and efficient way using mobile agents. During this thesis, we have extended its query language by adding semantics to the locations it was able to deal with. This bridges the semantic gap that there exists from GPS locations to the user’s vocabulary, and extends the semantics of location constraints. In this section, we firstly present an overview of the network of agents that LOQOMOTION deploys to process the queries. Secondly, we present the notion of semantic location granules, and we propose two complementary models for them. Then, we analyze the influence of using location granules on the expressivity of location-dependent queries, and how they can be integrated into the query model of LOQOMOTION. Finally, we present the Adapter that allows QueryGen to process queries using LOQOMOTION. The language used is the SQL-like query language presented in Section 6.3.3, and we will see how, through the use of the local and global conditions, QueryGen is able to perform the semantic checking even with non-DL query languages, such as this one. 6.3.1 LOQOMOTION Architecture Firstly, we present the basics of LOQOMOTION without considering location granules. No attempt is made to justify the use of mobile agents or the relation between LOQOMOTION and other systems for locationdependent query processing (for details about this, see [IMI06] and/or the survey in [IMI10]). To clarify the explanations, the scenario shown in Figure 6.4, and a query that retrieves the interesting objects within the (inner) moving query circles (relevant areas) centered on the reference objects car38 and policeCar5, will be considered7. In LOQOMOTION there is a static agent called QueryMonitor, executing on the mobile device of the user, and three different types of agents (two of them, mobile agents [TIM07,BIM10a]) are in charge of processing the query on the fixed network: •A mobile agent MonitorTracker on the fixed network (initially, on Proxy6 in Figure 6.4) is in charge of communicating, to the user device, the updated data about moving objects relevant to the query 7The areas shown in Figure 6.4 are circles, but this will not be necessarily the case when location granules are used. 6.3. Accessing LOQOMOTION with Extended Semantics 101 Target class: policeUnit policeman2 policeCar5 car15 policeCar4 policeman1 policeCar1 Proxy1 Proxy2 Proxy3 Proxy4 Proxy6 Proxy5 policeStation19 policeCar2 policeCar3 policeStation2 car38 policeStation3 (extended area, 0.87 miles) objects to watch (relevant area, 0.42 miles) query circle objects to watch (extended area, 0.75 miles) radius extension 0.33 miles user radius extension 0.31 miles Target class: policeCar MonitorTracker Tracker Updater query circle (relevant area, 0.56 miles) policeCar15 Figure 6.4: Query processing in LOQOMOTION: sample scenario. (target objects). This agent always executes on the proxy corresponding to the proxy area where the user is, following the user, to optimize communications with the mobile user device. •For each reference object, a mobile agent Tracker keeps itself on the proxy that handles the location of that reference object to track it (e.g., in Figure 6.4 the Tracker for car38 is initially executing on Proxy4, as car38 is within the coverage of that proxy), and computes the area that contains the objects that must be communicated to the MonitorTracker (called extended area). •For each proxy whose area intersects the extended area (the relevant proxies), a static Updater agent is created by such a Tracker (e.g., in Figure 6.4, the Tracker on Proxy4 sends Updaters to Proxy3,Proxy4, and Proxy5). An Updater is in charge of retrieving the interesting objects within its area by executing standard queries (i.e., queries without 102 Chapter 6. Accessing Data location-dependent constraints such as inside) on its proxy. The different mobile agents maintain themselves on the relevant proxies, to keep track of the interesting objects. In this way, they support an efficient continuous query processing, as results can be ready when a refreshment is needed. The use of mobile agents in LOQOMOTION facilitates: 1) tracking the positions of relevant objects efficiently, 2) optimizing the wireless communications, and 3) supporting the distributed query processing efficiently. For further details about this system, see [IMI06]. 6.3.2 Semantic Location Granules The existing work on location-dependent query processing implicitly assumes GPS locations for the objects in a scenario (e.g., [SWCD97,PXK+02, MXHA05,CHCX06,GL06, DTS08, IMI10]). However, some applications do not require location data at GPS resolution, and a coarser representation may be more appropriate for them. For example, a train tracking application would need to just consider in which city a train is currently in, and not its exact coordinates. For such applications, it is useful to define the concept of location granule as a set of physical locations [IMB07, ICBM09, BIM10b, IBM11, BBMI13]. This concept is similar to the concept of place in [Hig03,HS07,HS09] or spatial granule in [BCP09]. However, when we group a set of locations and give them a name, we are implicitly giving them also a meaning. For example, the set of locations that compose Madrid, when grouped under the name Madrid, become a city, the capital of Spain. Thus, the grouped locations become a new different entity as a whole, which could be related to other entities in different ways besides spatial relations. So, to model them, semantic location granules [BIM10b, BBMI13] are introduced (as defined in [BIM10b]): Definition 6.3.1 Asemantic location granule is a location granule with well-defined semantics, i.e., explicitly stated. Their semantics can be modeled using ontologies and, depending on the role that the locations are having in the system, we advocate for two complementary models for them. The former one considers the location granules as instances of a concept Granule, and allows us to extend the query model using logical rules on the ABox. The latter one, on the other hand, considers that the granules themselves are concepts, as they subsume a set of locations (which now become the instances). As we will see, this latter model allows the DL reasoner to make intensive use of the TBox to infer the containment relationships. 6.3. Accessing LOQOMOTION with Extended Semantics 103 6.3.2.1 Modeling Semantic Location Granules as Instances From an object-oriented point of view, one could argue that the location granules are instances of different types of classes, that would be the ones that define their characteristics [BIM10b]. Thus, modeling them in this way, we proposed the ontology in Figure 6.5. In this model, the notion of semantic granule map appears explicitly: Definition 6.3.2 Asemantic granule map is a set of semantic granules identified by a common name. It provides the global semantics of the location granules that participate in it. Thus, semantic location granules are also grouped to provide an interpretation of the location space, conforming semantic layers. This ontology is not meant to be complete, but a starting point to be extended and adapted to particular scenarios. The most basic properties that we identified are the following (see Figure 6.5): isEncapsulated Granule URI String Concept Datatype Role Domain Range GrMap encapsulates groups contains TT Name physicalSet identifier Additional Properties T = Transitive Role −1 −1 −1 participates groups contains encapsulates isContained Figure 6.5: Semantic location granules as instances: base ontology. •Contains: It represents the physical inclusion of a granule inside another. For example, the granule Spain (the country) contains, among others, the granules Madrid and Barcelona (the cities). This property permits to establish a spatial hierarchy to organize the granule instances. Its inverse property is isContained. •Groups: It represents the relationship that there exists between a granule map and the granules that make it up. For example, the 104 Chapter 6. Accessing Data granule map Countries would group the granules Spain,France, etc. Its inverse property is participates. Note that a granule can participate in several granule maps. •Encapsulates: It allows to establish hierarchies between granule maps according to the granularity level. For example, the granule map provincesOfSpain could encapsulate citiesOfSpain. Its inverse property is isEncapsulated. The rest of the properties are used to identify the granules (name) and the granule maps (identifier), and to associate a granule to one or several sets of physical coordinates (physicalSet). The physical coordinates are also accessible at the semantic level to allow including statements about them in the asserted knowledge and, therefore, to allow the system to perform spatial reasoning (for example, using RCC [GSBM08,RCC92]). Although this basic ontology may seem too simple, direct benefits can be obtained out of it. For example, even without any additional extension in the semantics, the presentation of results of the queries can be enhanced by exploiting the inclusion relationships to offer different views of the same answer set. Besides, we wanted to keep the model as simple as possible to make it easier to adapt it to the desired semantics. 6.3.2.2 Modeling Semantic Location Granules as Concepts On the other hand, if we consider that each of the locations themselves are instances, a semantic location granule must be modeled as a concept, as it subsumes geometrically their components [BBMI13]. To formalize the concepts of semantic granules and semantic granule maps with DLs, we will consider that a transitive role named isContained and concrete features locx1, . . . , locxnare defined in our model. Intuitively, the role isContained will be used to express that a granule is geographically contained in another one by subsumption and participation in the relationship, (e.g., NewY ork v ∃isContained.EEUU), and locx1, . . . , locxnwill be the coordinates of a point. These concrete features allow us to define areas, for example, locx≥10 ∧locx≤20 ∧locy≥20 ∧locy≤30 (if we work in R2, we write locx, locyinstead of locx1, locx2). Definition 6.3.3 An area concept f(locx1, . . . , locxn)is a concept built with operators ∩and ∪, and a combination of path-free compositions using concrete features locx1, . . . , locxn. An area concept name Ais a concept name 6.3. Accessing LOQOMOTION with Extended Semantics 111 General query structure Query →select Projections from Class-names (where Conds)? Class-names →Class-name (‘,’ Class-name)* Projections →Attr-Loc-Select (‘,’ Attr-Loc-Select)* Attr-Loc-Select →attribute |Loc-Select attribute →Qualified-attr |Unqualified-attr Qualified-attr →Class-name ‘.’ Unqualified-attr Loc-Select →Object-id ‘.’ ‘loc’ |gr ‘(’ Map-id ‘,’ Class-name ‘)’ Conditions can be standard conditions on attributes or location-dependent conditions Conds →Cond ((and |or) Cond)* Cond →(Bool-Cond |LDQ-Cond) Bool-Cond →attribute Comp Value Location-dependent conditions /* The focus is on inside constraints */ LDQ-Cond →inside ‘(’ Args-Inside ‘)’ |... Args-Inside →Radius ‘,’ Loc-Ref ‘,’ Loc-Target Loc-Ref →Object-id |GPS-coord | gr ‘(’ Map-id ‘,’ Object-id ‘)’ | gr-map ‘(’ Map-id ’,’ Gr-id ‘)’ Loc-Target →Class-name |gr ‘(’ Map-id ‘,’ Class-name ‘)’ Radius →Real Units Basic grammar productions String →([a-z] |[A-Z] |[0-9])+ Real →([0-9]+) (‘.’ [0-9]+)? Class-name →String /* Name of a class of objects */ Unqualified-attr →String /* Name of an attribute for a selected class */ Object-id →“ String ” /* Identifier of an object */ Map-id →“ String ” /* Identifier of a granule map */ Gr-id →“ String ” /* Identifier of a granule */ GPS-coord →‘(’ Real ‘,’ Real ‘)’ /* Two dimensions are assumed */ Units →meters |kilometers |miles |... Comp →‘=’ |‘>’|‘<’|‘>=’ |‘<=’ |‘<>’ Value →([0-9]+) |“ String ” Figure 6.8: Syntax of location-dependent queries with location granules. 6.3.4 LOQOMOTION Adapter While being complementary, the Adapter for LOQOMOTION adopts the location model where the location granules are represented as instances. In this section, assuming this location model, we present how its query language is adapted to work with QueryGen. The LOQOMOTION Adapter that we have developed is characterized 112 Chapter 6. Accessing Data by the following tuple: <{< KeyLOQO, KeyLOQOGrammar >}, {Snapshot, Monitoring, Continuous},{CSV }> That is, it supports an adaptation of the SQL-like query language that we have presented in the previous section, it can process the three types of queries that QueryGen supports, and it returns the data in comma-separated values format. In Table 6.3, the adapted grammar is presented. According to the grammar definition presented in Section 5.2.1, the elements of this grammar are as follows: •The initial symbol Qis Query. • {Opi}contains Projections, GrM, GrG, And, Or, Inside, and Comp nonterminals; {Qps}contains Projection, Attrib, LocSelect, LocReference, LocTarget, and Loc; and {Rtypes}contains Concept, Role, and Instance nonterminals. •T, as we have defined before, contains C, R, I, and ξtokens. •Pcontains each one of the productions in Table 6.3. Note that there are additional elements: In this case, the operator that translates a location into a granule according to a map (gr operator, explained in Section 6.3.3) is separated into two different nonterminals depending on the arguments it takes (GrM and GrG), and, to be applicable, they need that the operators belong to specific concepts defined in the location model presented in Section 6.3.2.1, where location granules are modeled as instances. In this language, there exist operands whose semantics are not directly checkable with a DL-reasoner. In particular, let us focus on Inside,GrM, GrG, and Comp operators, the most complex ones: •Inside imposes a condition on the location attribute of the returned objects. The type of the returned objects is specified in the LocTarget production, and therefore, that is the concept that is propagated as global condition. •GrG returns a granule object. It might take two different operands (along with the mapping to be used): A location point or the name of a granule in the mapping (in this case, an instance of granule). To 6.3. Accessing LOQOMOTION with Extended Semantics 113 Production Global Conditions Local Conditions Query →And($1, $2) Projections Concept Projections →And($1, $2) Projection Projections Projections →ξNeutral Projection →Attrib $1 Projection →LocSelect $1 Attrib →R Dom($1) Attrib →C R And($1, Dom($2)) Satisfiable(And ($1, Dom($2))) LocSelect →Loc LocSelect →GrM $1 LocReference →Loc LocReference →GrG LocTarget →C $1 Satisfiable($1) LocTarget →GrM $1 Loc →I GrM →I C $2 InstanceOf($1, GrMap) ∧ Satisfiable($2) GrG →I I InstanceOf($1, GrMap) ∧ InstanceOf($2, Granule) GrG →I Loc InstanceOf($1, GrMap) Concept →C $1 Concept →And $1 Concept →Or $1 Concept →Inside $1 Concept →Comp $1 And →Concept Concept And($1, $2) Or →Concept Concept Or($1, $2) Inside → LocReference LocTarget $2 Comp →C R C R Or($1,$3) Satisfiable(And($1, Dom($2))) ∧ Satisfiable(And($3, Dom($4))) ∧ Satisfiable(And(Range($2), Range($4))) Comp →R R Or(Dom($1), Dom($2)) Satisfiable(And(Range($1), Range($2))) Comp →R C C Or($2, $3) Satisfiable(And($2, Dom($1))) ∧ Satisfiable(And($3, Dom($1))) Table 6.3: Annotated grammar for a subset of the query language of LOQOMOTION (KeyLOQO). check that it is properly applied, the system has to check that the first operand is an instance of GrMap, and that the second operand (when 114 Chapter 6. Accessing Data it is not derived from a Loc production) is an instance of Granule. This way, our system can perform a semantic checking on the operands. It does not impose a global condition, as it only affects to the interpretation of the reference position to define the interest area, and it does not constraint semantically the nature of the objects to be returned. •GrM changes the way that the location constraint has to be processed. As we have seen in Section 6.3.3, it has different meanings depending on the position of the query. Anyway, the semantic checkings to be performed are the same ones for both situations. It needs two operands, a mapping and the concept of the target objects (the ones to be returned by the constraint). The checking is performed locally, and this time, it returns the concept of the target objects as global condition. This way, it can be propagated and its consistency checked along the rest of operands. For example, if we specified an inside constraint with Dogs as target objects, and the rest of the concept definition is about people (we assume that Dog and Person are stated as disjoint concepts), when the Inside or the LocSelect productions return the concept Dog, it will be checked against the rest of the expression. •Finally, Comp is the comparison operator. It allows the system to generate JOINs, for example. We have modeled it in three flavors, depending on the number of concepts and roles that we had in the input: –Only two properties are specified: We establish via the local conditions that the range of both the properties has to be compatible. On the other hand, we let the result of the comparison be the union of both domains. We assume that the rest of the query constrains the resulting set. –Two concepts and a property: We are comparing the instances of two different concepts according to the value of a property. Thus, we establish that the property has to be applicable9to both concepts (local condition). In this case, the resulting concept is the union of both compared concepts. –Two concepts and two properties: The comparison is made on an arbitrary property of each of the concepts. This case is the 9We consider a property applicable to a concept when its domain its not disjoint with it. We check it by testing the satisfiability of their intersection. 6.3. Accessing LOQOMOTION with Extended Semantics 115 combination of the two previous ones, as the ranges of the properties have to be compatible, and the properties applicable to its corresponding concept (local conditions). As with the previous one, the resulting set is the union of the participating concepts. Once the query has been semantically checked, we let the responsibility for its correct translation into the actual language syntax to the Adapter implementation. In the following subsection, we give a complete example of QueryGen using LOQOMOTION as backend. 6.3.5 A Complete Example with LOQOMOTION as Backend System In this section, we present a synthetic example to illustrate the keyword interpretation process with LOQOMOTION as target information system. In this case, we focus on how QueryGen is able to work with locationdependent operators such as Inside operator adding the semantics of the granules. Let us take a user that wants to monitor information about buses nearby Zaragoza. Thus, to do so, s/he inputs the keywords “Zaragoza bus passengers location”. The model for the location granules that we are using is the one shown in Figure 6.5. To populate it, we could easily reuse the information available in several Linked Data initiatives such as Linked GeoData [SLHA12], GeoLinkedData [VBVTS+10], or GeoNames10. Thus, we extend the model by adding the subconcept City, that is subsumed by Granule, and we group the cities of Spain under a mapping that is identified by SpanishCities. 1. In the disambiguation process, our system offers the user several interpretations for each keyword: •For “Zaragoza”, the proposed meaning is the instance of City. •For “bus”, one of the proposed meanings is the concept Bus from the OWL version of OntoSem ontology [BGK06]. •For “passenger”, one of the proposed meanings is the homonym property from OntoSem. •For “location”, one of the proposed meanings is the integrated sense of the location property from the DBpedia ontology, schema.org and OntoSem. 10http://www.geonames.org/, last accessed October 3, 2013. 116 Chapter 6. Accessing Data 2. In the generation process, at first, our system cannot build the intended query because it needs an extra instance to assign Zaragoza the correct granularity interpretation according to the SpanishCities mapping. As we have seen in Section 5.4.2, despite the fact that instances were not considered from the beginning, our system can add a VT of instance type. This allows the system to find out the query intended by the user: [location, passenger]Inside(GrG(Zaragoza, SpanishCities), Bus) which would retrieve the location and the passengers of the buses that are inside a radius from Zaragoza considered as a City. During the generation, QueryGen checks that Zaragoza is an instance of Granule, and that SpanishCities is an existing GrMap thanks to the local conditions established in the language definition. Moreover, passenger and location are projected because they are semantically applicable. However, the responsible for the modeling of the scenario has to take into account the need of a correct alignment between the properties defined in the ontologies used for the disambiguation and the properties defined in the LOQOMOTION scenario. Otherwise, the Adapter has not enough information to know how to access the data. 6.4 Summary of the Chapter In this chapter, we have explained the solution adopted to attach different data models to QueryGen. Thanks to the use of Adapters, QueryGen can forward the selected query to the appropriate underlying information system, adapting both the data model and the query execution model. These Adapters are an evolution of the wrappers proposed in OBSERVER [MI01], which adapted the queries to the different answering capabilities of the data repositories. In particular, the main capabilities that our system inherits from OBSERVER are the data integration capabilities and the ability of processing incomplete queries. Then, we have presented two successful use cases that have been implemented and registered into QueryGen: DBpedia (its SPARQL endpoint) and LOQOMOTION. •The first case provides a complete example of a semantic data access pipeline, going from plain keywords to the semantic data available in DBpedia in the form of Linked Data. 6.4. Summary of the Chapter 117 •The second case provides an example of how a system that, in principle, did not take into account any kind of semantics can be adapted and added to QueryGen to perform a semantic search on it. Last but not least, in this chapter, we have introduced two different semantic models for representing location granularities. They are complementary, as they are oriented for different tasks: The former is aimed at extending the capabilities of location dependent queries through the addition of semantics to location constraints [BIM10b], while the latter is aimed at providing automatic reasoning on the location model [BBMI13]. In fact, the second model can be used to feed the first one. 118 Chapter 6. Accessing Data Chapter 7 Experimental Results In this chapter, we present an evaluation of our approach from different points of view. We start by presenting a qualitative evaluation of the whole process, accessing data from DBpedia, and analyzing the current advantages and shortcomings that we have detected. Then, we analyze the performance of the different steps of the approach and the reduction rate achieved by the reduction techniques that QueryGen applies in the query generation process. 7.1 Evaluating the Semantic Capabilities of QueryGen To evaluate the semantic capabilities of our system, we have performed two different evaluations. First, we have focused only on the quality of the discovery of the user’s intended meaning, regardless of the source ontologies for the different meanings. Secondly, we have turned our focus on the evaluation of our current prototype accessing data from DBpedia, which has brought up several issues that conform the main lines of future work in this thesis. In the rest of the section, we present firstly the query set that we have selected, and then we present and analyze the results of both performed evaluations. 7.1.1 Selected Query Set To evaluate qualitatively the semantic capabilities of QueryGen, we considered at first two different query sets that are currently being used in different search contests: 119 120 Chapter 7. Experimental Results •Text REtrieval Conference (TREC)1Web Track The Web Track of this conference focused on Information Retrieval evaluation was discontinued in 2004, and it returned in 2009. In order to assess the quality of different Web Search engines, they provide a set of packages of 50 queries2expressed in keywords. Each of these queries has several retrieval tasks associated to it. •Query Answering over Linked Data (QALD)3[LUCM13] This contest/track is more recent than the TREC one, and it focuses on Linked Data resources. It is used to assess natural language interfaces and different keyword interpretation techniques over Linked Data, and up to now, there have been three contests held on a year basis. It considers DBpedia along with a RDF export of MusicBrainz4as data sets, and provides 100 queries with the expected results for each of them. Excepting the first year (QALD-1 query set), the queries are expressed both in natural language and keywords as well. QALD-2 and QALD-3 are equivalent, as the latter is just an extension of the former to address multilingual issues. We selected the set for the 2013 contest, QALD-3, to perform the evaluation, and in the following we will refer to it as the QALD query set. We discarded the first one as, in fact, the keyword sets that TREC provides for the Web Track are not oriented to search on structured information, thus, the semantic gap from the expressed keywords to the real meaning is huge. One could argue that this is the kind of input you have to expect from the users, but this gap seems to be the result of the users’ training over the years, who have learnt that Web Search engines do not retrieve what they were looking for, and therefore, they just relax their inputs to begin with the navigation on the first results as soon as possible [MMZ09]. Thus, we focused on evaluating our approach against the second query set. Moreover, in the QALD query set, for each query, they provide a SPARQL query that expresses the exact semantics corresponding to the input (natural language or keywords). Thus, it provides a mean to compare our results objectively. To properly evaluate the results of each of the steps of QueryGen, 1http://trec.nist.gov/, last accessed September 30, 2013. 2There is one package for each of the years that this track has been held, this is, 200 queries considering the 2009-2012 conferences. 3http://greententacle.techfak.uni-bielefeld.de/~cunger/qald/, last accessed October 3, 2013. 4http://musicbrainz.org/, last accessed October 3, 2013. 7.1. Evaluating the Semantic Capabilities of QueryGen 127 such as property (e.g., isLocated), we wouldn’t need this operator to build this query. •For the input keywords “Yenisei, river, flow, through, country” representing the query “Through which countries does the Yenisei river flow?”, QueryGen maps correctly all the keywords to terms in several ontologies, but flow one. It is mapped to a concept, while the property that we were looking for querying correctly DBpedia is dbpedia: country. This property is hidden by the fact that we are looking for countries and the user might choose Country as concept instead of choosing the dbpedia:country property as it is not intuitive. As in the previous query, an inverse of one of the operators is needed (in this case, the Fill operator) to get the instances that are related to the Yenisei river via the inverse property (which in this case does not exist in DBpedia). •For input keywords “school, type” meaning “Give me all school types”, our system obtains dbpedia:School and the property dbprop:type from the DBpedia ontology. These meanings (among others) do not allow our system to generate the desired query because of their semantics and how they are used in the DBpedia dataset. Although is quite counterintuitive, is not possible to access from the School concept, to the SchoolTypes concept. This is due to the fact that the YAGO’s concept comes from the SKOS categorization of the Wikipedia articles, which is left aside in the DBpedia ontology (as it is explained in Section 6.2, more details can be found in [BEM13]). YAGO is built extracting automatically all the information and introduces a lot of semantic noise. This case is a good example of it: Instead of classifying the different schools as subclasses of School, YAGO enumerates the types of school that there are, as directly extracted from the SKOS taxonomy of article’s subjects. This query could be directly answered if we added the YAGO taxonomy to our system, considering the fact that both keywords were mapped just to one concept: yago:SchoolTypes. •For the input keywords “Tom Cruise, movie”, as we have seen before, our system disambiguates correctly Movie, discovering and merging the senses from different ontologies. However, it is not mapped to be equivalent to the DBpedia’s Film concept, in spite of being able to 128 Chapter 7. Experimental Results find the synonym Film for Movie with the extraction techniques in other ontologies. So, when our system, with an extra term, builds: Movie And Dill(starring, T om Cruise) it does not retrieve the desired results. If we had input just Tom Cruise in our system, it would have retrieved results, as the Adapter for DBpedia adds the domain of the property and builds: PREFIX dbpedia:<http://dbpedia.org/ontology/> PREFIX dbres:<http://dbpedia.org/resource/> SELECT DISTINCT ?id0 WHERE { ?id0 a dbpedia:Work . ?id0 dbpedia:starring dbres:Tom_Cruise . } which retrieves all the movies that are starred by Tom Cruise. If the Film concept would have been correctly evaluated as equivalent to dbpedia:Movie (recall that our system disambiguates and merges it correctly), the Adapter would have added an extra constraint that refines further the results (we have checked the results of adding “id0 adbpedia:Film” to the query by hand). Evaluation Conclusions Analyzing the results of the prototype accessing DBpedia, we detected several issues that our current prototype does not address and that affects the answering capabilities of our system, which might constitute the main lines of future work. We detail them in the following, ordered by importance (number of queries affected by the issue): •Multiple keywords must be mapped to just one term: It is usual to have several keywords to be mapped to just one term or resource. For example, keywords Yenisei and river should be mapped together to the resource Yenisei river, or school and type mapped to YAGO’s concept SchoolType. •Need to run the discovering and disambiguation process on DBpedia’s resources: We have to take into account the new landscape of semantic data regarding the disambiguation process and include DBpedia’s 7.1. Evaluating the Semantic Capabilities of QueryGen 129 resources (in fact, we have to be able to include any SPARQL endpoint). This would allow, in addition to the previous point, to detect the resource Yenisei river or Tom Cruise directly in DBpedia. •Lack of expressivity of simplified BACK: The query language we used for the evaluation lacked some needed operators such as aggregation ones, operators for answering yes/no questions, etc. However, as we have seen, the addition of new operators comes at a cost, so this aspect would have to be carefully evaluated. For example, the more than two clause in the query “which countries have places with more than two caves?” implies being able to apply an aggregation operator (in this case, Count) on the intermediate results. •Ambiguous names of properties: There are times that the keyword query itself includes keywords that are too far from their actual meaning to be mapped to it in the disambiguation. For example, country is used in DBpedia to denote the fact that a river flows through a country, while Country is used to denote the concept country. Both of the meanings are part of the considered query, it is quite difficult to infer that flows keyword should be mapped to country. We find another example when considering married vs spouse: DBpedia uses the latter one to express the relationship of being married. We have to advance further in the disambiguation to be able to stretch the semantic gaps. •Not enough data/knowledge to answer the query: DBpedia itself might have not have enough information to be able to answer the posed query. This can happen at schema (properties that are not defined), and at data level (data that is missing). We can see these missed data in, among others, the query of the female astronauts, where their gender data is not stated in DBpedia. •Use of a keyword/property to name its inverse one: Users might unawarely use a keyword to name the inverse property (which might not even exist in the consulted ontologies). This could be tackled by adding inverse operators as we have seen in the query examples (in fact, this issue is subsumed by the lack of expressivity of the selected language, but we think it is important enough to be pointed out). In the query of the caves, as DBpedia only offers location as property (and not isLocated), we would need to apply the inverse of the Some operator to obtain the desired semantics. 130 Chapter 7. Experimental Results •Redundant keywords: The behaviour of current keyword search systems has modified how users express their keyword queries [MMZ09], and it is quite usual to have redundant keywords in the queries, such as an instance and its class (Yenisei and River), or two classes that one subsumes the another one (Place and Cave). •Keyword must be mapped to an operator or to a datatype value rather than to an ontological term: We have to be able to detect when a keyword/set of keywords have to be mapped to a particular operator, or a datatype instance. This would affect directly to the query generation process, as we could force the usage of a particular operator, narrowing the interpretation space. In the example of the caves, our system should have disambiguated two as a number, and therefore only consider the operands that would take a number as operand (this currently can be restricted by giving the corresponding local conditions on the operators). Note that these are current limitations of our prototype that we have detected while accessing DBpedia. However, assuming that the two first points were correctly addressed, we have been able to generate the proper queries with exactly the semantics needed for most of the queries. So, there exists a long road for improvements in our approach, but we think we are on the correct way. 7.2 System Performance In this section, we focus on the performance of the different steps of our system. On the one hand, we measure the performance of the disambiguation process taking into account different depths when comparing ontological contexts. On the other hand, we evaluate the impact of the reduction techniques we apply during the semantic query generation; and, finally, the performance of the generation step along with the semantic filtering (it includes both the local and global checks). 7.2.1 Keyword Disambiguation Performance To test the feasibility of our disambiguation techniques, we have performed a set of tests to evaluate its performance in a detailed and systematic way. The tests were executed on a Sunfire X2200 (2 x AMD Dual Core 2600 MHz, with 8GB RAM). We have used the same set of ontologies as in the previous 7.2. System Performance 131 section (the test collection OWLS-TC4 plus the ontologies dbpedia 3.6.owl, schema.org,People+Pets,Koala,Animals, and WordNet). Thus, a total of 55 ontologies were consulted by our prototype. The input keywords were not selected randomly but based on actual queries proposed by students of different degrees with skills in Computer Science. We considered fifty sets of input keywords to perform the tests, ten for each number of keywords. In Figure 7.1, the results for different sizes of the inputs are shown. Figure 7.1: Keyword disambiguation performance evaluation. As it can be seen, the disambiguation times depend on which depth is considered for matching (i.e., how many levels of parent and children terms in the ontological context). From the experiments, we have seen that using a depth greater than two lead to wrong results. This is due to the fact that the closer you get to the TOP concept in the ontologies, the more false positives appear, as too general subsumer terms are considered. So, a depth of two levels is considered to be semantically optimal. The cached results corresponds to executions on which the extraction procedures had been already performed and stored, as at first, it was the most expensive task. 132 Chapter 7. Experimental Results 7.2.2 Evaluation of Query Generation We turn our focus now on the performance of the query generation step. The tests have been carried out using Pellet14 1.5 as background DL reasoner. They were performed with the same settings, that is, on a Sunfire X2200 (2 x AMD Dual Core 2600 MHz, with 8GB RAM). For the sake’s of experiments repeatability, we selected two well-known ontologies: People+Pets and Koala. They are two popular ontologies of similar size to those used in well-known benchmarks such as the OAEI15. We only show the experimental results obtained with simplified BACK as output query language because most search approaches are based only on conjunctive queries. Nevertheless, we have also performed the experiments with another non-DL languages, and we obtained similar execution times and conclusions. For the experiments, we considered different sample sets of input keywords (selected from the terms of the above ontologies) and measured average values grouped by the number of keywords in the set. As in the evaluation of the performance of the disambiguation process, these inputs were based on actual queries proposed by students of different degrees with skills in Computer Science. The sets were chosen according to the following distribution: 10 sets with a single keyword (5 selecting a role and 5 selecting a concept), 15 sets with two keywords (5 sets where both keywords are roles, 5 sets where both keywords are concepts, and 5 sets where one keyword is a role and the other one is a concept), 20 sets with three keywords (5 with 2 concepts and 1 role, 5 with 1 concept and 2 roles, 5 with 3 concepts, and 5 with 3 roles) and, following the same idea, 25 sets with four keywords and 30 sets with five keywords. Notice that, even though our approach can effectively deal with instances as well, we do not consider sets with instances because the selected ontologies do not have instances (as it happens frequently [WPH06]). We set the maximum number of keywords to 5, as the average number of keywords used in keyword-based search engines “is somewhere between 2 and 3” [MRS08], and thus we can see how our system performs with inputs below and above this average number of keywords. We conducted four experiments: 1) no VTs added, the system works only with the user keywords; 2) one VT added, to try to find a possible missing keyword; 3) two VTs (1+1), is the same situation as 2) with an extra refinement step once the user has selected a candidate for the first VT to be rendered; and 4) two VTs added, to find two possible missing 14http://clarkparsia.com/pellet, last accessed October 3, 2013. 15http://oaei.ontologymatching.org/, last accessed October 3, 2013. 7.2. System Performance 133 keywords at the same time16. We have also considered that the user inputs at least one keyword. The X-axis in Figures 7.2 and 7.3 represents the total keywords considered, i.e., the input and the VTs added by the system. Thus, considering 3 keywords, the results are for 3 user keywords (no VTs), 2 user keywords and 1 VT (one VT), and 1 user keyword and 2 VTs. Figure 7.2 shows the average number of generated queries and the average number of patterns that are presented to the user (notice that the Y-axis is in log scale). Figure 7.2: Performance evaluation: average number of queries and shown patterns. As expected, the number of queries generated rapidly increases with the number of input terms, as the more operands there are, the more queries can be built. Moreover, performing the semantic enrichment leads also to a significant increase in the number of queries because many new interpretations appear. However, the use of query patterns reduces up to an average 92% the options that the user is presented with. Figure 7.2 also shows that, despite generating a higher number of queries, the system compresses the queries more when it has two VTs at once than in the other situations. This may be beneficial to the user, but it might require her/him more time navi16We do not consider adding more than 2 VTs because we do not aim at discovering the user’s intended query when too many keywords were missed in the input. 134 Chapter 7. Experimental Results gating through the candidate keywords for the VTs. The number of queries is lower for two VTs (1+1) as, in the refinement step, the user has fixed a VT and there are less options. Last but not least, no possible interpretation (according the query language) is discarded. Finally, the average times that the generation process takes are shown in Figure 7.3. They include the generation and the semantic filtering time. Being the low they are makes the system suitable to be a responsive frontend (note that we would have to add the times of the sense discovery module, but this module can be use in a standalone mode as well). As it can be seen in Figure 7.3 (notice that the Y-axis is in log scale), the average times for 3 and 4 keywords are similar and really low (recall that the average number of input keywords was between 2 and 3). Figure 7.3: Performance evaluation: processing time of the query generation step. 7.3 Summary of the Chapter In this chapter, we have analyzed QueryGen in a qualitative and a quantitative way. Firstly, adopting a standard that is being used to query DBpedia from keywords, we have evaluated the semantic capabilities of our approach discovering the user’s intended meaning. Secondly, we have evaluated our system working with the DBpedia Adapter, which uses our simplified ver- 7.3. Summary of the Chapter 135 sion of BACK as query language. The results of both evaluations show the potential of our techniques. Moreover, the analysis of the queries that presented problems has raised several issues that, far from being a dead end for the approach, will guide our future work regarding keyword interpretation. In particular, exploiting the knowledge in Linked Data repositories and detecting the operators to be used are specially well positioned to be good lines of improvement. Then, we have moved into performance related aspects of the system. At first, the disambiguation procedure might be seen as quite expensive so as to be used in a system with user interaction. Thanks to the inner structure and the reimplementation of several parts of the original code, we have managed to lower the times while not compromising the quality of the keyword disambiguation. Regarding the query generation, our system presents a good performance. In particular, the inconsistent query filtering is fast enough thanks to the fact that, once we have the original ontology classified, the reasoners can assess the satisfiability of the expressions without reclassifying this ontology. Finally, the impact of the reduction techniques has also been evaluated. The results show that the reduction rates that are managed reduce the possibilities presented to the user dramatically, which is an remarkable achievement as it is done without losing any possible interpretation. 136 Chapter 7. Experimental Results