dependencyreasoner.java

来自「Semantic Web Ontology Editor」· Java 代码 · 共 904 行 · 第 1/2 页

//The MIT License
//
// Copyright (c) 2004 Mindswap Research Group, University of Maryland, College Park
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

package org.mindswap.swoop.reasoner;

import java.io.Reader;
import java.io.StringReader;
import java.io.StringWriter;
import java.net.URI;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import org.mindswap.swoop.utils.owlapi.CorrectedRDFRenderer;
import org.mindswap.swoop.utils.owlapi.OWLEntityRemover;
import org.semanticweb.owl.impl.model.OWLConnectionImpl;
import org.semanticweb.owl.io.owl_rdf.OWLRDFErrorHandler;
import org.semanticweb.owl.io.owl_rdf.OWLRDFParser;
import org.semanticweb.owl.model.OWLAnd;
import org.semanticweb.owl.model.OWLCardinalityRestriction;
import org.semanticweb.owl.model.OWLClass;
import org.semanticweb.owl.model.OWLClassAxiom;
import org.semanticweb.owl.model.OWLDataValueRestriction;
import org.semanticweb.owl.model.OWLDescription;
import org.semanticweb.owl.model.OWLDisjointClassesAxiom;
import org.semanticweb.owl.model.OWLEntity;
import org.semanticweb.owl.model.OWLException;
import org.semanticweb.owl.model.OWLObjectAllRestriction;
import org.semanticweb.owl.model.OWLObjectProperty;
import org.semanticweb.owl.model.OWLObjectQuantifiedRestriction;
import org.semanticweb.owl.model.OWLObjectSomeRestriction;
import org.semanticweb.owl.model.OWLObjectValueRestriction;
import org.semanticweb.owl.model.OWLOntology;
import org.semanticweb.owl.model.OWLOr;
import org.semanticweb.owl.model.OWLProperty;
import org.semanticweb.owl.model.OWLRestriction;
import org.semanticweb.owl.model.change.ChangeVisitor;
import org.semanticweb.owl.model.change.RemoveClassAxiom;
import org.semanticweb.owl.model.change.RemoveEntity;
import org.semanticweb.owl.util.OWLConnection;
import org.xml.sax.SAXException;

/**
 * @author Aditya
 *
 */
public class DependencyReasoner {

	Set ontologies;
	OWLOntology ontology;
	Set unsat;
	
	boolean preprocessing = false;
	Set allPC; // set of all prop-value chains ending in universal on unsat class
	List propChain; // property-chain
	boolean lastPropAll = false; // if last prop in propChain is due to a allValuesRestriction
	boolean inUnion = false; // used to tag propChains as optional
	HashMap allPCMap;
	public HashMap dependencyMap;
	public List rootClasses, derivedClasses;
	int numSatTests;
	boolean DEBUG = false;
	SwoopRDFSReasoner rdfsReasoner;
	public HashMap childMap = new HashMap();
	
	public DependencyReasoner(Set ontologies, OWLOntology ontology, Set unsat) {
		this.ontologies = ontologies;
		this.ontology = ontology;
		this.unsat = unsat;
		this.rdfsReasoner = new SwoopRDFSReasoner();
		try {
			rdfsReasoner.setOntology(ontology);
		}
		catch (OWLException ex) {
			ex.printStackTrace();
		}
	}
	
	public void findDependencies() {
		
		/* initialize */
		allPCMap = new HashMap();
		dependencyMap = new HashMap();
		rootClasses = new ArrayList();
		derivedClasses = new ArrayList();
		
		/* for each unsat class in the ontology */
		for (Iterator iter = unsat.iterator(); iter.hasNext();) {
			
			OWLClass cla = (OWLClass) iter.next();
			
			/* Pre-processing - Stage 1 */
			preprocessing = true; /*** setting this global var is key ***/
			getAllPropValueChains((OWLClass) cla); // updates global var allPC
			allPCMap.put(cla, allPC);
			
			/* Extract dependencies - Stage 2 */
			preprocessing = false;
			Set dep = getDependency((OWLClass) cla);
			
			/* Post-processing - Stage 3 */
			
			// add final dependency set to hashmap
			dependencyMap.put(cla, dep);
			
			if (dep.size()==1) rootClasses.add(cla);
			else derivedClasses.add(cla);
		}
	}
	
	/*
	 * Mark mutually-dependent derived classes as potential roots
	 */
	public void mutualToRoot() {
		
		// make copy of dependencyMap
		HashMap prevDepMap = new HashMap(dependencyMap);
		
		for (Iterator iter = derivedClasses.iterator(); iter.hasNext();) {
			// get a derived class
			OWLClass derCla = (OWLClass) iter.next();
			// obtain its dependencies
			Set dep = (HashSet) this.dependencyMap.get(derCla);
			dep = this.unfoldSet(dep);
			// iterate and get parents of each dependency
			for (Iterator iter2 = new HashSet(dep).iterator(); iter2.hasNext();) {
				OWLClass parent = (OWLClass) iter2.next();
				if (!parent.equals(derCla)) {
					Set parDep = (HashSet) this.dependencyMap.get(parent);
					parDep = this.unfoldSet(parDep);
					// if parent has dependency equal to current derived class,
					// then both are mutually dependent, and so mark them as roots
					// need to remove them from dependency map
					if (parDep.contains(derCla)) {
						// mutually dependent roots found
						parDep.remove(derCla);
						dependencyMap.put(parent, parDep);
						dep.remove(parent);
						dependencyMap.put(derCla, dep);
					}
				}
			}			
		}
		// finally check dependency map again and move
		// all derived to roots that have only themselves as dependency
		for (Iterator iter = dependencyMap.keySet().iterator(); iter.hasNext();) {
			OWLClass cla = (OWLClass) iter.next();
			Set dep = (HashSet) dependencyMap.get(cla);
			dep = this.unfoldSet(dep);
			if (((dep.size()==1 && dep.contains(cla)) || dep.size()==0) && derivedClasses.contains(cla) && !rootClasses.contains(cla)) {
				// check previous dependency map
				// for each parent, see if now parent has 0 dependencies
				// then make current derived
				Set prevDep = (HashSet) prevDepMap.get(cla);
				prevDep = this.unfoldSet(prevDep);
				boolean stillHasParent = false;
				for (Iterator iter2=prevDep.iterator(); iter2.hasNext();) {
					// get old parent
					OWLClass par = (OWLClass) iter2.next();
					if (!par.equals(cla)) {
						// see its dependencies in new dependencyMap
						Set parDep = (HashSet) this.dependencyMap.get(par);
						parDep = this.unfoldSet(parDep);
						if (parDep.size()>1 || (parDep.size()==1 && !parDep.contains(par))) {
							stillHasParent = true;
							Set newDep = new HashSet();
							if (dependencyMap.get(cla)!=null) newDep = (HashSet) dependencyMap.get(cla);
							newDep.add(par);
							dependencyMap.put(cla, newDep);
						}
					}
				}
				if (!stillHasParent) {
					derivedClasses.remove(cla);
					rootClasses.add(cla);
				}
			}
		}
	}
	
	public void findAllRoots() {
		
		System.out.println("Finding roots using (optimized) brute-force...");
		
		// store all roots here
		Set allRoots = new HashSet();
		// create a copy of original ontology
		OWLOntology copy = this.cloneOntology(ontology);
		// create bkup which gets modified after each iteration
		OWLOntology bkup = this.cloneOntology(copy);
		// also count no. of sat. tests made during this process
		numSatTests = 0;
		OWLClass root = null;
		do {
			// call pruneRoots to find roots in one iteration
			// note: copy, roots gets modified inside pruneRoots
			System.out.println("Testing potential roots: "+rootClasses.size());
			root = pruneRoot(copy, new ArrayList(rootClasses));
			
			if (root==null) {
				// add remaining potential rootClasses to derived
				// also compute its dependency set
				for (Iterator iter = rootClasses.iterator(); iter.hasNext();) {
					OWLClass left = (OWLClass) iter.next();
					Set dep = new HashSet(allRoots);
					dependencyMap.put(left, dep);
				}
				derivedClasses.addAll(rootClasses);
				break;
			}
			else {
				// add roots to allRoots
				allRoots.add(root);
				
				// remove roots from rootClasses before next iteration
				rootClasses.remove(root);
				
				// remove roots from ontology
				System.out.println("Found root:" +getName(root));
				OWLEntity entity = null;
				try {
					entity = bkup.getClass(root.getURI());
//					OWLEntityRemover rem = new OWLEntityRemover(bkup);
//					rem.removeEntity(entity);
					RemoveEntity change = new RemoveEntity(bkup, entity, null);
	        		change.accept((ChangeVisitor) bkup);
				} 
				catch (OWLException e) {
					e.printStackTrace();
				}									
				copy = this.cloneOntology(bkup);
			}
		}
		while (root!=null);
		
		// finally make rootClasses equal to allRoots
		rootClasses = new ArrayList(allRoots);
	}
	
	/*
	 * Detect inferred dependency using ontology approximation technique
	 * Remove causes of contradictions and use reasoner to find hidden
	 * equivalence or subsumption
	 */
	public void infDepOntApprox() {
		
		System.out.println("Finding roots using ontology approximation...");
		try {
//			OWLBuilder builder = new OWLBuilder();
//			builder.createOntology(new URI("test"), new URI("test"));
//			OWLOntology newOnt = builder.getOntology();
//			for (Iterator iter = rootClasses.iterator(); iter.hasNext();) {
//				OWLClass root = (OWLClass) iter.next();
//				AddEntity ae = new AddEntity(newOnt, root, null);
//				ae.accept((ChangeVisitor) newOnt);
//			}
			OWLOntology newOnt = this.cloneOntology(ontology);
			System.out.println("ontology cloned...");
			for (Iterator iter = new HashSet(newOnt.getClasses()).iterator(); iter.hasNext();) {
				OWLClass cla = (OWLClass) iter.next();
				if (!rootClasses.contains(cla)) {
					OWLEntityRemover rem = new OWLEntityRemover(newOnt);
					rem.removeEntity(cla);
				}
			}
			System.out.println("all entities removed...");
		
			// now check disjoint axioms, note classes in disjoints
			// remove axiom and then check equivalence
			Set potRoots = new HashSet();
			for (Iterator iter = new HashSet(newOnt.getClassAxioms()).iterator(); iter.hasNext();) {
				OWLClassAxiom axiom = (OWLClassAxiom) iter.next();
				if (axiom instanceof OWLDisjointClassesAxiom) {
					OWLDisjointClassesAxiom dis = (OWLDisjointClassesAxiom) axiom;
					// check that dis contains atleast one root, otherwise dont remove it
					boolean check = false;
					for (Iterator iter2 = rootClasses.iterator(); iter2.hasNext();) {
						OWLClass root = (OWLClass) iter2.next();
						if (dis.getDisjointClasses().contains(root)) {
							check = true;
							break;
						}
					}
					if (check) {
						potRoots.addAll(dis.getDisjointClasses());
						// remove disjoint axiom
						RemoveClassAxiom rem = new RemoveClassAxiom(newOnt, dis, null);
						rem.accept((ChangeVisitor) newOnt);
					}
				}
			}
			if (!potRoots.isEmpty()) {
				PelletReasoner pellet = new PelletReasoner();
				pellet.setOntology(newOnt, false);
				for (Iterator iter = new HashSet(rootClasses).iterator(); iter.hasNext();) {
					OWLClass root = (OWLClass) iter.next();
					if (!potRoots.contains(root) && pellet.isConsistent(root)) {
						rootClasses.remove(root);
						derivedClasses.add(root);
						Set dep = new HashSet();
						dep.addAll(potRoots);
						dep.add("?");
						dependencyMap.put(root, dep);
					}
				}
			}
//			CorrectedRDFRenderer rdfRend = new CorrectedRDFRenderer();
//			StringWriter st = new StringWriter();
//			rdfRend.renderOntology(newOnt, st);
//			System.out.println(st.toString());
		}
		catch (Exception ex) {
			ex.printStackTrace();
		}
	}
	
	/**
	 * Prune out all actual *root* classes using a brute force algorithm
	 * Hidden Dependencies between roots may exist because of an inferred
	 * subsumption or equivalence with another root 
	 */
	public OWLClass pruneRoot(OWLOntology ont, List potRoots) {
		
		// order pot-roots, remove pot-root and check sat. of remaining
		// if all remaining become sat., then this pot-root is root
		// all the rest are dependent on it
		try {
			// used to dynamically store dependencies on any potential root
			List dependents = new ArrayList();
			
			List copyPotRoots = new ArrayList(potRoots);
			for (int i=0; i<copyPotRoots.size(); i++) {
				
				// test potential root
				OWLClass potRoot = (OWLClass) copyPotRoots.get(i);
				if (DEBUG) System.out.println("Testing: "+getName(potRoot));
				
				// remove pot root from ontology
				OWLOntology beforeRemovingOnt = this.cloneOntology(ont);
				OWLEntity pr = ont.getClass(potRoot.getURI());				
//				OWLEntityRemover remover = new OWLEntityRemover(ont);        		
//				remover.removeEntity(pr);
        		RemoveEntity change = new RemoveEntity(ont, pr, null);
        		change.accept((ChangeVisitor) ont);
				if (DEBUG) System.out.println("Removing: "+getName(potRoot));
				
        		// check if current potRoot is dependent of any previous potRoot
				if (contains(dependents, potRoot)) {
					// its been removed above, now dont check for satisfiability of anything else
					if (DEBUG) System.out.println("Skipping: "+getName(potRoot)+" because its a dependent");
        			potRoots.remove(potRoot);
        			continue;
        		}
				
        		// set reasoner with new ontology (-potRoot) 
        		PelletReasoner reasoner = new PelletReasoner();
        		reasoner.setOntology(ont, false);
        		
        		// check sat. of *remaining* potRoots
        		potRoots.remove(potRoot);
        		boolean allSat = true;
        		for (Iterator iter2 = potRoots.iterator(); iter2.hasNext();) {
					OWLClass rem = (OWLClass) iter2.next();
					if (DEBUG) System.out.print("Satisfiability of: "+getName(rem)+"..");
					boolean sat = reasoner.isConsistent(rem);
					numSatTests++;
					if (DEBUG) System.out.println(String.valueOf(sat));
					if (!sat) {
						// unsatisfiable class found!
						allSat = false;
						break;
					}
					else {
						// dependency on current potRoot, discard in the future
						dependents.add(rem);						
					}
				}
        		
				if (allSat) {					
					// it must be a root, unless..itself is satisfiable i.e. all classes are satisfiable!
					reasoner.setOntology(beforeRemovingOnt, false);
					numSatTests++;
					if (reasoner.isConsistent(potRoot)) {
						// all potRoots satisfiable..return
						if (DEBUG) System.out.println("All pot-roots are satisfiable");
						return null;
					}
					// found root! current potRoot = root
					OWLClass root = potRoot;
					Set roots = new HashSet();
					roots.add(root);
					roots.add("?");
					// add dependency sets of remaining potRoots
					for (Iterator depIter=potRoots.iterator(); depIter.hasNext();) {
						OWLClass derived = (OWLClass) depIter.next();
						// below is not correct! - parents could be any one/more of the classes removed  
						dependencyMap.put(derived, roots);
					}
					// remove from corresponding global sets for future iterations
					rootClasses.removeAll(potRoots);
					rootClasses.removeAll(dependents);
					derivedClasses.addAll(potRoots);
					derivedClasses.addAll(dependents);
					return root;					
				}				
			}
		}
		catch (OWLException ex) {
			ex.printStackTrace();
		}
		return null;
	}
	
	private boolean contains(List list, OWLClass elem) {
		try {
			for (Iterator iter = list.iterator(); iter.hasNext();) {
				OWLClass cla = (OWLClass) iter.next();
				if (cla.getURI().equals(elem.getURI())) return true;
			}
		}
		catch (OWLException ex) {
			ex.printStackTrace();
		}
		return false;
	}
	
	public OWLOntology cloneOntology(OWLOntology source) {
		OWLOntology copy = null;
		try {
			CorrectedRDFRenderer rdfRend = new CorrectedRDFRenderer();