Finite chase, or alternatively chase termination, is an important condition to ensure the decidability of existential rule languages. In the past few years, a number of rule languages with finite chase have been studied. In this work, we propose a novel approach for classifying the rule languages with finite chase. Using this approach, a family of decidable rule languages, which extend the existing languages with the finite chase property, are naturally defined. We then study the complexity of these languages. Although all of them are tractable for data complexity, we show that their combined complexity can be arbitrarily high. Furthermore, we prove that all the rule languages with finite chase that extend the weakly acyclic language are of the same expressiveness as the weakly acyclic one, while rule languages with higher combined complexity are in general more succinct than those with lower combined complexity.

Many various types of sensors coming from different complex devices collect data from a city. Their underlying data representation follows specific manufacturer specifications that have possibly incomplete descriptions (in ontology) alignments. This paper addresses the problem of determining accurate and complete matching of ontologies given some common descriptions and their pre-determined high level alignments. In this context the problem of ontology matching consists of automatically determining all matching given the latter alignments, and manually verifying the matching results. Especially for applications where it is crucial that ontologies are matched correctly the latter can turn into a very time-consuming task for the user. This paper tackles this challenge and addresses the problem of computing the minimum number of user inputs needed to verify all matchings. We show how to represent this problem as a reasoning problem over a bipartite graph and how to encode it over pseudo Boolean constraints. Experiments show that our approach can be successfully applied to real-world data sets.

Applications of description logics (DLs) such as ontology-based data access (OBDA) require understanding of how to pose database queries over DL knowledge bases. While there have been many studies regarding traditional relational query formalisms such as conjunctive queries and their extensions, little attention has been paid to graph database queries, despite the fact that graph databases have essentially the same structure as knowledge bases. In particular, not much is known about the interplay between DLs and XPath. The latter is a powerful formalism for querying semistructured data: it is in the core of most practical query languages for XML trees, and it is also gaining popularity in theory and practice of graph databases. In this paper we make a step towards coupling knowledge bases and graph databases by studying how to answer powerful XPath-style queries over simple DLs like DL-Lite and EL. We start with adapting the definition of XPath to the DL context, and then proceed to study the complexity of evaluating XPath queries over knowledge bases. Results show that, while query answering is undecidable for the full XPath, by carefully tuning the shape of negation allowed in the queries we can arrive at XPath fragments that have a potential to be used in practice.

Module extraction — the task of computing a (preferably small) fragment M of an ontology T that preserves entailments over a signature S — has found many applications in recent years. Extracting modules of minimal size is, however, computationally hard, and often algorithmically infeasible. Thus, practical techniques are based on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations, however, ensure that M preserves all second-order entailments of T w.r.t. S, which is stronger than is required in many applications, and may lead to large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach not only generalises existing approximations in an elegant way, but it can also be tailored to preserve only specific kinds of entailments, which allows us to extract significantly smaller modules. An evaluation on widely-used ontologies has shown very encouraging results.

Learning mutually-grounded vision-language knowledge is a foundational task for cognitive systems and human-level artificial intelligence. Most of knowledge-learning techniques are focused on single modal representations in a static environment with a fixed set of data. Here, we explore an ecologically more-plausible setting by using a stream of cartoon videos to build vision-language concept hierarchies continuously. This approach is motivated by the literature on cognitive development in early childhood. We present the model of deep concept hierarchy (DCH) that enables the progressive abstraction of concept knowledge in multiple levels. We develop a stochastic method for graph construction, i.e. a graph Monte Carlo algorithm, to search efficiently the huge compositional space of the vision-language concepts. The concept hierarchies are built incrementally and can handle concept drift, allowing for being deployed in lifelong learning environments. Using a series of approximately 200 episodes of educational cartoon videos we demonstrate the emergence and evolution of the concept hierarchies as the video stories unfold. We also present the application of the deep concept hierarchies for context-dependent translation between vision and language, i.e. the transcription of a visual scene into text and the generation of visual imagery from text.

The paper presents an approach for optimizing the evaluation of SPARQL queries over OWL ontologies using SPARQL's OWL Direct Semantics entailment regime. The approach is based on the computation of lower and upper bounds, but we allow for much more expressive queries than related approaches. In order to optimize the evaluation of possible query answers in the upper but not in the lower bound, we present a query extension approach that uses schema knowledge from the queried ontology to extend the query with additional parts. We show that the resulting query is equivalent to the original one and we use the additional parts that are simple to evaluate for restricting the bounds of subqueries of the initial query. In an empirical evaluation we show that the proposed query extension approach can lead to a significant decrease in the query execution time of up to four orders of magnitude.

ABox abduction plays an important role in reasoning over description logic (DL) ontologies. However, it does not work with inconsistent DL ontologies. To tackle this problem while achieving tractability, we generalize ABox abduction from the classical semantics to an inconsistency-tolerant semantics, namely the Intersection ABox Repair (IAR) semantics, and propose the notion of IAR-explanations in inconsistent DL ontologies. We show that computing all minimal IAR-explanations is tractable in data complexity for first-order rewritable ontologies. However, the computational method may still not be practical due to a possibly large number of minimal IAR-explanations. Hence we propose to use preference information to reduce the number of explanations to be computed.

Sorted Neighborhood is an established blocking method for relational databases. It has not been applied on graph-based data models such as the Resource Description Framework (RDF). This poster presents a modular workflow for applying Sorted Neighborhood to RDF. Real-world evaluations demonstrate the workflow's utility against a popular baseline. Entity Resolution (ER) is the abstract problem of identifying Figure 1: A simple instance of ER in an RDF graph pairs of entities across databases that are syntactically disparate but logically equivalent. The problem goes by multiple names in the AI community, examples being record Table 1: Tuples sorted using blocking key values (BKVs) linkage, instance matching, and coreference resolution (Elmagarmid, ID First Name Last Name Zip BKV Ipeirotis, and Verykios 2007).

With the current upward trend in semantically annotated data, ontology-based data access (OBDA) was formulated to tackle the problem of data integration and query answering, where an ontology is formalized as a description logic TBox. In order to meet usability requirements set by users, efforts have been made to equip OBDA system with explanation facilities. One important explanation tool for DL ontologies, referred to as query abduction, can be formalised as abductive reasoning. In particular, given an ontology and an observation (i.e., a query with an answer), an explanation to the observation is a set of facts that together with the ontology can entail the observation. In this paper, we develop a sound and complete algorithm of query abduction for general conjunctive queries in ELH ontologies. This is achieved through ontology approximation and query rewriting. We implemented a prototypical system using the highly optimized Prolog engine XSB. We evaluated our algorithm over university benchmark ontology and our experimental results show that the system is capable of handling query abduction problems for ontology that has approximately 10 millions ABox assertions.

In this paper, I summarize the results of a decade-plus of research and development driven by the vision that human knowledge can be grounded in a small number of prototypical components that can be extended through composition and analogy. These ideas have been embodied in a system called AURA, which has been used to engineer an expressive knowledge base for an intelligent biology textbook. The focus of the current paper is to abstract away from the specifics and, to instead describe the core ideas in such a manner that they can be transferred and applied in different contexts, and to relate those ideas to the ongoing research by others.