Seminar Details

MS Seminar

Title	:	Applications of Modularity and Atomic Decomposition of Ontologies
Speaker	:	T. V. Krishna Chaitanya (IITM)
Details	:	Tue, 30 Sep, 2014 3:00 PM @ BSB 361
Abstract:	:	An ontology is a set of axioms that describe a domain in a form that can be understood and processed by a computer program. Ontologies in Semantic Web are written in Description Logic, a fragment of First Order Logic. Axioms consist of a set of terms connected by some operators that describe the relationships between them. If an ontology engineer in a domain wants to use some terms from the other domain, she needs to import the terms along with all the valid relationships between them. Since the number of relationships can be infinite in number, identifying the valid ones among them is impossible. So, we should import a set of axioms, called a module, that can entail all the valid relationships between the set of required terms. A major challenge in this area is to extract such a set of axioms in a faster way. Consider an ontology with n terms whose power set has 2^n sets and hence 2^n modules may exist. There exists a representation of all these modules, called Atomic Decomposition (AD), whose size is linear in the number of axioms. We identify the the module for a given set of terms using this representation. Results show that the proposed algorithm outperforms the naive algorithm and an existing algorithm based on AD. Efficiency has been achieved in terms of preprocessing time, memory needed and the time needed for actual execution of the algorithm. Another challenge is to implement a concurrency control mechanism during collaborative editing of ontologies. Existing approach proved that if a set of terms S is being updated, then it is safe for a mechanism like 2-phase locking to lock a module for S. We extend our earlier solution and use the results proved in it to lock the module faster. Also, as we need to compute a module M for S before locking, we should identify at an earlier state if the axioms of M are already locked by another transaction. Intention locks we propose using Atomic Decomposition help in achieving this. Another challenge is to classify all the terms of an ontology whose complexity depends on the types of operators used in the axioms. It was proved that this is a 2NEXPTIME-complete problem if complex operators are used that are responsible for nondeterminism. Most practical ontologies contain a larger portion of the axioms that are made up of only simple operators. Classifying terms in this portion can be done in polynomial time. We identify the maximum possible such subset of axioms and try to improve classification. We also propose algorithms for efficient consistency checking of ontologies.

© 2016 - All Rights Reserved - Dept of CSE, IIT Madras

Website Credits