Recently, large amounts of data are being published using Semantic Web standards. Simultaneously, there has been a steady rise in links between objects from multiple sources. However, the ontologies behind these sources have remained largely disconnected, thereby challenging the interoperability goal of the Semantic Web. We address this problem by automatically finding alignments between concepts from multiple linked data sources. Instead of only considering the existing concepts in each ontology, we hypothesize new composite concepts, defined using conjunctions and disjunctions of (RDF) types and value restrictions, and generate alignments between them. In addition, our techniques provide a novel method for curating the linked data web by pointing to likely incorrect or missing assertions. Our approach provides a deeper understanding of the relationships between linked data sources and increases the interoperability among previously disconnected ontologies.

When answering queries in the presence of ontologies, adopting the closed world assumption for some predicates easily results in intractability. We analyze this situation on the level of individual ontologies formulated in the description logics DL-Lite and EL and show that in all cases where answering CQs with (open and) closed predicates is tractable, it coincides with answering CQs with all predicates assumed open. In this sense, CQ answering with closed predicates in inherently intractable. Our analysis also yields a dichotomy between AC0 and coNP for CQ answering in DL-Lite and a dichotomy between PTime and coNP for EL. Interestingly, the situation is less dramatic in the more expressive description logic ELI, where we find ontologies for which CQ answering is in PTime, but does not coincide with CQ answering where all predicates are open.

Rewriting-based approaches for answering queries over an OWL 2 DL ontology have so far been developed mainly for Horn fragments of OWL 2 DL. In this paper, we study the possibilities of answering queries over non-Horn ontologies using datalog rewritings. We prove that this is impossible in general even for very simple ontology languages, and even if PTIME = NP. Furthermore, we present a resolution-based procedure for SHI ontologies that, in case it terminates, produces a datalog rewriting of the ontology. We also show that our procedure necessarily terminates on DL-Lite Bool H,+ ontologies — an extension of OWL 2 QL with transitive roles and Boolean connectives.

The Distributed Ontology Language DOL, currently being standardized as ISO WD 17347 within the OntoIOp (Ontology Integration and Interoperability) activity of ISO/TC 37, provides a unified framework for (1) ontologies formalized in heterogeneous logics, (2) modular ontologies, (3) links between ontologies, and (4) ontology annotation. A DOL ontology consists of modules formalized in languages such as OWL or Common Logic, serialized in the existing syntaxes of these languages. On top, DOL’s meta level allows for expressing heterogeneous ontologies and links between ontologies, including (heterogeneous) imports and alignments, conservative extensions, and theory interpretations. We present the abstract syntax of these meta-level constructs, with three alternative semantics: direct, translational, and collapsed semantics.

A robust system for ontology-based data access should provide meaningful answers to queries even when the data conflicts with the ontology. This can be accomplished by adopting an inconsistency-tolerant semantics, with the consistent query answering (CQA) semantics being the most prominent example. Unfortunately, query answering under the CQA semantics has been shown to be computationally intractable, even when extremely simple ontology languages are considered. In this paper, we address this problem by proposing two new families of inconsistency-tolerant semantics which approximate the CQA semantics from above and from below and converge to it in the limit. We study the data complexity of conjunctive query answering under these new semantics, and show a general tractability result for all known first-order rewritable ontology languages. We also analyze the combined complexity of query answering for ontology languages of the DL-Lite family.

The study of preferences has a long tradition in many disciplines, but it has only relatively recently entered the realm of data management through their application in answering queries to relational databases. The current revolution in data availability through the Web and, perhaps most importantly in the last few years, social media sites and applications, puts ontology languages at the forefront of data and information management technologies. In this paper, we propose the first (to our knowledge) integration of ontology languages with preferences as in relational databases by developing PrefDatalog+/-, an extension of the Datalog+/- family of languages with preference management formalisms closely related to those previously studied for relational databases. We focus on two kinds of answers to queries that are relevant to this setting, skyline and k-rank (a generalization of top-k queries), and develop algorithms for computing these answers to both DAQs (disjunctions of atomic queries) and CQs (conjunctive queries). We show that DAQ answering in PrefDatalog+/- can be done in polynomial time in the data complexity, as in relational databases, as long as query answering can also be done in polynomial time (in the data complexity) in the underlying classical ontology.

Ontology Matching aims to find a set of semantic correspondences, called an alignment, between related ontologies. In recent years, there has been a growing interest in efficient and effective matching methods for large ontologies. However, most of the alignments produced for large ontologies are logically incoherent. It was only recently that the use of repair techniques to improve the quality of ontology alignments has been explored. In this paper we present a novel technique for detecting incoherent concepts based on ontology modularization, and a new repair algorithm that minimizes the incoherence of the resulting alignment and the number of matches removed from the input alignment. An implementation was done as part of a lightweight version of AgreementMaker system, a successful ontology matching platform, and evaluated using a set of four benchmark biomedical ontology matching tasks. Our results show that our implementation is efficient and produces better alignments with respect to their coherence and f-measure than the state of the art repairing tools. They also show that our implementation is a better alternative for producing coherent silver standard alignments.

In this paper, we show how to model the matching problem as a problem of joint inference. In opposite to existing ap-proaches, we distinguish between the layer of labels and the layer of concepts and properties. Entities from both layers appear as first class citizens in our model. We present an ex-ample and explain the benefits of our approach. Moreover, we argue that our approach can be extended to generate cor-respondences involving complex concept descriptions.

We consider the problem of building relational probabilistic models with an underlying ontology that defines the classes and properties used in the model. Properties in the ontology form random variables when applied to individuals. When an individual is not in the domain of a property, the corresponding random variable is undefined. If we are uncertain about the types of individuals, we may be uncertain about whether random variables are defined. We discuss how to extend a recent result on reasoning with potentially undefined random variables to the relational case. Object properties may have classes of individuals as their ranges, giving rise to random variables whose ranges vary with populations. We identify and discuss some of the issues that arise when constructing relational probabilistic models using the vocabulary and constraints from an ontology, and we outline possible solutions to certain problems.

The Web is currently shifting from data on linked Web pages towards less interlinked data in social networks on the Web. Therefore, rather than being based on the link structure between Web pages, the ranking of search results needs to be based on something new. We believe that it can be based on user preferences and ontological background knowledge, as a means to personalized access to information. There are many approaches to preference representation and reasoning in the literature. The most prominent qualitative ones are perhaps CP-nets. Their clear graphical structure unifies an easy representation of preferences with nice properties when computing the best outcome. In this paper, we introduce ontological CP-nets, where the knowledge domain has an ontological structure, i.e., the values of the variables are constrained relative to an underlying ontology. We show how the computation of Pareto optimal outcomes for such ontological CP-nets can be reduced to the solution of constraint satisfaction problems. We also provide several complexity and tractability results.