From e932527e33b6f4c1634995224188b26d870d92b2 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Mon, 31 May 2021 15:06:47 +0100 Subject: Add scafolding for generic approximation support --- .../scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala | 305 +++++++++++---------- .../cs/rsacomb/approximation/approximation.scala | 16 ++ .../ox/cs/rsacomb/approximation/lowerbound.scala | 207 ++++++++++++++ 3 files changed, 385 insertions(+), 143 deletions(-) create mode 100644 src/main/scala/uk/ac/ox/cs/rsacomb/approximation/approximation.scala create mode 100644 src/main/scala/uk/ac/ox/cs/rsacomb/approximation/lowerbound.scala (limited to 'src') diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala index c7b3bf0..e048c28 100644 --- a/src/main/scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala @@ -64,6 +64,104 @@ import uk.ac.ox.cs.rsacomb.sparql._ import uk.ac.ox.cs.rsacomb.util.{RDFoxUtil, RSA} import uk.ac.ox.cs.rsacomb.util.Logger +object RSAUtil { + + implicit def axiomsToOntology(axioms: Seq[OWLAxiom]) = { + val manager = OWLManager.createOWLOntologyManager() + manager.createOntology(axioms.asJava) + } + + /** Compute the RSA dependency graph for a set of axioms + * + * @return a tuple containing the dependency graph and a map between + * the newly introduced constants and the corresponding input axioms. + * + * @note no check on the ontology language is performed since the + * construction of the dependency graph is computed regardless. The + * input axioms are assumed to be normalized. + */ + private def dependencyGraph( + axioms: Seq[OWLAxiom], + datafiles: Seq[File] + ): (Graph[Resource, DiEdge], Map[String, OWLAxiom]) = { + val unsafe = this.unsafeRoles + var nodemap = Map.empty[String, OWLAxiom] + + object RSAConverter extends RDFoxConverter { + + override def convert( + expr: OWLClassExpression, + term: Term, + unsafe: List[OWLObjectPropertyExpression], + skolem: SkolemStrategy, + suffix: RSASuffix + ): Shards = + (expr, skolem) match { + + case (e: OWLObjectSomeValuesFrom, c: Constant) => { + nodemap.update(c.iri.getIRI, c.axiom) + val (res, ext) = super.convert(e, term, unsafe, skolem, suffix) + if (unsafe contains e.getProperty) + (RSA.PE(term, c.iri) :: RSA.U(c.iri) :: res, ext) + else + (RSA.PE(term, c.iri) :: res, ext) + } + + case (e: OWLDataSomeValuesFrom, c: Constant) => { + nodemap.update(c.iri.getIRI, c.axiom) + val (res, ext) = super.convert(e, term, unsafe, skolem, suffix) + if (unsafe contains e.getProperty) + (RSA.PE(term, c.iri) :: RSA.U(c.iri) :: res, ext) + else + (RSA.PE(term, c.iri) :: res, ext) + } + + case _ => super.convert(expr, term, unsafe, skolem, suffix) + } + } + + /* Ontology convertion into LP rules */ + val term = RSAOntology.genFreshVariable() + val result = axioms.map(a => + RSAConverter.convert(a, term, unsafe, new Constant(a), Empty) + ) + + val datalog = result.unzip + val facts = datalog._1.flatten + var rules = datalog._2.flatten + + /* Open connection with RDFox */ + val (server, data) = RDFoxUtil.openConnection("rsa_dependency_graph") + + /* Add additional built-in rules */ + val varX = Variable.create("X") + val varY = Variable.create("Y") + rules = Rule.create( + RSA.E(varX, varY), + RSA.PE(varX, varY), + RSA.U(varX), + RSA.U(varY) + ) :: rules + /* Load facts and rules from ontology */ + RDFoxUtil.addFacts(data, facts) + RDFoxUtil.addRules(data, rules) + /* Load data files */ + RDFoxUtil.addData(data, datafiles: _*) + + /* Build the graph */ + val query = "SELECT ?X ?Y WHERE { ?X rsa:E ?Y }" + val answers = RDFoxUtil.submitQuery(data, query, RSA.Prefixes).get + var edges: Seq[DiEdge[Resource]] = + answers.collect { case (_, Seq(n1, n2)) => n1 ~> n2 } + val graph = Graph(edges: _*) + + /* Close connection to RDFox */ + RDFoxUtil.closeConnection(server, data) + + (graph, nodemap) + } +} + object RSAOntology { /** Name of the RDFox data store used for CQ answering */ @@ -79,14 +177,63 @@ object RSAOntology { /** Manager instance to interface with OWLAPI */ val manager = OWLManager.createOWLOntologyManager() - def apply(ontology: File, data: File*): RSAOntology = + def apply( + ontofile: File, + datafiles: Seq[File], + approx: Option[Approximation] = None + ): RSAOntology = { + val ontology = manager.loadOntologyFromOntologyDocument(ontofile) + RSAOntology(ontology, datafiles, approx) + } + + def apply( + ontology: OWLOntology, + datafiles: Seq[File], + approx: Option[Approximation] = None + ): RSAOntology = { + val normalizer = new Normalizer() + + /** TBox axioms */ + var tbox: List[OWLLogicalAxiom] = + original + .tboxAxioms(Imports.INCLUDED) + .collect(Collectors.toList()) + .collect { case a: OWLLogicalAxiom => a } + .flatMap(normalizer.normalize) + + /** RBox axioms */ + var rbox: List[OWLLogicalAxiom] = + original + .rboxAxioms(Imports.INCLUDED) + .collect(Collectors.toList()) + .collect { case a: OWLLogicalAxiom => a } + .flatMap(normalizer.normalize) + + /** ABox axioms + * + * @note this represents only the set of assertions contained in the + * ontology file. Data files specified in `datafiles` are directly + * imported in RDFox due to performance issues when trying to import + * large data files via OWLAPI. + */ + var abox: List[OWLLogicalAxiom] = + original + .aboxAxioms(Imports.INCLUDED) + .collect(Collectors.toList()) + .collect { case a: OWLLogicalAxiom => a } + .flatMap(normalizer.normalize) + + /** Collection of logical axioms in the input ontology */ + var axioms: List[OWLLogicalAxiom] = abox ::: tbox ::: rbox + new RSAOntology( - manager.loadOntologyFromOntologyDocument(ontology), - data: _* + approx match { + case Some(a) => a.approximate(axioms, datafiles) + case None => axioms + }, + datafiles ) - - def apply(ontology: OWLOntology, data: File*): RSAOntology = - new RSAOntology(ontology, data: _*) + } } /** Wrapper class for an ontology in RSA @@ -94,7 +241,7 @@ object RSAOntology { * @param ontology the input OWL2 ontology. * @param datafiles additinal data (treated as part of the ABox) */ -class RSAOntology(val original: OWLOntology, val datafiles: File*) { +class RSAOntology(val axioms: Seq[OWLAxiom], val datafiles: File*) { /** Simplify conversion between OWLAPI and RDFox concepts */ import implicits.RDFox._ @@ -104,49 +251,8 @@ class RSAOntology(val original: OWLOntology, val datafiles: File*) { /** Set of axioms removed during the approximation to RSA */ private var removed: Seq[OWLAxiom] = Seq.empty - /** The normalizer normalizes the ontology and approximate it to - * Horn-ALCHOIQ. A further step is needed to obtain an RSA - * approximation of the input ontology `original`. - */ - private val normalizer = new Normalizer() - - /** TBox axioms */ - var tbox: List[OWLLogicalAxiom] = - original - .tboxAxioms(Imports.INCLUDED) - .collect(Collectors.toList()) - .collect { case a: OWLLogicalAxiom => a } - .flatMap(normalizer.normalize) - - /** RBox axioms */ - var rbox: List[OWLLogicalAxiom] = - original - .rboxAxioms(Imports.INCLUDED) - .collect(Collectors.toList()) - .collect { case a: OWLLogicalAxiom => a } - .flatMap(normalizer.normalize) - - /** ABox axioms - * - * @note this represents only the set of assertions contained in the - * ontology file. Data files specified in `datafiles` are directly - * imported in RDFox due to performance issues when trying to import - * large data files via OWLAPI. - */ - var abox: List[OWLLogicalAxiom] = - original - .aboxAxioms(Imports.INCLUDED) - .collect(Collectors.toList()) - .collect { case a: OWLLogicalAxiom => a } - .flatMap(normalizer.normalize) - - /** Collection of logical axioms in the input ontology */ - var axioms: List[OWLLogicalAxiom] = abox ::: tbox ::: rbox - /** Normalized Horn-ALCHOIQ ontology */ - val ontology = RSAOntology.manager.createOntology( - axioms.asInstanceOf[List[OWLAxiom]].asJava - ) + val ontology = RSAOntology.manager.createOntology(axioms.asJava) /** OWLAPI internal reasoner instantiated over the approximated ontology */ private val reasoner = @@ -170,7 +276,7 @@ class RSAOntology(val original: OWLOntology, val datafiles: File*) { val concepts: List[OWLClass] = ontology.getClassesInSignature().asScala.toList val roles: List[OWLObjectPropertyExpression] = - (tbox ++ rbox) + axioms .flatMap(_.objectPropertyExpressionsInSignature) .distinct @@ -190,12 +296,12 @@ class RSAOntology(val original: OWLOntology, val datafiles: File*) { /* Checking for unsafety condition (1) */ val unsafe1 = for { - axiom <- tbox + axiom <- axioms if axiom.isT5 role1 <- axiom.objectPropertyExpressionsInSignature roleSuper = role1 +: reasoner.superObjectProperties(role1) roleSuperInv = roleSuper.map(_.getInverseProperty) - axiom <- tbox + axiom <- axioms if axiom.isT3 && !axiom.isT3top role2 <- axiom.objectPropertyExpressionsInSignature if roleSuperInv contains role2 @@ -203,12 +309,12 @@ class RSAOntology(val original: OWLOntology, val datafiles: File*) { /* Checking for unsafety condition (2) */ val unsafe2 = for { - axiom <- tbox + axiom <- axioms if axiom.isT5 role1 <- axiom.objectPropertyExpressionsInSignature roleSuper = role1 +: reasoner.superObjectProperties(role1) roleSuperInv = roleSuper.map(_.getInverseProperty) - axiom <- tbox + axiom <- axioms if axiom.isT4 role2 <- axiom.objectPropertyExpressionsInSignature if roleSuper.contains(role2) || roleSuperInv.contains(role2) @@ -217,93 +323,6 @@ class RSAOntology(val original: OWLOntology, val datafiles: File*) { unsafe1 ++ unsafe2 } - /** Compute the RSA dependency graph - * - * This is used to approximate the input ontology to RSA. - * - * @return a tuple containing the dependency graph and a map between - * the constants newly introduced and the corresponding axioms in the - * ontology. - */ - private def dependencyGraph() - : (Graph[Resource, DiEdge], Map[String, OWLAxiom]) = { - val unsafe = this.unsafeRoles - var nodemap = Map.empty[String, OWLAxiom] - - object RSAConverter extends RDFoxConverter { - - override def convert( - expr: OWLClassExpression, - term: Term, - unsafe: List[OWLObjectPropertyExpression], - skolem: SkolemStrategy, - suffix: RSASuffix - ): Shards = - (expr, skolem) match { - - case (e: OWLObjectSomeValuesFrom, c: Constant) => { - nodemap.update(c.iri.getIRI, c.axiom) - val (res, ext) = super.convert(e, term, unsafe, skolem, suffix) - if (unsafe contains e.getProperty) - (RSA.PE(term, c.iri) :: RSA.U(c.iri) :: res, ext) - else - (RSA.PE(term, c.iri) :: res, ext) - } - - case (e: OWLDataSomeValuesFrom, c: Constant) => { - nodemap.update(c.iri.getIRI, c.axiom) - val (res, ext) = super.convert(e, term, unsafe, skolem, suffix) - if (unsafe contains e.getProperty) - (RSA.PE(term, c.iri) :: RSA.U(c.iri) :: res, ext) - else - (RSA.PE(term, c.iri) :: res, ext) - } - - case _ => super.convert(expr, term, unsafe, skolem, suffix) - } - } - - /* Ontology convertion into LP rules */ - val term = RSAOntology.genFreshVariable() - val result = axioms.map(a => - RSAConverter.convert(a, term, unsafe, new Constant(a), Empty) - ) - - val datalog = result.unzip - val facts = datalog._1.flatten - var rules = datalog._2.flatten - - /* Open connection with RDFox */ - val (server, data) = RDFoxUtil.openConnection("rsa_dependency_graph") - - /* Add additional built-in rules */ - val varX = Variable.create("X") - val varY = Variable.create("Y") - rules = Rule.create( - RSA.E(varX, varY), - RSA.PE(varX, varY), - RSA.U(varX), - RSA.U(varY) - ) :: rules - /* Load facts and rules from ontology */ - RDFoxUtil.addFacts(data, facts) - RDFoxUtil.addRules(data, rules) - /* Load data files */ - RDFoxUtil.addData(data, datafiles: _*) - - /* Build the graph */ - val query = "SELECT ?X ?Y WHERE { ?X rsa:E ?Y }" - val answers = RDFoxUtil.submitQuery(data, query, RSA.Prefixes).get - var edges: Seq[DiEdge[Resource]] = - answers.collect { case (_, Seq(n1, n2)) => n1 ~> n2 } - val graph = Graph(edges: _*) - - /* Close connection to RDFox */ - RDFoxUtil.closeConnection(server, data) - - (graph, nodemap) - } - /** Approximate a Horn-ALCHOIQ ontology to RSA * * This is done by gathering those axioms that prevent the ontology @@ -653,7 +672,7 @@ class RSAOntology(val original: OWLOntology, val datafiles: File*) { val conflR = this.confl(roleR) // We just need the TBox to find val terms = for { - axiom1 <- tbox + axiom1 <- axioms if axiom1.isT5 // We expect only one role coming out of a T5 axiom roleS <- axiom1.objectPropertyExpressionsInSignature @@ -693,7 +712,7 @@ class RSAOntology(val original: OWLOntology, val datafiles: File*) { ) Logger.print( s"Logical axioms in Horn-ALCHOIQ ontology: ${ontology - .getLogicalAxiomCount(true)} (${tbox.length}/${rbox.length}/${abox.length})", + .getLogicalAxiomCount(true)} (${axioms.length}/${axioms.length}/${axioms.length})", level ) Logger.print( diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/approximation.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/approximation.scala new file mode 100644 index 0000000..073d0d9 --- /dev/null +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/approximation.scala @@ -0,0 +1,16 @@ +package uk.ac.ox.cs.rsacomb.approximation + +import java.io.File +import org.semanticweb.owlapi.model.OWLAxiom + +/** Ontology approximation technique. */ +trait Approximation { + + /** Approximate an ontology. + * + * @param ontology input ontology + * @return a new approximated ontology + */ + def approximate(ontology: Seq[OWLAxiom], datafiles: Seq[File]): Seq[OWLAxiom] + +} diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/lowerbound.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/lowerbound.scala new file mode 100644 index 0000000..8036250 --- /dev/null +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/lowerbound.scala @@ -0,0 +1,207 @@ +package uk.ac.ox.cs.rsacomb.approximation + +/** Approximation algorithm that mantains soundness 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 LowerBound extends Approximation { + + val normalizer = new Normalizer() + + /** Main entry point for the approximation algorithm */ + def approximate( + ontology: Seq[OWLAxiom], + datafiles: Seq[File] + ): Seq[OWLAxiom] = { + /* Normalize axioms */ + val axioms1 = axioms flatMap normalizer.normalize + /* Delete any axiom outside of ALCHOIQ */ + val axioms2 = axioms1 filterNot inHornLACHOIQ + /* Shift any axiom with disjunction on the rhs */ + val axioms3 = for { + a1 <- axioms1 + a2 <- shift(a1) + a3 <- normalize(a2) + } yield a3 + /* Approximate to RSA */ + toRSA(axioms3, datafiles) + } + + /** Discards all axioms outside ALCHOIQ */ + 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 + } + + /** Shifting axioms with disjunction on the rhs. + * + * The process of shifting presenves soundness but completenes w.r.t. + * CQ answering is lost. + * + * @example + * + * A -> B1 u B2 u B3 . + * + * becomes + * + * A n nB1 n nB2 -> B3 . + * A n nB1 n nB3 -> B2 . + * A n nB2 n nB3 -> B1 . + * nB1 n nB2 n nB3 -> nA . + * + * where nA, nB1, nB2, nB3 are fresh predicates "corresponding" to + * the negation of A, B1, B2, B3 respectively. + */ + def shift(axiom: OWLLogicalAxiom): Seq[OWLLogicalAxiom] = + axiom match { + case a: OWLSubClassOfAxiom => { + val sub = a.getSubClass.getNNF + val sup = a.getSuperClass.getNNF + sup match { + case sup: OWLObjectUnionOf => { + val body = sub.asConjunctSet.map((atom) => (atom, freshOWLClass())) + val head = sup.asDisjunctSet.map((atom) => (atom, freshOWLClass())) + + val r1 = + factory.getOWLSubClassOfAxiom( + factory.getOWLObjectIntersectionOf( + (body.map(_._1) ++ head.map(_._2)): _* + ), + factory.getOWLNothing + ) + + val r2s = + for { + (a, na) <- head + hs = head.map(_._2).filterNot(_ equals na) + } yield factory.getOWLSubClassOfAxiom( + factory.getOWLObjectIntersectionOf( + (body.map(_._1) ++ hs): _* + ), + a + ) + + val r3s = + for { + (a, na) <- body + bs = body.map(_._1).filterNot(_ equals a) + } yield factory.getOWLSubClassOfAxiom( + factory.getOWLObjectIntersectionOf( + (bs ++ head.map(_._2)): _* + ), + na + ) + + Seq(r1) ++ r2s ++ r3s + } + case _ => Seq(axiom) + } + } + case _ => Seq(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 axioms the set of axioms to approximate. + * @return the approximated set of axioms. + */ + def toRSA(axioms: Seq[OWLAxiom], datafiles: Seq[File]): Seq[OWLAxiom] = { + /* Compute the dependency graph for the ontology */ + val (graph, nodemap) = RSAUtil.dependencyGraph(axioms, datafiles) + + /* 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.iterator.collect { case (resource: IRI, ToDelete) => + nodemap(resource.getIRI) + }.toSeq + + /* Remove axioms from approximated ontology */ + axioms diff toDelete + } + // 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