From 1cb2165ccbcd6b1210bee1dfb7b527b4d2440901 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Thu, 4 Feb 2021 10:41:09 +0000 Subject: Add versioning system for different versions of code Later on this will allow us to select the algorithm from the command line and compare performance easily. --- .../uk/ac/ox/cs/rsacomb/FilteringProgram.scala | 313 --------------------- .../scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala | 3 +- .../ox/cs/rsacomb/filtering/FilteringProgram.scala | 41 +++ .../rsacomb/filtering/NaiveFilteringProgram.scala | 307 ++++++++++++++++++++ .../scala/uk/ac/ox/cs/rsacomb/util/Versioned.scala | 18 ++ .../ac/ox/cs/rsacomb/FilteringProgramSpecs.scala | 92 ------ src/test/scala/uk/ac/ox/cs/rsacomb/SuiteAll.scala | 33 ++- .../rsacomb/filtering/FilteringProgramSpecs.scala | 94 +++++++ 8 files changed, 483 insertions(+), 418 deletions(-) delete mode 100644 src/main/scala/uk/ac/ox/cs/rsacomb/FilteringProgram.scala create mode 100644 src/main/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgram.scala create mode 100644 src/main/scala/uk/ac/ox/cs/rsacomb/filtering/NaiveFilteringProgram.scala create mode 100644 src/main/scala/uk/ac/ox/cs/rsacomb/util/Versioned.scala delete mode 100644 src/test/scala/uk/ac/ox/cs/rsacomb/FilteringProgramSpecs.scala create mode 100644 src/test/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgramSpecs.scala diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/FilteringProgram.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/FilteringProgram.scala deleted file mode 100644 index 06224e7..0000000 --- a/src/main/scala/uk/ac/ox/cs/rsacomb/FilteringProgram.scala +++ /dev/null @@ -1,313 +0,0 @@ -package uk.ac.ox.cs.rsacomb - -//import scala.collection.JavaConverters._ -import tech.oxfordsemantic.jrdfox.logic.Datatype -import tech.oxfordsemantic.jrdfox.logic.datalog.{ - Rule, - TupleTableAtom, - BodyFormula, - Negation -} -import tech.oxfordsemantic.jrdfox.logic.expression.{Term, Variable} -import uk.ac.ox.cs.rsacomb.sparql.ConjunctiveQuery -import uk.ac.ox.cs.rsacomb.suffix.{Forward, Backward} -import uk.ac.ox.cs.rsacomb.util.{RSA, RDFoxUtil} - -/** Factory for [[uk.ac.ox.cs.rsacomb.FilteringProgram FilteringProgram]] */ -object FilteringProgram { - - /** Create a new FilteringProgram instance. - * - * @param query CQ to be converted into logic rules. - * @param constants constants in the original ontology. They will be - * used to initialize predicate `rsa:Named`. - */ - def apply(query: ConjunctiveQuery): FilteringProgram = - new FilteringProgram(query) - -} - -/** Filtering Program generator - * - * Handles the conversion of a CQ into a set of logic rules, - * representing the filtering step of the RSA combined approach. - * - * Instances can be created using the companion object. - */ -class FilteringProgram(query: ConjunctiveQuery) { - - /** Extends capabilities of - * [[tech.oxfordsemantic.jrdfox.logic.datalog.TupleTableAtom TupleTableAtom]] - */ - import uk.ac.ox.cs.rsacomb.implicits.RSAAtom._ - - /** Implicit parameter used in RSA internal predicates. - * - * @see [[uk.ac.ox.cs.rsacomb.util.RSA]] for more information. - */ - implicit private[this] val _query = query - - /** General purpose variables used in rule instantiation. - * - * This is done to avoid creating new variables every time. - */ - private val varX = Variable.create("X") - private val varY = Variable.create("Y") - private val varZ = Variable.create("Z") - private val varV = Variable.create("V") - private val varU = Variable.create("U") - private val varW = Variable.create("W") - - /** Rule generating the instances of the predicate `rsa:NI`. - * - * According to the original paper, the set of `rsa:NI` is defined as - * the set of constants that are equal (w.r.t. the congruence - * relation represented by `rsa:Congruent`) to a constant in the - * original ontology. - * - * @note that the set of `rsa:Named` constants is always a subset of - * the set of `rsa:NI`s. - * - * @note in the paper, instances of `rsa:NI` are introduced as facts - * during the canonical model computation. By definition of the - * predicate, this is not feasible, and the instances are instead - * generate in the filtering program using a logic rule. - */ - val nis: Rule = - Rule.create(RSA.NI(varX), RSA.Congruent(varX, varY), RSA.Named(varY)) - - /** Collection of filtering program rules. */ - val rules: List[Rule] = - nis :: { - - /** Negates a [[tech.oxfordsemantic.jrdfox.logic.datalog.TupleTableAtom TupleTableAtom]] */ - def not(atom: TupleTableAtom): BodyFormula = Negation.create(atom) - - /** Generates all possible, unfiltered answers. - * - * @note corresponds to rule 1 in Table 3 in the paper. - */ - val r1 = Rule.create(RSA.QM, query.atoms: _*) - - /** Initializes instances of `rsa:ID`. - * - * They are initialized as a minimal congruence relation over the - * positions of the existential variables in the query which are - * mapped to anonymous terms. - * - * @note corresponds to rules 3x in Table 3. - */ - val r3a = - for ((v, i) <- query.bounded.zipWithIndex) - yield Rule.create(RSA.ID(RSA(i), RSA(i)), RSA.QM, not(RSA.NI(v))) - val r3b = Rule.create(RSA.ID(varV, varU), RSA.ID(varU, varV)) - val r3c = - Rule.create(RSA.ID(varU, varW), RSA.ID(varU, varV), RSA.ID(varV, varW)) - - /** Detects forks in the canonical model. - * - * @note corresponds to rules 4x in Table 3. - */ - val r4a = for { - role1 <- query.atoms filter (_.isRoleAssertion) - index1 = query.bounded indexOf (role1.getArguments get 2) - if index1 >= 0 - role2 <- query.atoms filter (_.isRoleAssertion) - index2 = query.bounded indexOf (role2.getArguments get 2) - if index2 >= 0 - } yield Rule.create( - RSA.FK, - RSA.ID(RSA(index1), RSA(index2)), - role1 << Forward, - role2 << Forward, - not(RSA.Congruent(role1.getArguments get 0, role2.getArguments get 0)) - ) - val r4b = for { - role1 <- query.atoms filter (_.isRoleAssertion) - index1 = query.bounded indexOf (role1.getArguments get 2) - if index1 >= 0 - role2 <- query.atoms filter (_.isRoleAssertion) - index2 = query.bounded indexOf (role2.getArguments get 0) - if index2 >= 0 - } yield Rule.create( - RSA.FK, - RSA.ID(RSA(index1), RSA(index2)), - role1 << Forward, - role2 << Backward, - not(RSA.Congruent(role1.getArguments get 0, role2.getArguments get 2)) - ) - val r4c = for { - role1 <- query.atoms filter (_.isRoleAssertion) - index1 = query.bounded indexOf (role1.getArguments get 0) - if index1 >= 0 - role2 <- query.atoms filter (_.isRoleAssertion) - index2 = query.bounded indexOf (role2.getArguments get 0) - if index2 >= 0 - } yield Rule.create( - RSA.FK, - RSA.ID(RSA(index1), RSA(index2)), - role1 << Backward, - role2 << Backward, - not(RSA.Congruent(role1.getArguments get 2, role2.getArguments get 2)) - ) - - /** Recursively propagates `rsa:ID` predicate. - * - * @note corresponds to rules 5x in Table 3. - */ - val r5a = for { - role1 <- query.atoms filter (_.isRoleAssertion) - r1arg0 = role1.getArguments get 0 - if query.bounded contains r1arg0 - r1arg2 = role1.getArguments get 2 - if query.bounded contains r1arg2 - role2 <- query.atoms filter (_.isRoleAssertion) - r2arg0 = role2.getArguments get 0 - if query.bounded contains r2arg0 - r2arg2 = role2.getArguments get 2 - if query.bounded contains r2arg2 - } yield Rule.create( - RSA.ID( - RSA(query.bounded indexOf r1arg0), - RSA(query.bounded indexOf r2arg0) - ), - RSA.ID( - RSA(query.bounded indexOf r1arg2), - RSA(query.bounded indexOf r2arg2) - ), - RSA.Congruent(r1arg0, r2arg0), - role1 << Forward, - role2 << Forward, - not(RSA.NI(r1arg0)) - ) - val r5b = for { - role1 <- query.atoms filter (_.isRoleAssertion) - r1arg0 = role1.getArguments get 0 - if query.bounded contains r1arg0 - r1arg2 = role1.getArguments get 2 - if query.bounded contains r1arg2 - role2 <- query.atoms filter (_.isRoleAssertion) - r2arg0 = role2.getArguments get 0 - if query.bounded contains r2arg0 - r2arg2 = role2.getArguments get 2 - if query.bounded contains r2arg2 - } yield Rule.create( - RSA.ID( - RSA(query.bounded indexOf r1arg0), - RSA(query.bounded indexOf r2arg2) - ), - RSA.ID( - RSA(query.bounded indexOf r1arg2), - RSA(query.bounded indexOf r2arg0) - ), - RSA.Congruent(r1arg0, r2arg2), - role1 << Forward, - role2 << Backward, - not(RSA.NI(r1arg0)) - ) - val r5c = for { - role1 <- query.atoms filter (_.isRoleAssertion) - r1arg0 = role1.getArguments get 0 - if query.bounded contains r1arg0 - r1arg2 = role1.getArguments get 2 - if query.bounded contains r1arg2 - role2 <- query.atoms filter (_.isRoleAssertion) - r2arg0 = role2.getArguments get 0 - if query.bounded contains r2arg0 - r2arg2 = role2.getArguments get 2 - if query.bounded contains r2arg2 - } yield Rule.create( - RSA.ID( - RSA(query.bounded indexOf r1arg2), - RSA(query.bounded indexOf r2arg2) - ), - RSA.ID( - RSA(query.bounded indexOf r1arg0), - RSA(query.bounded indexOf r2arg0) - ), - RSA.Congruent(r1arg2, r2arg2), - role1 << Backward, - role2 << Backward, - not(RSA.NI(r1arg2)) - ) - - /** Detect cycles in the canonical model. - * - * Cycles are detected by introducing a new predicate `rsa:AQ` - * and computing its transitive closure. Cycles are computed from - * forward and backward roles separately. - * - * @note corresponds to rules 6,7x in Table 3. - */ - val r6 = for { - role <- query.atoms filter (_.isRoleAssertion) - index0 = query.bounded indexOf (role.getArguments get 0) - if index0 >= 0 - index2 = query.bounded indexOf (role.getArguments get 2) - if index2 >= 0 - suffix <- Seq(Forward, Backward) - } yield Rule.create( - RSA.AQ(varV, varW, suffix), - role << suffix, - RSA.ID(RSA(index0), varV), - RSA.ID(RSA(index2), varW) - ) - val r7a = - for (suffix <- List(Forward, Backward)) - yield Rule.create( - RSA.TQ(varU, varV, suffix), - RSA.AQ(varU, varV, suffix) - ) - val r7b = - for (suffix <- List(Forward, Backward)) - yield Rule.create( - RSA.TQ(varU, varW, suffix), - RSA.AQ(varU, varV, suffix), - RSA.TQ(varV, varW, suffix) - ) - - /** Flag spurious answers. - * - * @note corresponds to rules 8x in Table 3. - */ - val r8a = - for (v <- query.answer) - yield Rule.create(RSA.SP, RSA.QM, not(RSA.Named(v))) - val r8b = Rule.create(RSA.SP, RSA.FK) - val r8c = - for (suffix <- List(Forward, Backward)) - yield Rule.create( - RSA.SP, - RSA.TQ(varV, varV, suffix) - ) - - /** Determine answers to the query - * - * Answers are identified by predicate `rsa:Ans`. In case the - * input query is a BCQ (answer is just true/false), we derive - * `rsa:Ans` for a fresh constant `c`. Later on we can query for - * instances of `rsa:Ans` as follows - * - * {{{ - * ASK { ?X a rsa:Ans } - * }}} - * - * to determine whether the query is true or false. - * - * @note corresponds to rule 9 in Table 3. - */ - val r9 = Rule.create(RSA.Ans, RSA.QM, not(RSA.SP)) - - (r1 :: - r3a ::: r3b :: r3c :: - r4a ::: r4b ::: r4c ::: - r5a ::: r5b ::: r5c ::: - r6 ::: r7b ::: r7a ::: - r8a ::: r8b :: r8c ::: - r9 :: List()) map RDFoxUtil.reify - } - - /** Pretty-print filtering rule */ - override def toString(): String = rules mkString "\n" - -} 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 42a5b87..b0b52c7 100644 --- a/src/main/scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/RSAOntology.scala @@ -58,6 +58,7 @@ import tech.oxfordsemantic.jrdfox.logic._ import org.semanticweb.owlapi.model.OWLObjectInverseOf import uk.ac.ox.cs.rsacomb.converter._ +import uk.ac.ox.cs.rsacomb.filtering.{FilteringProgram, FilterType} import uk.ac.ox.cs.rsacomb.suffix._ import uk.ac.ox.cs.rsacomb.sparql._ import uk.ac.ox.cs.rsacomb.util.{RDFoxUtil, RSA} @@ -409,7 +410,7 @@ class RSAOntology(_ontology: File, val datafiles: File*) { def filteringProgram(query: ConjunctiveQuery): FilteringProgram = Logger.timed( - new FilteringProgram(query), + FilteringProgram(FilterType.FILTER_NAIVE)(query), "Generating filtering program", Logger.DEBUG ) diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgram.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgram.scala new file mode 100644 index 0000000..9c8cbaa --- /dev/null +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgram.scala @@ -0,0 +1,41 @@ +package uk.ac.ox.cs.rsacomb.filtering + +import tech.oxfordsemantic.jrdfox.logic.datalog.Rule +import uk.ac.ox.cs.rsacomb.sparql.ConjunctiveQuery +import uk.ac.ox.cs.rsacomb.util.Versioned + +sealed trait FilterType +object FilterType { + case object FILTER_NAIVE extends FilterType + case object FILTER_REVISED_V1 extends FilterType +} + +object FilteringProgram extends Versioned[FilterType] { + + import FilterType._ + + type Result = (ConjunctiveQuery) => FilteringProgram + + def apply(t: FilterType): (ConjunctiveQuery) => FilteringProgram = + t match { + case FILTER_NAIVE => NaiveFilteringProgram(_) + case FILTER_REVISED_V1 => NaiveFilteringProgram(_) + } +} + +/** Filtering Program generator + * + * Handles the conversion of a CQ into a set of logic rules, + * representing the filtering step of the RSA combined approach. + */ +trait FilteringProgram { + + /** Query from which the filtering program is generated */ + val query: ConjunctiveQuery + + /** Collection of filtering program rules. */ + def rules: List[Rule] + + /** Pretty-print filtering rule */ + override def toString(): String = rules mkString "\n" +} diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/filtering/NaiveFilteringProgram.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/filtering/NaiveFilteringProgram.scala new file mode 100644 index 0000000..57898a8 --- /dev/null +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/filtering/NaiveFilteringProgram.scala @@ -0,0 +1,307 @@ +package uk.ac.ox.cs.rsacomb.filtering + +//import scala.collection.JavaConverters._ +import tech.oxfordsemantic.jrdfox.logic.Datatype +import tech.oxfordsemantic.jrdfox.logic.datalog.{ + Rule, + TupleTableAtom, + BodyFormula, + Negation +} +import tech.oxfordsemantic.jrdfox.logic.expression.{Term, Variable} +import uk.ac.ox.cs.rsacomb.sparql.ConjunctiveQuery +import uk.ac.ox.cs.rsacomb.suffix.{Forward, Backward} +import uk.ac.ox.cs.rsacomb.util.{RSA, RDFoxUtil} + +/** Factory for [[uk.ac.ox.cs.rsacomb.FilteringProgram FilteringProgram]] */ +object NaiveFilteringProgram { + + /** Create a new FilteringProgram instance. + * + * @param query CQ to be converted into logic rules. + */ + def apply(query: ConjunctiveQuery): FilteringProgram = + new NaiveFilteringProgram(query) +} + +/** Filtering Program generator + * + * Handles the conversion of a CQ into a set of logic rules, + * representing the filtering step of the RSA combined approach. + * + * Instances can be created using the companion object. + */ +class NaiveFilteringProgram(val query: ConjunctiveQuery) + extends FilteringProgram { + + /** Extends capabilities of + * [[tech.oxfordsemantic.jrdfox.logic.datalog.TupleTableAtom TupleTableAtom]] + */ + import uk.ac.ox.cs.rsacomb.implicits.RSAAtom._ + + /** Implicit parameter used in RSA internal predicates. + * + * @see [[uk.ac.ox.cs.rsacomb.util.RSA]] for more information. + */ + implicit private[this] val _query = query + + /** General purpose variables used in rule instantiation. + * + * This is done to avoid creating new variables every time. + */ + private val varX = Variable.create("X") + private val varY = Variable.create("Y") + private val varZ = Variable.create("Z") + private val varV = Variable.create("V") + private val varU = Variable.create("U") + private val varW = Variable.create("W") + + /** Rule generating the instances of the predicate `rsa:NI`. + * + * According to the original paper, the set of `rsa:NI` is defined as + * the set of constants that are equal (w.r.t. the congruence + * relation represented by `rsa:Congruent`) to a constant in the + * original ontology. + * + * @note that the set of `rsa:Named` constants is always a subset of + * the set of `rsa:NI`s. + * + * @note in the paper, instances of `rsa:NI` are introduced as facts + * during the canonical model computation. By definition of the + * predicate, this is not feasible, and the instances are instead + * generate in the filtering program using a logic rule. + */ + val nis: Rule = + Rule.create(RSA.NI(varX), RSA.Congruent(varX, varY), RSA.Named(varY)) + + /** Collection of filtering program rules. */ + val rules: List[Rule] = + nis :: { + + /** Negates a [[tech.oxfordsemantic.jrdfox.logic.datalog.TupleTableAtom TupleTableAtom]] */ + def not(atom: TupleTableAtom): BodyFormula = Negation.create(atom) + + /** Generates all possible, unfiltered answers. + * + * @note corresponds to rule 1 in Table 3 in the paper. + */ + val r1 = Rule.create(RSA.QM, query.atoms: _*) + + /** Initializes instances of `rsa:ID`. + * + * They are initialized as a minimal congruence relation over the + * positions of the existential variables in the query which are + * mapped to anonymous terms. + * + * @note corresponds to rules 3x in Table 3. + */ + val r3a = + for ((v, i) <- query.bounded.zipWithIndex) + yield Rule.create(RSA.ID(RSA(i), RSA(i)), RSA.QM, not(RSA.NI(v))) + val r3b = Rule.create(RSA.ID(varV, varU), RSA.ID(varU, varV)) + val r3c = + Rule.create(RSA.ID(varU, varW), RSA.ID(varU, varV), RSA.ID(varV, varW)) + + /** Detects forks in the canonical model. + * + * @note corresponds to rules 4x in Table 3. + */ + val r4a = for { + role1 <- query.atoms filter (_.isRoleAssertion) + index1 = query.bounded indexOf (role1.getArguments get 2) + if index1 >= 0 + role2 <- query.atoms filter (_.isRoleAssertion) + index2 = query.bounded indexOf (role2.getArguments get 2) + if index2 >= 0 + } yield Rule.create( + RSA.FK, + RSA.ID(RSA(index1), RSA(index2)), + role1 << Forward, + role2 << Forward, + not(RSA.Congruent(role1.getArguments get 0, role2.getArguments get 0)) + ) + val r4b = for { + role1 <- query.atoms filter (_.isRoleAssertion) + index1 = query.bounded indexOf (role1.getArguments get 2) + if index1 >= 0 + role2 <- query.atoms filter (_.isRoleAssertion) + index2 = query.bounded indexOf (role2.getArguments get 0) + if index2 >= 0 + } yield Rule.create( + RSA.FK, + RSA.ID(RSA(index1), RSA(index2)), + role1 << Forward, + role2 << Backward, + not(RSA.Congruent(role1.getArguments get 0, role2.getArguments get 2)) + ) + val r4c = for { + role1 <- query.atoms filter (_.isRoleAssertion) + index1 = query.bounded indexOf (role1.getArguments get 0) + if index1 >= 0 + role2 <- query.atoms filter (_.isRoleAssertion) + index2 = query.bounded indexOf (role2.getArguments get 0) + if index2 >= 0 + } yield Rule.create( + RSA.FK, + RSA.ID(RSA(index1), RSA(index2)), + role1 << Backward, + role2 << Backward, + not(RSA.Congruent(role1.getArguments get 2, role2.getArguments get 2)) + ) + + /** Recursively propagates `rsa:ID` predicate. + * + * @note corresponds to rules 5x in Table 3. + */ + val r5a = for { + role1 <- query.atoms filter (_.isRoleAssertion) + r1arg0 = role1.getArguments get 0 + if query.bounded contains r1arg0 + r1arg2 = role1.getArguments get 2 + if query.bounded contains r1arg2 + role2 <- query.atoms filter (_.isRoleAssertion) + r2arg0 = role2.getArguments get 0 + if query.bounded contains r2arg0 + r2arg2 = role2.getArguments get 2 + if query.bounded contains r2arg2 + } yield Rule.create( + RSA.ID( + RSA(query.bounded indexOf r1arg0), + RSA(query.bounded indexOf r2arg0) + ), + RSA.ID( + RSA(query.bounded indexOf r1arg2), + RSA(query.bounded indexOf r2arg2) + ), + RSA.Congruent(r1arg0, r2arg0), + role1 << Forward, + role2 << Forward, + not(RSA.NI(r1arg0)) + ) + val r5b = for { + role1 <- query.atoms filter (_.isRoleAssertion) + r1arg0 = role1.getArguments get 0 + if query.bounded contains r1arg0 + r1arg2 = role1.getArguments get 2 + if query.bounded contains r1arg2 + role2 <- query.atoms filter (_.isRoleAssertion) + r2arg0 = role2.getArguments get 0 + if query.bounded contains r2arg0 + r2arg2 = role2.getArguments get 2 + if query.bounded contains r2arg2 + } yield Rule.create( + RSA.ID( + RSA(query.bounded indexOf r1arg0), + RSA(query.bounded indexOf r2arg2) + ), + RSA.ID( + RSA(query.bounded indexOf r1arg2), + RSA(query.bounded indexOf r2arg0) + ), + RSA.Congruent(r1arg0, r2arg2), + role1 << Forward, + role2 << Backward, + not(RSA.NI(r1arg0)) + ) + val r5c = for { + role1 <- query.atoms filter (_.isRoleAssertion) + r1arg0 = role1.getArguments get 0 + if query.bounded contains r1arg0 + r1arg2 = role1.getArguments get 2 + if query.bounded contains r1arg2 + role2 <- query.atoms filter (_.isRoleAssertion) + r2arg0 = role2.getArguments get 0 + if query.bounded contains r2arg0 + r2arg2 = role2.getArguments get 2 + if query.bounded contains r2arg2 + } yield Rule.create( + RSA.ID( + RSA(query.bounded indexOf r1arg2), + RSA(query.bounded indexOf r2arg2) + ), + RSA.ID( + RSA(query.bounded indexOf r1arg0), + RSA(query.bounded indexOf r2arg0) + ), + RSA.Congruent(r1arg2, r2arg2), + role1 << Backward, + role2 << Backward, + not(RSA.NI(r1arg2)) + ) + + /** Detect cycles in the canonical model. + * + * Cycles are detected by introducing a new predicate `rsa:AQ` + * and computing its transitive closure. Cycles are computed from + * forward and backward roles separately. + * + * @note corresponds to rules 6,7x in Table 3. + */ + val r6 = for { + role <- query.atoms filter (_.isRoleAssertion) + index0 = query.bounded indexOf (role.getArguments get 0) + if index0 >= 0 + index2 = query.bounded indexOf (role.getArguments get 2) + if index2 >= 0 + suffix <- Seq(Forward, Backward) + } yield Rule.create( + RSA.AQ(varV, varW, suffix), + role << suffix, + RSA.ID(RSA(index0), varV), + RSA.ID(RSA(index2), varW) + ) + val r7a = + for (suffix <- List(Forward, Backward)) + yield Rule.create( + RSA.TQ(varU, varV, suffix), + RSA.AQ(varU, varV, suffix) + ) + val r7b = + for (suffix <- List(Forward, Backward)) + yield Rule.create( + RSA.TQ(varU, varW, suffix), + RSA.AQ(varU, varV, suffix), + RSA.TQ(varV, varW, suffix) + ) + + /** Flag spurious answers. + * + * @note corresponds to rules 8x in Table 3. + */ + val r8a = + for (v <- query.answer) + yield Rule.create(RSA.SP, RSA.QM, not(RSA.Named(v))) + val r8b = Rule.create(RSA.SP, RSA.FK) + val r8c = + for (suffix <- List(Forward, Backward)) + yield Rule.create( + RSA.SP, + RSA.TQ(varV, varV, suffix) + ) + + /** Determine answers to the query + * + * Answers are identified by predicate `rsa:Ans`. In case the + * input query is a BCQ (answer is just true/false), we derive + * `rsa:Ans` for a fresh constant `c`. Later on we can query for + * instances of `rsa:Ans` as follows + * + * {{{ + * ASK { ?X a rsa:Ans } + * }}} + * + * to determine whether the query is true or false. + * + * @note corresponds to rule 9 in Table 3. + */ + val r9 = Rule.create(RSA.Ans, RSA.QM, not(RSA.SP)) + + (r1 :: + r3a ::: r3b :: r3c :: + r4a ::: r4b ::: r4c ::: + r5a ::: r5b ::: r5c ::: + r6 ::: r7b ::: r7a ::: + r8a ::: r8b :: r8c ::: + r9 :: List()) map RDFoxUtil.reify + } +} diff --git a/src/main/scala/uk/ac/ox/cs/rsacomb/util/Versioned.scala b/src/main/scala/uk/ac/ox/cs/rsacomb/util/Versioned.scala new file mode 100644 index 0000000..aa2a963 --- /dev/null +++ b/src/main/scala/uk/ac/ox/cs/rsacomb/util/Versioned.scala @@ -0,0 +1,18 @@ +package uk.ac.ox.cs.rsacomb.util + +/** Utility to allow hussle free version switching of blocks of code + * + * This allows for example testing different implementations of a + * module or algorithm. + */ +trait Versioned[T] { + + /** Type of the returned versioned object */ + type Result + + /** Returns correct instance of the versioned object + * + * @param t object uniquely identifing the requested instance. + */ + def apply(t: T): Result +} diff --git a/src/test/scala/uk/ac/ox/cs/rsacomb/FilteringProgramSpecs.scala b/src/test/scala/uk/ac/ox/cs/rsacomb/FilteringProgramSpecs.scala deleted file mode 100644 index 32ef8da..0000000 --- a/src/test/scala/uk/ac/ox/cs/rsacomb/FilteringProgramSpecs.scala +++ /dev/null @@ -1,92 +0,0 @@ -package uk.ac.ox.cs.rsacomb - -import org.scalatest.flatspec.AnyFlatSpec -import org.scalatest.matchers.should.Matchers -import tech.oxfordsemantic.jrdfox.logic.expression.IRI -import uk.ac.ox.cs.rsacomb.FilteringProgram -import uk.ac.ox.cs.rsacomb.sparql.ConjunctiveQuery - -object FilteringProgramSpec { - - val constants = - List(IRI.create("_:iri1"), IRI.create("_:iri2"), IRI.create("_:iri3")) - - val cq0 = """ - PREFIX : - - SELECT ?X - WHERE { - ?X a :D ; - :R ?Y . - ?Y :S ?Z . - ?Z a :D . - } - """ - - val cq1 = """ - PREFIX : - - SELECT * - WHERE { - ?X a :D ; - :R ?Y . - ?Y :S ?Z . - ?Z a :D . - } - """ - - val cq2 = """ - PREFIX : - - SELECT ?X - WHERE { - ?X a :D ; - :R ?Y . - ?Y :S ?Z . - ?Y :T ?W . - ?Z a :D . - ?W a :D - } - """ - - val bcq0 = """ - PREFIX : - - ASK { - ?X a :D ; - :R ?Y . - ?Y :S ?Z . - ?Z a :D . - } - """ -} - -class FilteringProgramSpec extends AnyFlatSpec with Matchers { - - import FilteringProgramSpec._ - - "CQ 0" should "generate 27 rules and 3 facts" in { - val cq = ConjunctiveQuery.parse(cq0).get - val filter = FilteringProgram(cq) - filter.rules should have length 27 - } - - "CQ 1" should "generate 15 rules" in { - val cq = ConjunctiveQuery.parse(cq1).get - val filter = FilteringProgram(cq) - filter.rules should have length 15 - } - - "CQ 2" should "generate 51 rules" in { - val cq = ConjunctiveQuery.parse(cq2).get - val filter = FilteringProgram(cq) - filter.rules should have length 51 - } - - "BCQ 0" should "generate 46 rules" in { - val cq = ConjunctiveQuery.parse(bcq0).get - val filter = FilteringProgram(cq) - filter.rules should have length 43 - } - -} diff --git a/src/test/scala/uk/ac/ox/cs/rsacomb/SuiteAll.scala b/src/test/scala/uk/ac/ox/cs/rsacomb/SuiteAll.scala index 2162f8c..f32c088 100644 --- a/src/test/scala/uk/ac/ox/cs/rsacomb/SuiteAll.scala +++ b/src/test/scala/uk/ac/ox/cs/rsacomb/SuiteAll.scala @@ -2,16 +2,25 @@ package uk.ac.ox.cs.rsacomb import org.scalatest.Suites -import uk.ac.ox.cs.rsacomb.converter.{OWLAxiomSpec, OWLClassSpec, RDFoxConverterSpec} -import uk.ac.ox.cs.rsacomb.sparql.{ConjunctiveQueryAnswerSpec, ConjunctiveQuerySpec} +import uk.ac.ox.cs.rsacomb.converter.{ + OWLAxiomSpec, + OWLClassSpec, + RDFoxConverterSpec +} +import uk.ac.ox.cs.rsacomb.filtering.NaiveFilteringProgramSpec +import uk.ac.ox.cs.rsacomb.sparql.{ + ConjunctiveQueryAnswerSpec, + ConjunctiveQuerySpec +} -class SuiteAll extends Suites ( - new Ontology1_CanonicalModelSpec, - new Ontology2_CanonicalModelSpec, - new FilteringProgramSpec, - new OWLAxiomSpec, - new OWLClassSpec, - new RDFoxConverterSpec, - new ConjunctiveQueryAnswerSpec, - new ConjunctiveQuerySpec -) +class SuiteAll + extends Suites( + new Ontology1_CanonicalModelSpec, + new Ontology2_CanonicalModelSpec, + new NaiveFilteringProgramSpec, + new OWLAxiomSpec, + new OWLClassSpec, + new RDFoxConverterSpec, + new ConjunctiveQueryAnswerSpec, + new ConjunctiveQuerySpec + ) diff --git a/src/test/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgramSpecs.scala b/src/test/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgramSpecs.scala new file mode 100644 index 0000000..372b78c --- /dev/null +++ b/src/test/scala/uk/ac/ox/cs/rsacomb/filtering/FilteringProgramSpecs.scala @@ -0,0 +1,94 @@ +package uk.ac.ox.cs.rsacomb.filtering + +import org.scalatest.flatspec.AnyFlatSpec +import org.scalatest.matchers.should.Matchers +import tech.oxfordsemantic.jrdfox.logic.expression.IRI +import uk.ac.ox.cs.rsacomb.filtering.{FilteringProgram, FilterType} +import uk.ac.ox.cs.rsacomb.sparql.ConjunctiveQuery + +object NaiveFilteringProgramSpec { + + val naive: FilterType = FilterType.FILTER_NAIVE + + val constants = + List(IRI.create("_:iri1"), IRI.create("_:iri2"), IRI.create("_:iri3")) + + val cq0 = """ + PREFIX : + + SELECT ?X + WHERE { + ?X a :D ; + :R ?Y . + ?Y :S ?Z . + ?Z a :D . + } + """ + + val cq1 = """ + PREFIX : + + SELECT * + WHERE { + ?X a :D ; + :R ?Y . + ?Y :S ?Z . + ?Z a :D . + } + """ + + val cq2 = """ + PREFIX : + + SELECT ?X + WHERE { + ?X a :D ; + :R ?Y . + ?Y :S ?Z . + ?Y :T ?W . + ?Z a :D . + ?W a :D + } + """ + + val bcq0 = """ + PREFIX : + + ASK { + ?X a :D ; + :R ?Y . + ?Y :S ?Z . + ?Z a :D . + } + """ +} + +class NaiveFilteringProgramSpec extends AnyFlatSpec with Matchers { + + import NaiveFilteringProgramSpec._ + + "CQ 0" should "generate 27 rules and 3 facts" in { + val cq = ConjunctiveQuery.parse(cq0).get + val filter = FilteringProgram(naive)(cq) + filter.rules should have length 27 + } + + "CQ 1" should "generate 15 rules" in { + val cq = ConjunctiveQuery.parse(cq1).get + val filter = FilteringProgram(naive)(cq) + filter.rules should have length 15 + } + + "CQ 2" should "generate 51 rules" in { + val cq = ConjunctiveQuery.parse(cq2).get + val filter = FilteringProgram(naive)(cq) + filter.rules should have length 51 + } + + "BCQ 0" should "generate 46 rules" in { + val cq = ConjunctiveQuery.parse(bcq0).get + val filter = FilteringProgram(naive)(cq) + filter.rules should have length 43 + } + +} -- cgit v1.2.3