Ontology Mapping Validation: Dealing with an NP-Complete Problem

Ontology Mapping Validation: Dealing with an NP-Complete Problem

Felipe Serpeloni (Unicamp, Brazil), Regina Moraes (Unicamp, Brazil) and Rodrigo Bonacin (Center for Information Technology Renato Archer and Public Research Centre Henri Tudor, Brazil)
Copyright: © 2011 |Pages: 11
DOI: 10.4018/jwp.2011070101
OnDemand PDF Download:
No Current Special Offers


The use of ontologies and ontology mappings is increasing in companies. Often the same context is modeled in different ontologies. Mapping is necessary to integrate these ontologies; however, in many cases these mappings are incorrect, i.e., they incorrectly link semantic concepts with different meanings. Tools that validate these mappings are necessary to ensure reliable communication between heterogeneous systems. This validation cannot be done in a completely automatic way, because the mappings are based on human interpretation. This work describes a semi-automatic tool that supports this activity, based on graphs that generate instances validated in a semi-automatic process that aims to ensure mapping robustness. This algorithm deals with an NP-Complete problem in order to generate all the instances. This paper presents a first prototype of the tool and the methodology used to validate the instances automatically generated by the tool.
Article Preview


Ontology, in Web Semantics, can be understood as an explicit definition of a context, where contextualization is a simplified view of the represented world, a collection of objects of the domain, concepts, and their relations (Jacob, 2003). Ontologies are used in artificial intelligence, information sharing, communication, interoperability, and for the reuse of knowledge domains.

In the context of Web Semantics, ontology is composed of classes, properties, relations, axioms, and instances. Classes represent the concepts of the domain. Properties correspond to the characteristics whose values differentiate instances of the same class. Relations represent the interaction between concepts or classes. Axioms define always true statements in the domain. Instances are the representations of specific elements of the concepts, which is the actual information (Ehrig & Sure, 2004).

In an algebraic definition, an ontology is a pair O=(S, A), where S is the vocabulary (classes, attributes, relations) and A are the axioms (Kalfoglou & Schorlemmer, 2003).

A major problem in the use of ontologies is the variety of existing ontologies. Many of them represent similar domains or intersections between domains, but they are modeled in different ways. This heterogeneity complicates any process that uses more than one ontology, such as software interoperability and semantic search.

Ontology mappings are constructed to deal with this problem. These mappings are rules that associate the concepts of one ontology with another. The mapping process can be defined as: “given two ontologies A and B, to map an ontology to another means that for any concept in ontology A, try to find a corresponding concept in the ontology B, with the same or similar semantic, and vice versa” (Ehrig & Sure, 2004).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 14: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 13: 2 Issues (2021)
Volume 12: 2 Issues (2020)
Volume 11: 2 Issues (2019)
Volume 10: 2 Issues (2018)
Volume 9: 2 Issues (2017)
Volume 8: 1 Issue (2016)
Volume 7: 2 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing