From 30b199205f3a16cc92577393ddf9b5d7b36d9dc3 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Tue, 27 Jul 2021 12:52:48 +0100 Subject: Add skeleton for upperbound computation --- .../ox/cs/rsacomb/approximation/Upperbound.scala | 183 +++++++++++++++++++++ 1 file changed, 183 insertions(+) create mode 100644 src/main/scala/uk/ac/ox/cs/rsacomb/approximation/Upperbound.scala (limited to 'src/main/scala') diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/Upperbound.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/Upperbound.scala new file mode 100644 index 0000000..ba26113 --- /dev/null +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/Upperbound.scala @@ -0,0 +1,183 @@ +package uk.ac.ox.cs.rsacomb.approximation + +// import java.io.File + +import org.semanticweb.owlapi.apibinding.OWLManager +import org.semanticweb.owlapi.model.{IRI => _, _} + +// import tech.oxfordsemantic.jrdfox.logic.expression.{Resource, IRI} + +// import scala.collection.mutable.{Set, Map} +// import scalax.collection.Graph +// import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._ +// import scalax.collection.GraphTraversal._ + +import uk.ac.ox.cs.rsacomb.RSAOntology +// import uk.ac.ox.cs.rsacomb.RSAUtil +import uk.ac.ox.cs.rsacomb.ontology.Ontology + +object UpperBound { + + private val manager = OWLManager.createOWLOntologyManager() + private val factory = manager.getOWLDataFactory() + +} + +/** Approximation algorithm that mantains completeness for CQ answering. + * + * The input OWL 2 ontology is assumed to be normalized and the output + * ontology is guaranteed to be in RSA. + * + * The algorithm is performed in three steps: + * 1. the ontology is reduced to ALCHOIQ by discarding any axiom + * that is not in the language; + * 2. the ontology is further reduced to Horn-ALCHOIQ by shifting + * axioms with disjunction on the rhs; + * 3. the ontology is approximated to RSA by manipulating its + * dependency graph. + * + * @see [[uk.ac.ox.cs.rsacomb.converter.Normalizer]] + */ +class UpperBound extends Approximation[RSAOntology] { + + /** Simplify conversion between Java and Scala collections */ + import uk.ac.ox.cs.rsacomb.implicits.JavaCollections._ + + /** Simplify conversion between OWLAPI and RDFox concepts */ + // import uk.ac.ox.cs.rsacomb.implicits.RDFox._ + + /** Main entry point for the approximation algorithm */ + def approximate(ontology: Ontology): RSAOntology = + toRSA( + new Ontology( + ontology.axioms filter inALCHOIQ flatMap toConjuncts, + ontology.datafiles + ) + ) + + /** Discards all axioms outside ALCHOIQ */ + private def inALCHOIQ(axiom: OWLLogicalAxiom): Boolean = + axiom match { + case a: OWLSubClassOfAxiom => { + val sub = a.getSubClass.getNNF + val sup = a.getSuperClass.getNNF + (sub, sup) match { + case (sub: OWLObjectAllValuesFrom, _) => false + case (sub: OWLDataAllValuesFrom, _) => false + case (_, sup: OWLDataAllValuesFrom) => false + case (sub: OWLObjectMinCardinality, _) if sub.getCardinality >= 2 => + false + case (sub: OWLDataMinCardinality, _) if sub.getCardinality >= 2 => + false + case (_, sup: OWLObjectMinCardinality) if sup.getCardinality >= 2 => + false + case (_, sup: OWLDataMinCardinality) if sup.getCardinality >= 2 => + false + case (sub: OWLObjectMaxCardinality, _) => false + case (sub: OWLDataMaxCardinality, _) => false + case (_, sup: OWLObjectMaxCardinality) if sup.getCardinality >= 2 => + false + case (_, sup: OWLDataMaxCardinality) if sup.getCardinality >= 1 => + false + case (_, sup: OWLObjectOneOf) if sup.getIndividuals.length > 2 => + false + case (sub: OWLObjectHasSelf, _) => false + case (_, sup: OWLObjectHasSelf) => false + case _ => true + } + } + case a: OWLTransitiveObjectPropertyAxiom => false + case a: OWLReflexiveObjectPropertyAxiom => false + case a: OWLSubPropertyChainOfAxiom => false + case a: OWLAsymmetricObjectPropertyAxiom => false + case a => true + } + + /** Turn disjuncts into conjuncts + * + * This is a very naive way of getting rid of disjunction preserving + * completeness of CQ answering. + * + * @todo implement a choice function that decides which disjunct to + * keep instead of keeping all of them. Note that PAGOdA is currently + * doing something similar. + */ + private def toConjuncts(axiom: OWLLogicalAxiom): List[OWLLogicalAxiom] = + axiom match { + case a: OWLSubClassOfAxiom => { + val sub = a.getSubClass.getNNF + val sup = a.getSuperClass.getNNF + sup match { + case sup: OWLObjectUnionOf => + sup.asDisjunctSet.map( + UpperBound.factory.getOWLSubClassOfAxiom(sub, _) + ) + case _ => List(axiom) + } + } + case _ => List(axiom) + } + + // /** Approximate a Horn-ALCHOIQ ontology to RSA + // * + // * This is done by gathering those axioms that prevent the ontology + // * dependency graph from being tree-shaped, and removing them. + // * + // * @param ontology the set of axioms to approximate. + // * @return the approximated RSA ontology + // */ + // private def toRSA(ontology: Ontology): RSAOntology = { + // /* Compute the dependency graph for the ontology */ + // val (graph, nodemap) = ontology.dependencyGraph + + // /* Define node colors for the graph visit */ + // sealed trait NodeColor + // case object Unvisited extends NodeColor + // case object Visited extends NodeColor + // case object ToDelete extends NodeColor + + // /* Keep track of node colors during graph visit */ + // var color = Map.from[Resource, NodeColor]( + // graph.nodes.toOuter.map(k => (k, Unvisited)) + // ) + + // for { + // component <- graph.componentTraverser().map(_ to Graph) + // edge <- component + // .outerEdgeTraverser(component.nodes.head) + // .withKind(BreadthFirst) + // } yield { + // val source = edge._1 + // val target = edge._2 + // color(source) match { + // case Unvisited | Visited => { + // color(target) match { + // case Unvisited => + // color(source) = Visited; + // color(target) = Visited + // case Visited => + // color(source) = ToDelete + // case ToDelete => + // color(source) = Visited + // } + // } + // case ToDelete => + // } + // } + + // val toDelete = color.collect { case (resource: IRI, ToDelete) => + // nodemap(resource.getIRI) + // }.toList + + // /* Remove axioms from approximated ontology */ + // RSAOntology(ontology.axioms diff toDelete, ontology.datafiles) + // } + + // val edges1 = Seq('A ~> 'B, 'B ~> 'C, 'C ~> 'D, 'D ~> 'H, 'H ~> + // 'G, 'G ~> 'F, 'E ~> 'A, 'E ~> 'F, 'B ~> 'E, 'F ~> 'G, 'B ~> 'F, + // 'C ~> 'G, 'D ~> 'C, 'H ~> 'D) + // val edges2 = Seq('I ~> 'M, 'I ~> 'L, 'L ~> 'N, 'M ~> 'N) + // val edges3 = Seq('P ~> 'O) + // val graph = Graph.from(edges = edges1 ++ edges2 ++ edges3) + // +} -- cgit v1.2.3