Goto

Collaborating Authors

Borgwardt

AAAI Conferences

Context-aware systems use data collected at runtime to recognize certain predefined situations and trigger adaptations. This can be implemented using ontology-based data access (OBDA), which augments classical query answering in databases by adopting the open-world assumption and including domain knowledge provided by an ontology.


Bienvenu

AAAI Conferences

While query answering in the presence of description logic (DL) ontologies is a well-studied problem, questions of static analysis such as query containment and query optimization have received less attention. In this paper, we study a rather general version of query containment that, unlike the classical version, cannot be reduced to query answering. First, we allow a restriction to be placed on the vocabulary used in the instance data, which can result in shorter equivalent queries; and second, we allow each query its own ontology rather than assuming a single ontology for both queries, which is crucial in applications to versioning and modularity. We also study global minimization of queries in the presence of DL ontologies, which is more subtle than for classical databases as minimal queries need not be isomorphic.


On the Complexity of Learning Description Logic Ontologies

arXiv.org Artificial Intelligence

Ontologies are a popular way of representing domain knowledge, in particular, knowledge in domains related to life sciences. (Semi-)automating the process of building an ontology has attracted researchers from different communities into a field called "Ontology Learning". We provide a formal specification of the exact and the probably approximately correct learning models from computational learning theory. Then, we recall from the literature complexity results for learning lightweight description logic (DL) ontologies in these models. Finally, we highlight other approaches proposed in the literature for learning DL ontologies.


Query Abduction for ELH Ontologies

AAAI Conferences

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.


On the Complexity of Consistent Query Answering in the Presence of Simple Ontologies

AAAI Conferences

Consistent query answering is a standard approach for producing meaningful query answers when data is inconsistent. Recent work on consistent query answering in the presence of ontologies has shown this problem to be intractable in data complexity even for ontologies expressed in lightweight description logics. In order to better understand the source of this intractability, we investigate the complexity of consistent query answering for simple ontologies consisting only of class subsumption and class disjointness axioms. We show that for conjunctive queries with at most one quantified variable, the problem is first-order expressible; for queries with at most two quantified variables, the problem has polynomial data complexity but may not be first-order expressible; and for three quantified variables, the problem may become co-NP-hard in data complexity. For queries having at most two quantified variables, we further identify a necessary and sufficient condition for first-order expressibility. In order to be able to handle arbitrary conjunctive queries, we propose a novel inconsistency-tolerant semantics and show that under this semantics, first-order expressibility is always guaranteed. We conclude by extending our positive results to DL-Lite ontologies without inverse.