diff options
-rw-r--r-- | src/main/scala/uk/ac/ox/cs/rsacomb/approximation/Upperbound.scala | 228 |
1 files changed, 128 insertions, 100 deletions
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 index ba26113..65cdee1 100644 --- a/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/Upperbound.scala +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/approximation/Upperbound.scala | |||
@@ -5,18 +5,18 @@ package uk.ac.ox.cs.rsacomb.approximation | |||
5 | import org.semanticweb.owlapi.apibinding.OWLManager | 5 | import org.semanticweb.owlapi.apibinding.OWLManager |
6 | import org.semanticweb.owlapi.model.{IRI => _, _} | 6 | import org.semanticweb.owlapi.model.{IRI => _, _} |
7 | 7 | ||
8 | // import tech.oxfordsemantic.jrdfox.logic.expression.{Resource, IRI} | 8 | import tech.oxfordsemantic.jrdfox.logic.expression.{Resource, IRI} |
9 | 9 | ||
10 | // import scala.collection.mutable.{Set, Map} | 10 | import scala.collection.mutable.Map |
11 | // import scalax.collection.Graph | 11 | import scalax.collection.Graph |
12 | // import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._ | 12 | import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._ |
13 | // import scalax.collection.GraphTraversal._ | 13 | import scalax.collection.GraphTraversal._ |
14 | 14 | ||
15 | import uk.ac.ox.cs.rsacomb.RSAOntology | 15 | import uk.ac.ox.cs.rsacomb.RSAOntology |
16 | // import uk.ac.ox.cs.rsacomb.RSAUtil | 16 | import uk.ac.ox.cs.rsacomb.RSAUtil |
17 | import uk.ac.ox.cs.rsacomb.ontology.Ontology | 17 | import uk.ac.ox.cs.rsacomb.ontology.Ontology |
18 | 18 | ||
19 | object UpperBound { | 19 | object Upperbound { |
20 | 20 | ||
21 | private val manager = OWLManager.createOWLOntologyManager() | 21 | private val manager = OWLManager.createOWLOntologyManager() |
22 | private val factory = manager.getOWLDataFactory() | 22 | private val factory = manager.getOWLDataFactory() |
@@ -38,7 +38,7 @@ object UpperBound { | |||
38 | * | 38 | * |
39 | * @see [[uk.ac.ox.cs.rsacomb.converter.Normalizer]] | 39 | * @see [[uk.ac.ox.cs.rsacomb.converter.Normalizer]] |
40 | */ | 40 | */ |
41 | class UpperBound extends Approximation[RSAOntology] { | 41 | class Upperbound extends Approximation[RSAOntology] { |
42 | 42 | ||
43 | /** Simplify conversion between Java and Scala collections */ | 43 | /** Simplify conversion between Java and Scala collections */ |
44 | import uk.ac.ox.cs.rsacomb.implicits.JavaCollections._ | 44 | import uk.ac.ox.cs.rsacomb.implicits.JavaCollections._ |
@@ -50,52 +50,52 @@ class UpperBound extends Approximation[RSAOntology] { | |||
50 | def approximate(ontology: Ontology): RSAOntology = | 50 | def approximate(ontology: Ontology): RSAOntology = |
51 | toRSA( | 51 | toRSA( |
52 | new Ontology( | 52 | new Ontology( |
53 | ontology.axioms filter inALCHOIQ flatMap toConjuncts, | 53 | ontology.axioms flatMap toConjuncts, |
54 | ontology.datafiles | 54 | ontology.datafiles |
55 | ) | 55 | ) |
56 | ) | 56 | ) |
57 | 57 | ||
58 | /** Discards all axioms outside ALCHOIQ */ | 58 | /** Discards all axioms outside ALCHOIQ */ |
59 | private def inALCHOIQ(axiom: OWLLogicalAxiom): Boolean = | 59 | // private def inALCHOIQ(axiom: OWLLogicalAxiom): Boolean = |
60 | axiom match { | 60 | // axiom match { |
61 | case a: OWLSubClassOfAxiom => { | 61 | // case a: OWLSubClassOfAxiom => { |
62 | val sub = a.getSubClass.getNNF | 62 | // val sub = a.getSubClass.getNNF |
63 | val sup = a.getSuperClass.getNNF | 63 | // val sup = a.getSuperClass.getNNF |
64 | (sub, sup) match { | 64 | // (sub, sup) match { |
65 | case (sub: OWLObjectAllValuesFrom, _) => false | 65 | // case (sub: OWLObjectAllValuesFrom, _) => false |
66 | case (sub: OWLDataAllValuesFrom, _) => false | 66 | // case (sub: OWLDataAllValuesFrom, _) => false |
67 | case (_, sup: OWLDataAllValuesFrom) => false | 67 | // case (_, sup: OWLDataAllValuesFrom) => false |
68 | case (sub: OWLObjectMinCardinality, _) if sub.getCardinality >= 2 => | 68 | // case (sub: OWLObjectMinCardinality, _) if sub.getCardinality >= 2 => |
69 | false | 69 | // false |
70 | case (sub: OWLDataMinCardinality, _) if sub.getCardinality >= 2 => | 70 | // case (sub: OWLDataMinCardinality, _) if sub.getCardinality >= 2 => |
71 | false | 71 | // false |
72 | case (_, sup: OWLObjectMinCardinality) if sup.getCardinality >= 2 => | 72 | // case (_, sup: OWLObjectMinCardinality) if sup.getCardinality >= 2 => |
73 | false | 73 | // false |
74 | case (_, sup: OWLDataMinCardinality) if sup.getCardinality >= 2 => | 74 | // case (_, sup: OWLDataMinCardinality) if sup.getCardinality >= 2 => |
75 | false | 75 | // false |
76 | case (sub: OWLObjectMaxCardinality, _) => false | 76 | // case (sub: OWLObjectMaxCardinality, _) => false |
77 | case (sub: OWLDataMaxCardinality, _) => false | 77 | // case (sub: OWLDataMaxCardinality, _) => false |
78 | case (_, sup: OWLObjectMaxCardinality) if sup.getCardinality >= 2 => | 78 | // case (_, sup: OWLObjectMaxCardinality) if sup.getCardinality >= 2 => |
79 | false | 79 | // false |
80 | case (_, sup: OWLDataMaxCardinality) if sup.getCardinality >= 1 => | 80 | // case (_, sup: OWLDataMaxCardinality) if sup.getCardinality >= 1 => |
81 | false | 81 | // false |
82 | case (_, sup: OWLObjectOneOf) if sup.getIndividuals.length > 2 => | 82 | // case (_, sup: OWLObjectOneOf) if sup.getIndividuals.length > 2 => |
83 | false | 83 | // false |
84 | case (sub: OWLObjectHasSelf, _) => false | 84 | // case (sub: OWLObjectHasSelf, _) => false |
85 | case (_, sup: OWLObjectHasSelf) => false | 85 | // case (_, sup: OWLObjectHasSelf) => false |
86 | case _ => true | 86 | // case _ => true |
87 | } | 87 | // } |
88 | } | 88 | // } |
89 | case a: OWLTransitiveObjectPropertyAxiom => false | 89 | // case a: OWLTransitiveObjectPropertyAxiom => false |
90 | case a: OWLReflexiveObjectPropertyAxiom => false | 90 | // case a: OWLReflexiveObjectPropertyAxiom => false |
91 | case a: OWLSubPropertyChainOfAxiom => false | 91 | // case a: OWLSubPropertyChainOfAxiom => false |
92 | case a: OWLAsymmetricObjectPropertyAxiom => false | 92 | // case a: OWLAsymmetricObjectPropertyAxiom => false |
93 | case a => true | 93 | // case a => true |
94 | } | 94 | // } |
95 | 95 | ||
96 | /** Turn disjuncts into conjuncts | 96 | /** Turn disjuncts into conjuncts |
97 | * | 97 | * |
98 | * This is a very naive way of getting rid of disjunction preserving | 98 | * This is a very naïve way of getting rid of disjunction preserving |
99 | * completeness of CQ answering. | 99 | * completeness of CQ answering. |
100 | * | 100 | * |
101 | * @todo implement a choice function that decides which disjunct to | 101 | * @todo implement a choice function that decides which disjunct to |
@@ -110,7 +110,7 @@ class UpperBound extends Approximation[RSAOntology] { | |||
110 | sup match { | 110 | sup match { |
111 | case sup: OWLObjectUnionOf => | 111 | case sup: OWLObjectUnionOf => |
112 | sup.asDisjunctSet.map( | 112 | sup.asDisjunctSet.map( |
113 | UpperBound.factory.getOWLSubClassOfAxiom(sub, _) | 113 | Upperbound.factory.getOWLSubClassOfAxiom(sub, _) |
114 | ) | 114 | ) |
115 | case _ => List(axiom) | 115 | case _ => List(axiom) |
116 | } | 116 | } |
@@ -118,60 +118,88 @@ class UpperBound extends Approximation[RSAOntology] { | |||
118 | case _ => List(axiom) | 118 | case _ => List(axiom) |
119 | } | 119 | } |
120 | 120 | ||
121 | // /** Approximate a Horn-ALCHOIQ ontology to RSA | 121 | /** Approximate a Horn-ALCHOIQ ontology to RSA |
122 | // * | 122 | * |
123 | // * This is done by gathering those axioms that prevent the ontology | 123 | * This is done by gathering those existential axioms that prevent |
124 | // * dependency graph from being tree-shaped, and removing them. | 124 | * the ontology dependency graph from being tree-shaped and constant |
125 | // * | 125 | * skolemize them. |
126 | // * @param ontology the set of axioms to approximate. | 126 | * |
127 | // * @return the approximated RSA ontology | 127 | * @param ontology the set of axioms to approximate. |
128 | // */ | 128 | * @return the approximated RSA ontology |
129 | // private def toRSA(ontology: Ontology): RSAOntology = { | 129 | */ |
130 | // /* Compute the dependency graph for the ontology */ | 130 | private def toRSA(ontology: Ontology): RSAOntology = { |
131 | // val (graph, nodemap) = ontology.dependencyGraph | 131 | /* Compute the dependency graph for the ontology */ |
132 | 132 | val (graph, nodemap) = ontology.dependencyGraph | |
133 | // /* Define node colors for the graph visit */ | 133 | |
134 | // sealed trait NodeColor | 134 | /* Define node colors for the graph visit */ |
135 | // case object Unvisited extends NodeColor | 135 | sealed trait NodeColor |
136 | // case object Visited extends NodeColor | 136 | case object Unvisited extends NodeColor |
137 | // case object ToDelete extends NodeColor | 137 | case object Visited extends NodeColor |
138 | 138 | case object ToSkolem extends NodeColor | |
139 | // /* Keep track of node colors during graph visit */ | 139 | |
140 | // var color = Map.from[Resource, NodeColor]( | 140 | /* Keep track of node colors during graph visit */ |
141 | // graph.nodes.toOuter.map(k => (k, Unvisited)) | 141 | var color = Map.from[Resource, NodeColor]( |
142 | // ) | 142 | graph.nodes.toOuter.map(k => (k, Unvisited)) |
143 | 143 | ) | |
144 | // for { | 144 | |
145 | // component <- graph.componentTraverser().map(_ to Graph) | 145 | for { |
146 | // edge <- component | 146 | component <- graph.componentTraverser().map(_ to Graph) |
147 | // .outerEdgeTraverser(component.nodes.head) | 147 | edge <- component |
148 | // .withKind(BreadthFirst) | 148 | .outerEdgeTraverser(component.nodes.head) |
149 | // } yield { | 149 | .withKind(BreadthFirst) |
150 | // val source = edge._1 | 150 | } yield { |
151 | // val target = edge._2 | 151 | val source = edge._1 |
152 | // color(source) match { | 152 | val target = edge._2 |
153 | // case Unvisited | Visited => { | 153 | color(source) match { |
154 | // color(target) match { | 154 | case Unvisited | Visited => { |
155 | // case Unvisited => | 155 | color(target) match { |
156 | // color(source) = Visited; | 156 | case Unvisited => |
157 | // color(target) = Visited | 157 | color(source) = Visited; |
158 | // case Visited => | 158 | color(target) = Visited |
159 | // color(source) = ToDelete | 159 | case Visited => |
160 | // case ToDelete => | 160 | color(source) = ToSkolem |
161 | // color(source) = Visited | 161 | case ToSkolem => |
162 | // } | 162 | color(source) = Visited |
163 | // } | 163 | } |
164 | // case ToDelete => | 164 | } |
165 | // } | 165 | case ToSkolem => {} |
166 | // } | 166 | } |
167 | } | ||
167 | 168 | ||
168 | // val toDelete = color.collect { case (resource: IRI, ToDelete) => | 169 | val toSkolem = color.collect { case (resource: IRI, ToSkolem) => |
169 | // nodemap(resource.getIRI) | 170 | nodemap(resource.getIRI) |
170 | // }.toList | 171 | }.toList |
172 | |||
173 | // Force constant skolemization by introducing a fresh individual | ||
174 | // (singleton class). | ||
175 | val skolemized = toSkolem flatMap { (axiom) => | ||
176 | import uk.ac.ox.cs.rsacomb.implicits.RSAAxiom._ | ||
177 | axiom.toTriple match { | ||
178 | case Some((subclass, role, filler)) => { | ||
179 | val skolem = Upperbound.factory.getOWLNamedIndividual(s"i_${axiom.toString.hashCode}") | ||
180 | val fresh = RSAUtil.getFreshOWLClass() | ||
181 | List( | ||
182 | Upperbound.factory.getOWLSubClassOfAxiom( | ||
183 | subclass, | ||
184 | Upperbound.factory.getOWLObjectSomeValuesFrom(role, fresh) | ||
185 | ), | ||
186 | Upperbound.factory.getOWLSubClassOfAxiom( | ||
187 | fresh, | ||
188 | Upperbound.factory.getOWLObjectOneOf(skolem) | ||
189 | ), | ||
190 | Upperbound.factory.getOWLClassAssertionAxiom(filler, skolem) | ||
191 | ) | ||
192 | } | ||
193 | case None => List() | ||
194 | } | ||
195 | } | ||
171 | 196 | ||
172 | // /* Remove axioms from approximated ontology */ | 197 | /* Substitute selected axioms with their "skolemized" version */ |
173 | // RSAOntology(ontology.axioms diff toDelete, ontology.datafiles) | 198 | RSAOntology( |
174 | // } | 199 | ontology.axioms diff toSkolem concat skolemized, |
200 | ontology.datafiles | ||
201 | ) | ||
202 | } | ||
175 | 203 | ||
176 | // val edges1 = Seq('A ~> 'B, 'B ~> 'C, 'C ~> 'D, 'D ~> 'H, 'H ~> | 204 | // val edges1 = Seq('A ~> 'B, 'B ~> 'C, 'C ~> 'D, 'D ~> 'H, 'H ~> |
177 | // 'G, 'G ~> 'F, 'E ~> 'A, 'E ~> 'F, 'B ~> 'E, 'F ~> 'G, 'B ~> 'F, | 205 | // 'G, 'G ~> 'F, 'E ~> 'A, 'E ~> 'F, 'B ~> 'E, 'F ~> 'G, 'B ~> 'F, |
@@ -179,5 +207,5 @@ class UpperBound extends Approximation[RSAOntology] { | |||
179 | // val edges2 = Seq('I ~> 'M, 'I ~> 'L, 'L ~> 'N, 'M ~> 'N) | 207 | // val edges2 = Seq('I ~> 'M, 'I ~> 'L, 'L ~> 'N, 'M ~> 'N) |
180 | // val edges3 = Seq('P ~> 'O) | 208 | // val edges3 = Seq('P ~> 'O) |
181 | // val graph = Graph.from(edges = edges1 ++ edges2 ++ edges3) | 209 | // val graph = Graph.from(edges = edges1 ++ edges2 ++ edges3) |
182 | // | 210 | |
183 | } | 211 | } |