ABSTRACT. For the first time since the emergence of the Web, structured data is playing a key role in search engines and is therefore being collected via a concerted effort. Much of this data is being extracted from the Web, which contains vast quantities of structured data on a variety of domains, such as hobbies, products and reference data. Moreover, the Web provides a platform that encourages publishing more data sets from governments and other public organizations. The Web also supports new data management opportunities, such as effective crisis response, data journalism and crowd-sourcing data sets.

I will describe some of the efforts we are conducting at Google to collect structured data, filter the high-quality content, and serve it to our users. These efforts include providing Google Fusion Tables, a service for easily ingesting, visualizing and integrating data, mining the Web for high-quality HTML tables, and contributing these data assets to Google's other services. The talk will touch at various points on the role of ontologies in managing all this structured data and the new kind of ontological tools we may require.

ABSTRACT. An increasing number of applications are relying on RDF format for storing data, on OWL ontologies to enhance the data with semantics, and SPARQL for accessing the data. SPARQL, however, is not targeted towards end-users, and suitable query interfaces are needed. Faceted search is a prominent approach for end-user data access, and in this paper we discuss how this approach can be applied to RDF and OWL. We implemented our ideas in a proof of concept prototype, SemFacet, and a preliminary evaluation of the system is encouraging.

ABSTRACT. We consider the consequences on basic reasoning problems of allowing negated primitive concepts on left-hand-sides of inclusion dependencies in the description logic dialect CFDnc. Although earlier work has shown that this makes CQ answering coNP-complete, we show that TBox consistency and concept satisfiability remain in PTIME. We also show that knowledge base consistency and instance retrieval remain in PTIME if a CFDnc knowledge base satisfies a number of additional conditions, and that failing any one of these conditions will alone lead to intractability for these problems.

ABSTRACT. Many applications nowadays expose data in semantic formats such as RDF and OWL. The standard query language to access such data is SPARQL. Writing SPARQL requires requires training and it is not feasible for unexperienced users. In this paper we present OptiqueVQS, a query formulation interface that addresses this problem and allows to construct conjunctive SPARQL queries in an intuitive way. Our approach relies on a graph based representation paradigm to visualise queries. Users can construct queries step by step and OptiqueVQS provides them with suggestions on how to continue query construction. These suggestions depend on specific parts of the constructed query and automatically computed by reasoning over the ontology underlying the interface. OptiqueVQS has two types of suggestions which are based on data and object properties. Preliminary user studies of the interface with geologists gave us encouraging results.

ABSTRACT. In this paper we present an in progress prototype for the graphical visualization and management of mappings for Ontology-based data access (OBDA). The tool supports the specification of expressive mappings linking a DL-Lite ontology to a relational source database, and allows the designer to graphically navigate them, according to various possible views, modify their textual representation, and validate their syntactic correctness. Furthermore, it gives preliminary support to the semantic analysis of the mappings, which aims to identify anomalies in the representation, like the specification of mapping queries that cannot return answers without contradicting the ontology. Such functionalities are currently being enhanced in our ongoing development of the tool.

ABSTRACT. In this paper we present Graphol, a novel language for the diagrammatic representation of Description Logic (DL) ontologies. Graphol is designed with the aim of offering a completely visual representation to the users (notably, no formulae need to be used in our diagrams), thus helping the understanding of people not skilled in logic. At the same time, it provides designers with simple mechanisms for ontology editing, which free them from having to write down complex textual syntax. Graphol offers most of the classical constructs used in DLs, and allows for specifying expressive ontologies. It is also suitably extended to capture the same expressivity of OWL 2. In this respect, we developed a basic tool to translate Graphol ontologies realized with the yEd graph editor into OWL 2 encoding. User evaluation tests, conducted with designers skilled in conceptual or ontology modeling and users without specific logic background, demonstrate the effectiveness of our language for both visualization and editing of ontologies.

ABSTRACT. Ontology-based data access (OBDA) is a new paradigm aiming at accessing and managing data by means of an ontology, i.e., a conceptual representation of the domain of interest in the underlying information system. In the last years, this new paradigm has been used for providing users with suitable mechanisms for querying the data residing at the information system sources. Most of the research has been concentrating on making query answering efficient. However, query answering is not the only service that an OBDA system must provide. Another crucial service is consistency checking. Current approaches to this problem involves executing expensive queries at run-time. In this paper we address a fundamental problem for OBDA system: given an OBDA specification, can we avoid the consistency check on the whole OBDA system (global consistency check), and rely instead on the constraint checking carried out by the DBMS on the data source (local consistency checking)? We present algorithms and complexity analysis for this problem, showing that it can be solved efficiently for a class of OBDA systems that is very relevant in practice.

ABSTRACT. Mapping relational data to RDF is an important task for the development of the Semantic Web. To this end, the W3C has recently released a Recommendation for the so-called direct mapping of relational data to RDF. In this work, we propose an enrichment of the direct mapping to make it more faithful by transferring also semantic information present in the relational schema from the relational world to the RDF world. For this purpose we enrich DL-Lite_{RDFS} with expressive identification constraints to capture functional dependencies and define an RDF Normal Form, which precisely captures the classical Boyce-Codd Normal Form of relational schemas.

ABSTRACT. In previous work it has been shown how a SROIQ ontology O can be `repaired' for an RL system ans---that is, how we can compute a set of axioms R that is independent from the data and such that ans that is generally incomplete for O becomes complete for all SPARQL queries when used with O and R. However, the initial implementation and experiments were very preliminary and hence it is currently unclear whether the approach can be applied to large and complex ontologies. Moreover, the approach could not support non-SPARQL CQs. In the current paper we thoroughly investigate repairing as an approach to scalable (and complete) ontology-based data access. First, we present several non-trivial optimisations to the first prototype. Second, we show how (arbitrary) conjunctive queries can be supported by integrating well-known query rewriting techniques with RL systems via repairing. Third, we perform an extensive experimental evaluation obtaining encouraging results. In more detail, our results show that we can compute repairs even for very large real-world ontologies in a reasonable amount of time, that the performance overhead introduced by repairing is negligible in small to medium sized ontologies and noticeable but manageable in large and complex one, and that our approach to handling non-SPARQL CQs can very efficiently compute the correct answers for real-world challenging TBoxes.

ABSTRACT. Competency Questions (CQs) play an important role in the ontology development life-cycle, as they represent the ontology requirements. Although the main methodologies use them, there is room for improvement in the current practice of ontology engineering. One of the main problems is the lack of tools to check if CQs defined in OWL, are being fulfilled by an ontology, preferably in an automated way. Moreover, requirement (or CQ) traceability is rarely explored. Recently there has been a trend on checking CQs against ontologies using RDF and SPARQL. Naturally, this language, being created for Semantic Networks, is inadequate to check the fulfillment of OWL CQs. In this paper, we introduce a semi-automatic, full-fledged method to develop ontologies iteratively, using CQs as requirements. It presents many novelties: a tracer to monitor the relations among CQs and the OWL code; an NLP component that translates CQs in natural language into OWL queries; a logic checker that confirms whether CQs are satisfied or not; a generator of new CQs, which comes into play when the CQ being dealt is not satisfied yet; and an axiom generator that suggests to the user new axioms to be included in the ontology.

ABSTRACT. In this paper we introduce the notion of an ontology excerpt as being a fixed-size subset of an ontology that preserves as much as possible of the meaning of the terms in a given signature as described in the ontology. We consider different extraction techniques for ontology excerpts based on methods from information retrieval. To evaluate these techniques we measure the degree of incompleteness of the resulting excerpts using the notion of logical difference. As such a measure we use the number of concept names from an input signature that witness the logical concept difference between the ontology and its excerpt. We provide an experimental evaluation of the extraction techniques using the biomedicalal ontology SNOMED CT.

ABSTRACT. We investigate conjunctive query inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query entailment of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to EXPTIME and 2EXPTIME.

ABSTRACT. We present a new method for detecting logical differences between EL-terminologies extended with role inclusions, domain and range restrictions of roles using a hypergraph representation of ontologies. In this paper we only consider differences that are given by pairs consisting of a conjunctive query together with an ABox formulated over a signature of interest. We define a simulation notion between such hypergraph representations and we show that its existence coincides with the absence of a logical difference. To demonstrate the practical applicability of our approach, we evaluate the performance of our prototype implementation on large ontologies.

ABSTRACT. We present a method to compute uniform interpolants of ALC ontologies with ABoxes. Uniform interpolants are restricted views of ontologies that only use a specified set of symbols, but share all entailments in that signature with the original ontology. This way, it allows to select or remove information from an ontology based on a signature, which has applications in privacy, ontology analysis and ontology reuse. In turns out, that in general, uniform interpolants of ALC ontologies with ABoxes may require the use of disjunctions in the ABox or nominals. Our evaluation of the method suggests however, that in most practical cases uniform interpolants can be represented as a classical ALC ontology.

ABSTRACT. The formal definition of abduction asks what needs to be added to a knowledge base to enable an observation to be entailed. TBox abduction in description logics (DLs) asks what TBox axioms need to be added to a DL knowledge base to allow a TBox axiom to be entailed. We describe a sound and complete algorithm, based on the standard DL tableau, that takes a TBox abduction problem in ALC and generates solutions in a restricted language. We then show how this algorithm can be enhanced to deal with a broader range of problems in ALC.

ABSTRACT. We present a method for generating understandable explanations in description logic. Such explanations could be of potential use for e.g. engineers, doctors, and users of the semantic web. Users commonly need to understand why a logical statement follows from a set of hypotheses. Then automatically generated explanations that are easily understandable could be of help. A proof system for description logic that can be used for generating understandable explanations is proposed. Similar systems have been proposed for propositional logic and first-order logic.

ABSTRACT.  

This paper investigates a new approach for computing ap- proximate answers of ontological queries based on a notion of an edit distance of a given individual w.r.t. a given query. Such a distance is computed by counting the number of elementary operations needed to be applied to an ABox in order to make a given individual a correct an- swer to a given query. The considered elementary operations are adding to or removing from an ABox, assertions of the form of an atomic con- cept (or its negation) and/or atomic roles. We describe some preliminary results regarding the problem of computing such approximate answers in the context of the Open World Assumption (OWA) and the Generalized Closed World Assumption (GCWA) approaches.

ABSTRACT. Ontology repair remains one of the main bottlenecks for the development of ontologies for practical use. Many automated methods have been developed for suggesting potential repairs, but ultimately human intervention is required for selecting the adequate one, and the human expert might be overwhelmed by the amount of information delivered to her. We propose a decomposition of ontologies into smaller components that can be repaired in parallel. We show the utility of our approach for ontology repair, provide algorithms for computing this decomposition through standard reasoning, and study the complexity of several associated problems.

ABSTRACT. We consider the problem of consistent query answering under existential rules. More precisely, we aim at answering conjunctive queries under ontologies expressed by existential rules in the presence of negative constraints. These constraints may make the knowledge base inconsistent. Semantics have already been defined in order to keep meaningful answers even in the presence of such inconsistencies. However, it is known that even under very simple ontologies, consistent query answering is intractable under some reasonable semantics. The aim of this paper is to study more precisely where the complexity comes from, and to provide theoretical tools that make the complexity of the problem decrease in reasonable settings. To that purpose, we introduce the notion of archipelago and adapt the notion of exchangeable literals that has been introduced in the setting of conjunctive query answering with atomic negation. We exploit them to derive tractability results, first in the absence of existential rules then when simple (but nonetheless expressive) ontologies are used.

ABSTRACT. We describe a hybrid approach to conjunctive query answering over OWL 2 ontologies that combines a datalog reasoner with a fully-fledged OWL 2 reasoner in order to provide scalable “pay as you go” performance. Our approach delegates the bulk of the computation to the highly scalable datalog engine and resorts to expensive OWL 2 reasoning only as necessary to fully answer the query. We have implemented a prototype system that uses RDFox as a datalog reasoner, and HermiT as an OWL 2 reasoner. Our evaluation over both benchmark and realistic ontologies and datasets suggests the feasibility of our approach.

ABSTRACT. Query answering over SROIQ TBoxes is an important reasoning task for many modern applications. Unfortunately, due to its high computational complexity, SROIQ reasoners are still not able to cope with datasets containing billions of data. Consequently, application developers often employ provably scalable systems which only support a fragment of SROIQ and which are, hence, most likely incomplete for the given input. However, this notion of completeness is too coarse since it implies that there exists \emph{some} query and \emph{some} dataset for which these systems would miss answers. Nevertheless, there might still be a large number of user queries for which they can compute all the right answers even over SROIQ TBoxes. In the current paper, we investigate whether, given a (ground) query Q over a SROIQ TBox T and a system ans, it is possible to identify in an efficient way if ans is complete for Q,T and every dataset. We give sufficient conditions for (in)completeness and present a hybrid query answering algorithm which uses ans when it is complete, otherwise it falls back to a fully-fledged SROIQ reasoner. However, even in the latter case, our algorithm still exploits ans as much as possible in order to reduce the search space of the SROIQ reasoner. Finally, we have implemented our approach using a concrete system ans and SROIQ reasoner obtaining encouraging results.

ABSTRACT. Absorption is a well-known and very important optimisation technique that is widely used to reduce non-determinism for tableau-based reasoning systems. In this paper, we present the partial absorption algorithm which allows for absorbing parts of concepts of very expressive Description Logics and, thus, further reduces non-determinism. In addition, we present several extensions of the basic algorithm, which, for example, can be used to improve the handling of datatypes. The described absorption techniques are used in the reasoning system Konclude and they are essential for Konclude's performance.

ABSTRACT. We consider the setting of graph-structured data that evolve as a result of operations carried out by users or applications. We rely on a simple yet powerful action language in which actions are finite sequences of insertions and deletions of nodes and labels, and on the use of Description Logics for describing integrity constraints and (partial) states of the data. For this setting, we study variants of planning problems, which range from ensuring the satisfaction of a given set of integrity constraints after executing a given sequence of actions, to deciding the existence of a sequence of actions that takes the data to an (un)desirable state, starting either from a specific data instance or from an incomplete description of it. For these problems we establish (un)decidability results and study the computational complexity, also considering various restrictions.