Rewriting-Based Instance Retrieval for Negated Concepts in Description Logic Ontologies
Instance retrieval computes all instances of a given concept in a consistent description logic (DL) ontology. Although it is a popular task for ontology reasoning, there is no scalable method for instance retrieval for negated concepts by now. This paper
- PDF / 298,760 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 163 Views
Guangdong University of Foreign Studies, Guangzhou 510006, China [email protected] 2 The University of Aberdeen, Aberdeen AB24 3UE, UK
Abstract. Instance retrieval computes all instances of a given concept in a consistent description logic (DL) ontology. Although it is a popular task for ontology reasoning, there is no scalable method for instance retrieval for negated concepts by now. This paper studies a new approach to instance retrieval for negated concepts based on query rewriting. A class of DL ontologies called the inconsistency-based first-order rewritable (IFO-rewritable) class is identified. This class guarantees that instance retrieval for an atomic negation can be reduced to answering a disjunction of conjunctive queries (CQs) over the ABox. The IFOrewritable class is more expressive than the first-order rewritable class which guarantees that answering a CQ is reducible to answering a disjunction of CQs over the ABox regardless of the TBox. Two sufficient conditions are proposed to detect IFO-rewritable ontologies that are not first-order rewritable. A rewriting-based method for retrieving instances of a negated concept is proposed for IFO-rewritable ontologies. Preliminary experimental results on retrieving instances of all atomic negations show that this method is significantly more efficient than existing methods implemented in state-of-the-art DL systems.
1
Introduction
Description logics (DLs) [2] are popular knowledge representation languages underpinning the Web Ontology Language (OWL). A DL ontology consists of a TBox and an ABox, where the TBox describes relations between concepts and roles, and the ABox describes instances of concepts and roles. DLs enable a number of tasks for ontology reasoning based on the classical first-order semantics. Among these tasks, instance retrieval is a popular one which computes all individuals in a consistent DL ontology that are instances of a given concept. Most studies on instance retrieval focus on atomic concepts, namely concept names. It is well-known that instance retrieval for atomic concepts is tractable for those DLs that underpin the three profiles QL, EL and RL of OWL 2, the newest version of OWL. There have also been optimization and approximation techniques proposed for instance retrieval in expressive DLs [13,17,21]. However, to the best of our knowledge, there is seldom any dedicated study on instance retrieval for negated concepts. A negated concept is of the form ¬C where C is c Springer International Publishing Switzerland 2015 M. Arenas et al. (Eds.): ISWC 2015, Part I, LNCS 9366, pp. 339–355, 2015. DOI: 10.1007/978-3-319-25007-6 20
340
J. Du and J.Z. Pan
a DL concept without the negation symbol ¬. In the reality, it is often required to compute instances of a negated concept. For example, one may often raise questions like the following ones upon a DL ontology describing people in universities: Who is not an undergraduate? Who does not have a friend who is a professor? Who does not get a PhD degree from a Chinese university? According to the s
Data Loading...
