We consider the overlap between reasoning involved in <em>conjunctive query optimization</em> (CQO) and in tableaux-based approaches to reasoning about subsumption in <em>description logics</em> (DLs). In both cases, an underlying graph is created, searched and modified. This process is determined by a given <em>query</em> and <em>database schema</em> in the first case and by a given <em>description</em> and <em>terminology</em> in the second. The opportunities for overlap derive from an abundance of reductions of various schema languages to terminologies for common DL dialects, and from the fact that descriptions can in turn be viewed as queries that compute a single column. <br /><br /> Our main contributions are as follows. We present the design and implementation of a common graph utility that integrates the requirements for both CQO and DL reasoning. We then verify this model by also presenting the design and implementation for two drivers, one that implements a query optimizer for a conjunctive query language extended with descriptions, and one that implements a complete DL reasoner for a feature based DL dialect.

The Web Ontology Language OWL is based on the highly expressive description logic SROIQ, which allows OWL ontology users to employ out-of-the-box reasoners to compute information that is not only explicitly asserted, but entailed by the ontology. Explanation facilities for entailments of OWL ontologies form an essential part of ontology development tools, as they support users in detecting and repairing errors in potentially large and highly complex ontologies, thus helping to ensure ontology quality. Justifications, minimal subsets of an ontology that are sufficient for an entailment to hold, are currently the prevalent form of explanation in OWL ontology development tools. They have been found to significantly reduce the time and effort required to debug erroneous entailments. A large number of entailments, however, have not only one but many justifications, which can make it considerably more challenging for a user to find a suitable repair for the entailment.In this thesis, we investigate the relationships between multiple justifications for both single and multiple entailments, with the goal of exploiting this justificatory structure in order to devise new coping strategies for multiple justifications. We describe various aspects of the justificatory structure of OWL ontologies, such as shared axiom cores and structural similarities. We introduce a model for measuring user effort in the debugging process and propose debugging strategies that exploit the justificatory structure in order to reduce user effort. Finally, an analysis of a large corpus of ontologies from the biomedical domain reveals that OWL ontologies used in practice frequently exhibit a rich justificatory structure.

Description logics are a family of logics that provide formalisms for representing and reasoning about knowledge, based on describing concepts, in a structured and formally well-understood way. They provide the logical foundation for the web ontology language (OWL), which increased awareness of them recently. The most popular techniques for decision procedures for description logics are tableau reasoning methods, which have a long tradition and are well established in automated reasoning. This thesis investigates the possibility of finding a general and optimised blocking mechanism for description logics with the finite model property. It suggests that, while the high branching factor for unrestricted blocking reduces its performance, suitable control of the application of the blocking rule can make the performance acceptable while preserving termination. This claim is supported by experiments that compare the performance of two sample controlled versions of unrestricted blocking. In order to show the generality and power of controlled versions of unrestricted blocking, it is shown how some of the mainstream and most successful standard blocking mechanisms can be approximated as restricted forms of unrestricted blocking. These approximations have the advantage of always being sound compared to their standard versions, which are known to be sound only for some logics. Here, a variation of unrestricted blocking which can ensure strong termination is also introduced. This is done through introducing a new rule that uses the inequality expressions introduced by the blocking rule. The weak termination property of unrestricted blocking is one of its weak points which by this variant of blocking can be addressed. The work presented in this thesis should be of value to people who are working on generalising different aspects of reasoning methods. As blocking plays a critical role in termination of tableau provers, exploration of different variations of unrestricted blocking introduced here may be also of interest for the artificial intelligence researcher.

A reutilização de conhecimento é uma tarefa chave para qualquer sistema computacional. Entretanto, o reúso indiscriminado desse conhecimento pode gerar resultados conflitantes com o objetivo de uso do conhecimento, levando sistemas a se comportarem de maneira imprevisível. Neste trabalho estudamos as consequências do reúso de conhecimento em ontologias baseadas em lógicas de descrição. Focamos principalmente nos problemas que podem ser causados pela fusão de ontologias. Investigamos e comparamos a capacidade das ferramentas de desenvolvimento de ontologias atuais de lidarem com esses problemas e como a teoria se desenvolveu para resolver os mesmos problemas. Realizamos a construção de um arcabouço lógico e de software, organizado na forma de um processo, que tem como objetivo auxiliar o projetista de ontologias a resolver conflitos advindos da fusão. O processo agrupa tarefas descritas normalmente na literatura em separado. Acreditamos que a união dessas abordagens leva a uma melhor solução de conflitos. Durante o desenvolvimento deste trabalho, concentramos nossos esforços principalmente no desenvolvimento de algoritmos para a construção de sub-ontologias maximais, onde os conflitos não ocorram, bem como a ordenação desses conjuntos segundo critérios comuns discutidos na literatura. Tais estratégias foram implementadas em software e testadas utilizando dados gerados automaticamente e dados reais. / Knowledge reuse is a key task during any system development. Nevertheless, careless knowledge reuse may generate conflicting outcomes regarding the system goal, leading such systems to unpredictable behaviour. With that in mind, during this research we studied the consequences of knowledge reuse in ontologies based on description logics. We focused mainly on conflicts arising from ontology merging. We investigated and compared the features developed for this purpose on ontology development tools and how the theory field proposed to deal with the same issues. We developed both a logical and a software framework grouped into a process that aims to help the ontology designer solve conflicts arising from ontology merging. The process groups common tasks that are normally described separately. We believe that the unification of these approaches should result in a better solution for the merging conflicts. We concentrated our efforts during this work on building algorithms for building maximal sub-ontologies where such conflicts are non-existent as well as means for ordering such sets according to a few relevance criteria commonly described at the literature. Such algorithms were implemented and tested against automatically generated and real data.

No description available.

DL-based ontologies have been widely used as knowledge infrastructures in knowledge management systems and on the Semantic Web. The development of efficient, sound and complete reasoning technologies has been a central topic in DL research. Recently, the paradigm shift from professional to novice users, and from standalone and static to inter-linked and dynamic applications raises new challenges: Can users build and evolve ontologies, both static and dynamic, with features provided by expressive DLs, while still enjoying e cient reasoning as in tractable DLs, without worrying too much about the quality (soundness and completeness) of results? To answer these challenges, this thesis investigates the problem of tractable and quality-guaranteed reasoning for ontologies in expressive DLs. The thesis develops syntactic approximation, a consequence-based reasoning procedure with worst-case PTime complexity, theoretically sound and empirically high-recall results, for ontologies constructed in DLs more expressive than any tractable DL. The thesis shows that a set of semantic completeness-guarantee conditions can be identifed to efficiently check if such a procedure is complete. Many ontologies tested in the thesis, including difficult ones for an off-the-shelf reasoner, satisfy such conditions. Furthermore, the thesis presents a stream reasoning mechanism to update reasoning results on dynamic ontologies without complete re-computation. Such a mechanism implements the Delete-and-Re-derive strategy with a truth maintenance system, and can help to reduce unnecessary over-deletion and re-derivation in stream reasoning and to improve its efficiency. As a whole, the thesis develops a worst-case tractable, guaranteed sound, conditionally complete and empirically high-recall reasoning solution for both static and dynamic ontologies in expressive DLs. Some techniques presented in the thesis can also be used to improve the performance and/or completeness of other existing reasoning solutions. The results can further be generalised and extended to support a wider range of knowledge representation formalisms, especially when a consequence-based algorithm is available.

We introduce a family of logics extending the lightweight Description Logic EL, that allows us to define concepts in an approximate way. The main idea is to use a graded membership function m, which for each individual and concept yields a number in the interval [0,1] expressing the degree to which the individual belongs to the concept. Threshold concepts C~t for ~ in {<,<=,>,>=} then collect all the individuals that belong to C with degree ~t. We further study this framework in two particular directions. First, we define a specific graded membership function deg and investigate the complexity of reasoning in the resulting Description Logic tEL(deg) w.r.t. both the empty terminology and acyclic TBoxes. Second, we show how to turn concept similarity measures into membership degree functions. It turns out that under certain conditions such functions are well-defined, and therefore induce a wide range of threshold logics. Last, we present preliminary results on the computational complexity landscape of reasoning in such a big family of threshold logics.

Description logics (DLs) are knowledge representation formalisms with well-understood model-theoretic semantics and computational properties. The DL SROIQ provides the logical underpinning for the semantic web language OWL 2, which is quickly becoming the standard for knowledge representation on the web. A central component of most DL applications is an efficient and scalable reasoner, which provides services such as consistency testing and classification. Despite major advances in DL reasoning algorithms over the last decade, however, ontologies are still encountered in practice that cannot be handled by existing DL reasoners. We present a novel reasoning calculus for the description logic SROIQ which addresses two of the major sources of inefficiency present in the tableau-based reasoning calculi used in state-of-the-art reasoners: unnecessary nondeterminism and unnecessarily large model sizes. Further, we describe a new approach to classification which exploits partial information about the subsumption relation between concept names to reduce both the number of individual subsumption tests performed and the cost of working with large ontologies; our algorithm is applicable to the general problem of deducing a quasi-ordering from a sequence of binary comparisons. We also present techniques for extracting partial information about the subsumption relation from the models generated by constructive DL reasoning methods, such as our hypertableau calculus. Empirical results from a prototypical implementation demonstrate substantial performance improvements compared to existing algorithms and implementations.

We consider the problem of answering conjunctive queries over description logic knowledge bases via query rewriting. Given a conjunctive query Q and a TBox T, we compute a new query Q′ that incorporates the semantic consequences of T such that, for any ABox A, evaluating Q over T and A can be done by evaluating the new query Q′ over A alone. We present RQR—a novel resolution-based rewriting algorithm for the description logic ELHIO¬ that generalizes and extends existing approaches. RQR not only handles a spectrum of logics ranging from DL-Lite_core up to ELHIO¬, but it is worst-case optimal with respect to data complexity for all of these logics; moreover, given the form of the rewritten queries, their evaluation can be delegated to off-the-shelf (deductive) database systems. We use RQR to derive the novel complexity results that conjunctive query answering for ELHIO¬ and DL-Lite+ are, respectively, PTime and NLogSpace complete with respect to data complexity. In order to show the practicality of our approach, we present the results of an empirical evaluation. Our evaluation suggests that RQR, enhanced with various straightforward optimizations, can be successfully used in conjunction with a (deductive) database system in order to answer queries over knowledge bases in practice. Moreover, in spite of being a more general procedure, RQR will often produce significantly smaller rewritings than the standard query rewriting algorithm for the DL-Lite family of logics.

Constructing description logic ontologies is a difficult task that is normally conducted by experts. Recent results show that parts of ontologies can be constructed from description logic interpretations. However, these results assume the interpretations to be free of errors, which may not be the case for real-world data. To provide some mechanism to handle these errors, the notion of confidence from data mining is introduced into description logics, yielding confident general concept inclusions (confident GCIs) of finite interpretations. The main focus of this work is to prove the existence of finite bases of confident GCIs and to describe some of theses bases explicitly.