From 0c2726db44b562cbda9bfa87e76d829927c31ec8 Mon Sep 17 00:00:00 2001 From: RncLsn Date: Tue, 12 May 2015 18:48:56 +0100 Subject: Added classes for implementing new upper store (Limited Skolemisation). Started implementation of the new classes. --- .../ox/cs/pagoda/multistage/ExistApproximator.java | 15 - .../multistage/ExistConstantApproximator.java | 23 -- .../LimitedSkolemisationApplication.java | 7 +- .../LimitedSkolemisationApproximator.java | 36 -- .../pagoda/multistage/MultiStageQueryEngine.java | 10 +- .../pagoda/multistage/MultiStageUpperProgram.java | 387 ++++++++++----------- .../pagoda/multistage/RestrictedApplication.java | 101 +++--- .../treatement/Pick4NegativeConcept.java | 73 ++-- .../ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java | 129 +++---- .../cs/pagoda/rules/ExistConstantApproximator.java | 23 ++ .../rules/LimitedSkolemisationApproximator.java | 72 ++++ src/uk/ac/ox/cs/pagoda/rules/OverApproxExist.java | 104 +++--- .../pagoda/rules/TupleDependentApproximator.java | 16 + src/uk/ac/ox/cs/pagoda/util/SparqlHelper.java | 49 +-- 14 files changed, 521 insertions(+), 524 deletions(-) delete mode 100644 src/uk/ac/ox/cs/pagoda/multistage/ExistApproximator.java delete mode 100644 src/uk/ac/ox/cs/pagoda/multistage/ExistConstantApproximator.java delete mode 100644 src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApproximator.java create mode 100644 src/uk/ac/ox/cs/pagoda/rules/ExistConstantApproximator.java create mode 100644 src/uk/ac/ox/cs/pagoda/rules/LimitedSkolemisationApproximator.java create mode 100644 src/uk/ac/ox/cs/pagoda/rules/TupleDependentApproximator.java diff --git a/src/uk/ac/ox/cs/pagoda/multistage/ExistApproximator.java b/src/uk/ac/ox/cs/pagoda/multistage/ExistApproximator.java deleted file mode 100644 index 0ee2035..0000000 --- a/src/uk/ac/ox/cs/pagoda/multistage/ExistApproximator.java +++ /dev/null @@ -1,15 +0,0 @@ -package uk.ac.ox.cs.pagoda.multistage; - -import org.semanticweb.HermiT.model.DLClause; - -import java.util.Collection; - -/** - * An approximator for existential rules. - * */ -public interface ExistApproximator { - - Collection convert(DLClause clause, - DLClause originalClause, - Collection violationTuples); -} diff --git a/src/uk/ac/ox/cs/pagoda/multistage/ExistConstantApproximator.java b/src/uk/ac/ox/cs/pagoda/multistage/ExistConstantApproximator.java deleted file mode 100644 index 5df66bc..0000000 --- a/src/uk/ac/ox/cs/pagoda/multistage/ExistConstantApproximator.java +++ /dev/null @@ -1,23 +0,0 @@ -package uk.ac.ox.cs.pagoda.multistage; - -import org.semanticweb.HermiT.model.DLClause; -import uk.ac.ox.cs.pagoda.rules.OverApproxExist; - -import java.util.Collection; - -/** - * A wrapper for OverApproxExist. - * */ -public class ExistConstantApproximator implements ExistApproximator { - - private final OverApproxExist overApproxExist; - - public ExistConstantApproximator() { - overApproxExist = new OverApproxExist(); - } - - @Override - public Collection convert(DLClause clause, DLClause originalClause, Collection violationTuples) { - return overApproxExist.convert(clause, originalClause); - } -} diff --git a/src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApplication.java b/src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApplication.java index b0068e7..13752a3 100644 --- a/src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApplication.java +++ b/src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApplication.java @@ -2,15 +2,16 @@ package uk.ac.ox.cs.pagoda.multistage; import uk.ac.ox.cs.pagoda.constraints.BottomStrategy; +import uk.ac.ox.cs.pagoda.rules.ExistConstantApproximator; +import uk.ac.ox.cs.pagoda.rules.LimitedSkolemisationApproximator; import uk.ac.ox.cs.pagoda.rules.Program; public class LimitedSkolemisationApplication extends RestrictedApplication { + public static final int MAX_DEPTH = 1; public LimitedSkolemisationApplication(Program program, BottomStrategy upperBottom) { super(program, upperBottom); + m_approxExist = new LimitedSkolemisationApproximator(MAX_DEPTH, new ExistConstantApproximator()); } - - - // TODO override methods properly } diff --git a/src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApproximator.java b/src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApproximator.java deleted file mode 100644 index 348e849..0000000 --- a/src/uk/ac/ox/cs/pagoda/multistage/LimitedSkolemisationApproximator.java +++ /dev/null @@ -1,36 +0,0 @@ -package uk.ac.ox.cs.pagoda.multistage; - -import org.semanticweb.HermiT.model.DLClause; - -import java.util.Collection; - -/** - * Approximates existential rules by a limited form of Skolemisation. - *

- * Given a rule and a grounding substitution, - * it Skolemises the rule if - * all the terms in the substitution have depth less than a given depth, - * otherwise it approximates using an alternative ExistApproximator. - * - * */ -public class LimitedSkolemisationApproximator implements ExistApproximator { - - private final int maxTermDepth; - private final ExistApproximator alternativeApproximator; - - public LimitedSkolemisationApproximator(int maxTermDepth) { - this(maxTermDepth, new ExistConstantApproximator()); - } - - public LimitedSkolemisationApproximator(int maxTermDepth, ExistApproximator alternativeApproximator) { - this.maxTermDepth = maxTermDepth; - this.alternativeApproximator = alternativeApproximator; - } - - @Override - public Collection convert(DLClause clause, - DLClause originalClause, - Collection violationTuples) { - return null; - } -} diff --git a/src/uk/ac/ox/cs/pagoda/multistage/MultiStageQueryEngine.java b/src/uk/ac/ox/cs/pagoda/multistage/MultiStageQueryEngine.java index 7e40faf..f0f631a 100644 --- a/src/uk/ac/ox/cs/pagoda/multistage/MultiStageQueryEngine.java +++ b/src/uk/ac/ox/cs/pagoda/multistage/MultiStageQueryEngine.java @@ -69,11 +69,11 @@ public class MultiStageQueryEngine extends StageQueryEngine { // TODO to be removed ... // if (gap == null) // program.save("output/multi.dlog"); - - Collection violations = null; + + Collection violations; int iteration = 0; - Timer subTimer = new Timer(); - boolean incrementally = false; + Timer subTimer = new Timer(); + boolean incrementally; try { while (true) { long oldTripleCount = store.getTriplesCount(); @@ -106,7 +106,7 @@ public class MultiStageQueryEngine extends StageQueryEngine { if (!isValid()) { if (iteration == 1) { - Utility.logInfo("The ontology is incosistent."); + Utility.logInfo("The ontology is inconsistent."); return -1; } Utility.logInfo(name + " store FAILED for multi-stage materialisation in " + t.duration() + " seconds."); diff --git a/src/uk/ac/ox/cs/pagoda/multistage/MultiStageUpperProgram.java b/src/uk/ac/ox/cs/pagoda/multistage/MultiStageUpperProgram.java index daf7c2c..acaf167 100644 --- a/src/uk/ac/ox/cs/pagoda/multistage/MultiStageUpperProgram.java +++ b/src/uk/ac/ox/cs/pagoda/multistage/MultiStageUpperProgram.java @@ -7,8 +7,10 @@ import uk.ac.ox.cs.pagoda.MyPrefixes; import uk.ac.ox.cs.pagoda.constraints.BottomStrategy; import uk.ac.ox.cs.pagoda.hermit.RuleHelper; import uk.ac.ox.cs.pagoda.reasoner.light.RDFoxTripleManager; +import uk.ac.ox.cs.pagoda.rules.ExistConstantApproximator; import uk.ac.ox.cs.pagoda.rules.OverApproxExist; import uk.ac.ox.cs.pagoda.rules.Program; +import uk.ac.ox.cs.pagoda.rules.TupleDependentApproximator; import uk.ac.ox.cs.pagoda.util.Namespace; import uk.ac.ox.cs.pagoda.util.SparqlHelper; import uk.ac.ox.cs.pagoda.util.Timer; @@ -18,212 +20,264 @@ import java.io.*; import java.util.*; public abstract class MultiStageUpperProgram { - - Set constraints = new HashSet(); - Set rules = new HashSet(); - Collection clauses; - BottomStrategy m_bottom = null; - ExistApproximator m_approxExist = new ExistConstantApproximator(); - - protected static final Variable X = Variable.create("X"); - + protected static final Variable X = Variable.create("X"); + Set constraints = new HashSet(); + Set rules = new HashSet(); + Collection clauses; + BottomStrategy m_bottom = null; + TupleDependentApproximator m_approxExist = new ExistConstantApproximator(); + Map map = new HashMap(); + Set updatedPredicates = new HashSet(); private MyPrefixes prefixes = MyPrefixes.PAGOdAPrefixes; - Map map = new HashMap(); + private StringBuilder datalogRuleText = new StringBuilder(); + private Timer t = new Timer(); public MultiStageUpperProgram(Program program, BottomStrategy upperBottom) { - m_bottom = upperBottom; + m_bottom = upperBottom; clauses = getInitialClauses(program); Collection introducedConstraints = new LinkedList(); - LinkedList newHeadAtoms = new LinkedList(); + LinkedList newHeadAtoms = new LinkedList(); for (DLClause clause: m_bottom.process(clauses)) { - if (m_bottom.isBottomRule(clause) || clause.getHeadLength() == 1 && !(clause.getHeadAtom(0).getDLPredicate() instanceof AtLeast)) - addDatalogRule(clause); + if (m_bottom.isBottomRule(clause) || clause.getHeadLength() == 1 && !(clause.getHeadAtom(0).getDLPredicate() instanceof AtLeast)) + addDatalogRule(clause); else { - newHeadAtoms.clear(); - boolean changed = false; + newHeadAtoms.clear(); + boolean changed = false; for (Atom atom: clause.getHeadAtoms()) { if (atom.getDLPredicate() instanceof AtLeastConcept) { - AtLeastConcept atLeast = (AtLeastConcept) atom.getDLPredicate(); + AtLeastConcept atLeast = (AtLeastConcept) atom.getDLPredicate(); if (atLeast.getToConcept() instanceof AtomicNegationConcept) { - AtomicConcept positive = ((AtomicNegationConcept) atLeast.getToConcept()).getNegatedAtomicConcept(); - AtomicConcept negative = OverApproxExist.getNegationConcept(positive); + AtomicConcept positive = ((AtomicNegationConcept) atLeast.getToConcept()).getNegatedAtomicConcept(); + AtomicConcept negative = OverApproxExist.getNegationConcept(positive); Atom atom1 = Atom.create(positive, X); Atom atom2 = Atom.create(negative, X); - introducedConstraints.add(DLClause.create(new Atom[0], new Atom[] {atom1, atom2})); - newHeadAtoms.add( + introducedConstraints.add(DLClause.create(new Atom[0], new Atom[]{atom1, atom2})); + newHeadAtoms.add( Atom.create( - AtLeastConcept.create(atLeast.getArity(), atLeast.getOnRole(), negative), + AtLeastConcept.create(atLeast.getArity(), atLeast.getOnRole(), negative), atom.getArgument(0))); - changed = true; - continue; + changed = true; + continue; } } else if (atom.getDLPredicate() instanceof AtLeastDataRange) - changed = true; - else + changed = true; + else newHeadAtoms.add(atom); - + } if (!changed) constraints.add(clause); else if (!newHeadAtoms.isEmpty()) { - DLClause newClause = DLClause.create(newHeadAtoms.toArray(new Atom[0]), clause.getBodyAtoms()); - map.put(newClause, getOriginalClause(clause)); - constraints.add(newClause); + DLClause newClause = DLClause.create(newHeadAtoms.toArray(new Atom[0]), clause.getBodyAtoms()); + map.put(newClause, getOriginalClause(clause)); + constraints.add(newClause); } } } - + for (DLClause clause: m_bottom.process(introducedConstraints)) addDatalogRule(clause); } - protected void addDatalogRule(DLClause clause) { - rules.add(clause); - datalogRuleText.append(RuleHelper.getText(clause)).append(Utility.LINE_SEPARATOR); - } - public static Atom getNegativeAtom(Atom atom) { - if (atom.getDLPredicate() instanceof AtomicConcept) + if (atom.getDLPredicate() instanceof AtomicConcept) return Atom.create(OverApproxExist.getNegationConcept(atom.getDLPredicate()), atom.getArgument(0)); - + if (atom.getDLPredicate() instanceof Inequality) - return Atom.create(Equality.INSTANCE, atom.getArgument(0), atom.getArgument(1)); - + return Atom.create(Equality.INSTANCE, atom.getArgument(0), atom.getArgument(1)); + if (atom.getDLPredicate() instanceof Equality || atom.getDLPredicate() instanceof AnnotatedEquality) - return Atom.create(Inequality.INSTANCE, atom.getArgument(0), atom.getArgument(1)); - + return Atom.create(Inequality.INSTANCE, atom.getArgument(0), atom.getArgument(1)); + return null; } - - private StringBuilder datalogRuleText = new StringBuilder(); + + public static AnswerTupleID project(AnswerTupleID tuple, String[] vars, String[] subVars) { + int subArity = 0; + for (int i = 0; i < subVars.length; ++i) + if (subVars[i] != null) ++subArity; + + if (tuple.getArity() == subArity) + return tuple; + + AnswerTupleID newTuple = new AnswerTupleID(subArity); + for (int i = 0, j = 0; i < vars.length; ++i) + if (subVars[i] != null && !subVars[i].isEmpty()) { + newTuple.setTerm(j++, tuple.getTerm(i)); + } + + return newTuple; + } + + public static String[] getVarSubset(String[] vars, Atom... atoms) { + String[] newVars = new String[vars.length]; + Set allVars = new HashSet(); + int arity; + for (Atom atom : atoms) { + arity = atom.getArity(); + if (atom.getDLPredicate() instanceof AnnotatedEquality) arity = 2; + for (int j = 0; j < arity; ++j) + if (atom.getArgument(j) instanceof Variable) { + allVars.add(atom.getArgumentVariable(j)); + } + } + + for (int i = 0; i < vars.length; ++i) { + newVars[i] = allVars.contains(Variable.create(vars[i])) ? vars[i] : null; + } + + return newVars; + } + + public static String[] getCommonVars(DLClause clause) { + Set headVars = getVariables(clause.getHeadAtoms()); + Set bodyVars = getVariables(clause.getBodyAtoms()); + + Collection common = new LinkedList(); + for (Variable v : headVars) + if (bodyVars.contains(v)) common.add(v.getName()); + + return common.toArray(new String[0]); + } + + public static Set getVariables(Atom[] atoms) { + Set v = new HashSet(); + for (Atom atom : atoms) atom.getVariables(v); + return v; + } + + protected void addDatalogRule(DLClause clause) { + rules.add(clause); + datalogRuleText.append(RuleHelper.getText(clause)).append(Utility.LINE_SEPARATOR); + } public String getDatalogRuleText() { - StringBuilder program = new StringBuilder(); + StringBuilder program = new StringBuilder(); program.append(prefixes.prefixesText()); - program.append(datalogRuleText.toString()); + program.append(datalogRuleText.toString()); return program.toString(); } protected void addDerivedPredicate(MultiStageQueryEngine engine) { - TupleIterator derivedTuples = null; + TupleIterator derivedTuples = null; try { - derivedTuples = engine.internal_evaluateAgainstIDBs("select distinct ?z where { ?x <" + Namespace.RDF_TYPE + "> ?z . }"); + derivedTuples = engine.internal_evaluateAgainstIDBs("select distinct ?z where { ?x <" + Namespace.RDF_TYPE + "> ?z . }"); for (long multi = derivedTuples.open(); multi != 0; multi = derivedTuples.getNext()) { String p = prefixes.expandIRI(RDFoxTripleManager.getQuotedTerm(derivedTuples.getResource(0))); - updatedPredicates.add(AtomicConcept.create(p)); + updatedPredicates.add(AtomicConcept.create(p)); } } catch (JRDFStoreException e) { e.printStackTrace(); } finally { - if (derivedTuples != null) derivedTuples.dispose(); + if (derivedTuples != null) derivedTuples.dispose(); } - - derivedTuples = null; + + derivedTuples = null; try { - derivedTuples = engine.internal_evaluateAgainstIDBs("select distinct ?y where { ?x ?y ?z . }"); + derivedTuples = engine.internal_evaluateAgainstIDBs("select distinct ?y where { ?x ?y ?z . }"); for (long multi = derivedTuples.open(); multi != 0; multi = derivedTuples.getNext()) { - String p = RDFoxTripleManager.getQuotedTerm(derivedTuples.getResource(0)); + String p = RDFoxTripleManager.getQuotedTerm(derivedTuples.getResource(0)); if (p.equals(Namespace.RDF_TYPE_ABBR) || p.equals(Namespace.RDF_TYPE_QUOTED)) ; else if (p.equals(Namespace.EQUALITY_ABBR) || p.equals(Namespace.EQUALITY_QUOTED)); - else updatedPredicates.add(AtomicRole.create(prefixes.expandIRI(p))); + else updatedPredicates.add(AtomicRole.create(prefixes.expandIRI(p))); } } catch (JRDFStoreException e) { e.printStackTrace(); } finally { - if (derivedTuples != null) derivedTuples.dispose(); + if (derivedTuples != null) derivedTuples.dispose(); } } public abstract Collection isIntegrated(MultiStageQueryEngine engine, boolean incrementally); - + protected Violation violate(MultiStageQueryEngine engine, DLClause clause, boolean incrementally) { Utility.logTrace("checking constraint: " + clause); - - String[] vars = getCommonVars(clause), subVars; - + + String[] vars = getCommonVars(clause), subVars; + Set headAnswers = new HashSet(); Set rootAnswers = new HashSet(); - + Set restHeadAtoms = new HashSet(); - Atom rootAtom = null; + Atom rootAtom = null; for (Atom atom: clause.getHeadAtoms()) - if (rootAtom == null && atom.getDLPredicate() instanceof AtomicConcept && atom.getArgument(0).equals(X)) - rootAtom = atom; - else - restHeadAtoms.add(atom); + if (rootAtom == null && atom.getDLPredicate() instanceof AtomicConcept && atom.getArgument(0).equals(X)) + rootAtom = atom; + else + restHeadAtoms.add(atom); if (rootAtom != null) { - subVars = getVarSubset(vars, rootAtom); + subVars = getVarSubset(vars, rootAtom); getHeadAnswers(engine, rootAtom, subVars, headAnswers); - for (AnswerTupleID tuple: headAnswers) rootAnswers.add(tuple.getTerm(0)); + for (AnswerTupleID tuple : headAnswers) rootAnswers.add(tuple.getTerm(0)); headAnswers.clear(); } - + if (incrementally) { - boolean affected = false; + boolean affected = false; for (Atom bodyAtom: clause.getBodyAtoms()) if (updatedPredicates.contains(bodyAtom.getDLPredicate())) { - affected = true; - break; + affected = true; + break; } - + for (Atom headAtom: clause.getHeadAtoms()) - if (headAtom.getDLPredicate() instanceof AtLeastConcept && + if (headAtom.getDLPredicate() instanceof AtLeastConcept && ((AtomicConcept) ((AtLeastConcept) headAtom.getDLPredicate()).getToConcept()).getIRI().endsWith("_neg")) if (updatedPredicates.contains(OverApproxExist.getNegationConcept(((AtomicConcept) ((AtLeastConcept) headAtom.getDLPredicate()).getToConcept())))) { - affected = true; - break; + affected = true; + break; } - + if (!affected) return null; } - - LinkedList bodyAnswers = getBodyAnswers(engine, clause, vars, rootAnswers); + + LinkedList bodyAnswers = getBodyAnswers(engine, clause, vars, rootAnswers); rootAnswers.clear(); - + Utility.logTrace("Time to compute body answers: " + t.duration() + " number: " + bodyAnswers.size()); - + if (bodyAnswers.isEmpty()) return null; - + t.reset(); - + for (Atom headAtom: restHeadAtoms) { -// Timer subTimer = new Timer(); - subVars = getVarSubset(vars, headAtom); - +// Timer subTimer = new Timer(); + subVars = getVarSubset(vars, headAtom); + // TODO: conditions check negative existential restrictions // if (false) { - if (headAtom.getDLPredicate() instanceof AtLeastConcept && + if (headAtom.getDLPredicate() instanceof AtLeastConcept && ((AtomicConcept) ((AtLeastConcept) headAtom.getDLPredicate()).getToConcept()).getIRI().endsWith("_neg")) { - AtLeastConcept alc = (AtLeastConcept) headAtom.getDLPredicate(); - String x = null, y = "Y"; + AtLeastConcept alc = (AtLeastConcept) headAtom.getDLPredicate(); + String x = null, y = "Y"; for (String var: subVars) if (var != null) x = var; - if (x == "Y") y = "X"; + if (x == "Y") y = "X"; Atom[] atoms = new Atom[2]; - if (alc.getOnRole() instanceof AtomicRole) + if (alc.getOnRole() instanceof AtomicRole) atoms[0] = Atom.create((AtomicRole) alc.getOnRole(), Variable.create(x), Variable.create(y)); - else + else atoms[0] = Atom.create(((InverseRole) alc.getOnRole()).getInverseOf(), Variable.create(y), Variable.create(x)); - + atoms[1] = Atom.create(OverApproxExist.getNegationConcept((AtomicConcept) ((AtLeastConcept) headAtom.getDLPredicate()).getToConcept()), Variable.create(y)); - Set addAnswers = new HashSet(); - TupleIterator tuples = null; + Set addAnswers = new HashSet(); + TupleIterator tuples = null; try { - tuples = engine.internal_evaluateNotExpanded(SparqlHelper.getSPARQLQuery(new Atom[] {atoms[0]}, x, y)); - for (long multi = tuples.open(); multi != 0; multi = tuples.getNext()) + tuples = engine.internal_evaluateNotExpanded(SparqlHelper.getSPARQLQuery(new Atom[]{atoms[0]}, x, y)); + for (long multi = tuples.open(); multi != 0; multi = tuples.getNext()) addAnswers.add(new AnswerTupleID(tuples)); } catch (JRDFStoreException e) { e.printStackTrace(); } finally { if (tuples != null) tuples.dispose(); } - - tuples = null; + + tuples = null; try { - tuples = engine.internal_evaluateNotExpanded(SparqlHelper.getSPARQLQuery(atoms, x, y)); - for (long multi = tuples.open(); multi != 0; multi = tuples.getNext()) + tuples = engine.internal_evaluateNotExpanded(SparqlHelper.getSPARQLQuery(atoms, x, y)); + for (long multi = tuples.open(); multi != 0; multi = tuples.getNext()) addAnswers.remove(new AnswerTupleID(tuples)); } catch (JRDFStoreException e) { e.printStackTrace(); @@ -235,140 +289,87 @@ public abstract class MultiStageUpperProgram { headAnswers.add(project(tuple, new String[] {x, y}, new String[] {x, null})); addAnswers.clear(); } - - getHeadAnswers(engine, headAtom, subVars, headAnswers); - for (Iterator iter = bodyAnswers.iterator(); iter.hasNext(); ) + + getHeadAnswers(engine, headAtom, subVars, headAnswers); + for (Iterator iter = bodyAnswers.iterator(); iter.hasNext(); ) if (headAnswers.contains(project(iter.next(), vars, subVars))) iter.remove(); headAnswers.clear(); } - + Utility.logTrace("Time to rule out all head answers: " + t.duration() + " rest number: " + bodyAnswers.size()); if (bodyAnswers.isEmpty()) return null; - - return new Violation(clause, bodyAnswers, vars); + + return new Violation(clause, bodyAnswers, vars); } private void getHeadAnswers(MultiStageQueryEngine engine, Atom headAtom, String[] commonVars, Set headAnswers) { - String headQuery = SparqlHelper.getSPARQLQuery(new Atom[] { headAtom }, commonVars); - TupleIterator tuples = null; + String headQuery = SparqlHelper.getSPARQLQuery(new Atom[]{headAtom}, commonVars); + TupleIterator tuples = null; try { - tuples = engine.internal_evaluateNotExpanded(headQuery); - for (long multi = tuples.open(); multi != 0; multi = tuples.getNext()) + tuples = engine.internal_evaluateNotExpanded(headQuery); + for (long multi = tuples.open(); multi != 0; multi = tuples.getNext()) headAnswers.add(new AnswerTupleID(tuples)); } catch (JRDFStoreException e) { e.printStackTrace(); } finally { if (tuples != null) tuples.dispose(); - } + } } - private Timer t = new Timer(); - protected LinkedList getBodyAnswers(MultiStageQueryEngine engine, DLClause clause, String[] vars, Set rootAnswers) { //, boolean incrementally) { Collection validIndexes = new LinkedList(); - - int rootVarIndex = -1; + + int rootVarIndex = -1; for (int i = 0; i < vars.length; ++i) - if (vars[i].equals("X")) { rootVarIndex = i; break; } - - String[] subVars; + if (vars[i].equals("X")) { + rootVarIndex = i; + break; + } + + String[] subVars; for (Atom headAtom: clause.getHeadAtoms()) { if ((headAtom.getDLPredicate() instanceof Equality || headAtom.getDLPredicate() instanceof AnnotatedEquality) && headAtom.getArgument(0) instanceof Variable && headAtom.getArgument(1) instanceof Variable) { - int[] validIndex = new int[2]; - subVars = getVarSubset(vars, headAtom); + int[] validIndex = new int[2]; + subVars = getVarSubset(vars, headAtom); for (int i = 0, j = 0; i < subVars.length; ++i) if (subVars[i] != null) - validIndex[j++] = i; - validIndexes.add(validIndex); + validIndex[j++] = i; + validIndexes.add(validIndex); } } - + t.reset(); - + LinkedList bodyAnswers = new LinkedList(); String bodyQuery = SparqlHelper.getSPARQLQuery(clause.getBodyAtoms(), vars); TupleIterator bodyTuples = null; - - boolean filtered; + + boolean filtered; try { - bodyTuples = engine.internal_evaluateNotExpanded(bodyQuery); + bodyTuples = engine.internal_evaluateNotExpanded(bodyQuery); for (long multi = bodyTuples.open(); multi != 0; multi = bodyTuples.getNext()) { filtered = false; - if (rootVarIndex >= 0 && rootAnswers.contains(bodyTuples.getResourceID(rootVarIndex))) continue; + if (rootVarIndex >= 0 && rootAnswers.contains(bodyTuples.getResourceID(rootVarIndex))) continue; for (int[] validIndex: validIndexes) if (bodyTuples.getResourceID(validIndex[0]) == bodyTuples.getResourceID(validIndex[1])) { - filtered = true; - break; + filtered = true; + break; } if (!filtered) - bodyAnswers.add(new AnswerTupleID(bodyTuples)); + bodyAnswers.add(new AnswerTupleID(bodyTuples)); } } catch (JRDFStoreException e) { e.printStackTrace(); } finally { if (bodyTuples != null) bodyTuples.dispose(); } - - validIndexes.clear(); - Utility.logTrace("Time to get all body answers: " + t.duration()); - return bodyAnswers; - } - - public static AnswerTupleID project(AnswerTupleID tuple, String[] vars, String[] subVars) { - int subArity = 0; - for (int i = 0; i < subVars.length; ++i) - if (subVars[i] != null) ++subArity; - - if (tuple.getArity() == subArity) - return tuple; - - AnswerTupleID newTuple = new AnswerTupleID(subArity); - for (int i = 0, j = 0; i < vars.length; ++i) - if (subVars[i] != null && !subVars[i].isEmpty()) { - newTuple.setTerm(j++, tuple.getTerm(i)); - } - - return newTuple; - } - - public static String[] getVarSubset(String[] vars, Atom... atoms) { - String[] newVars = new String[vars.length]; - Set allVars = new HashSet(); - int arity; - for (Atom atom: atoms) { - arity = atom.getArity(); - if (atom.getDLPredicate() instanceof AnnotatedEquality) arity = 2; - for (int j = 0; j < arity; ++j) - if (atom.getArgument(j) instanceof Variable) { - allVars.add(atom.getArgumentVariable(j)); - } - } - - for (int i = 0; i < vars.length; ++i) { - newVars[i] = allVars.contains(Variable.create(vars[i])) ? vars[i] : null; - } - - return newVars; - } - - public static String[] getCommonVars(DLClause clause) { - Set headVars = getVariables(clause.getHeadAtoms()); - Set bodyVars = getVariables(clause.getBodyAtoms()); - Collection common = new LinkedList(); - for (Variable v: headVars) - if (bodyVars.contains(v)) common.add(v.getName()); - - return common.toArray(new String[0]); - } - - public static Set getVariables(Atom[] atoms) { - Set v = new HashSet(); - for (Atom atom: atoms) atom.getVariables(v); - return v; + validIndexes.clear(); + Utility.logTrace("Time to get all body answers: " + t.duration()); + return bodyAnswers; } public Collection convertExist(DLClause clause, DLClause originalDLClause) { @@ -376,11 +377,9 @@ public abstract class MultiStageUpperProgram { } public Collection convertExist(DLClause clause, DLClause originalDLClause, List violationTuples) { - return m_bottom.process(m_approxExist.convert(clause, originalDLClause, null)); + return m_bottom.process(m_approxExist.convert(clause, originalDLClause, violationTuples)); } - - public void save(String filename) { try { BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(filename))); @@ -395,11 +394,9 @@ public abstract class MultiStageUpperProgram { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); - } + } } - Set updatedPredicates = new HashSet(); - // public void addUpdatedPredicates(Set predicates) { // for (Iterator iter = predicates.iterator(); iter.hasNext(); ) { // updatedPredicate.add(iter.next()); diff --git a/src/uk/ac/ox/cs/pagoda/multistage/RestrictedApplication.java b/src/uk/ac/ox/cs/pagoda/multistage/RestrictedApplication.java index 174175f..b16e645 100644 --- a/src/uk/ac/ox/cs/pagoda/multistage/RestrictedApplication.java +++ b/src/uk/ac/ox/cs/pagoda/multistage/RestrictedApplication.java @@ -22,59 +22,48 @@ public class RestrictedApplication extends MultiStageUpperProgram { clauses.addAll(constraints); } - private void addNegativeDatalogRules() { - Collection allRules = new LinkedList(rules); - allRules.addAll(constraints); - for (DLClause clause: allRules) { - for (DLClause newClause: addAdditionalDatalogRules(clause, m_bottom, norm)) - addDatalogRule(newClause); - } - allRules.clear(); - } - - // It should be c-Skolemisation + shifting + // It should be shifting public static Collection addAdditionalDatalogRules(DLClause clause, BottomStrategy bottom, Normalisation norm) { - LinkedList newClauses = new LinkedList(); - Atom[] headAtoms = clause.getHeadAtoms(); - Atom[] bodyAtoms = clause.getBodyAtoms(); - int headLength = headAtoms.length; + LinkedList newClauses = new LinkedList(); + Atom[] headAtoms = clause.getHeadAtoms(); + Atom[] bodyAtoms = clause.getBodyAtoms(); + int headLength = headAtoms.length; int bodyLength = bodyAtoms.length; - DLClause tClause; - if (bottom.isBottomRule(clause)) { - if (clause.getBodyLength() == 1) return newClauses; + DLClause tClause; + if (bottom.isBottomRule(clause)) { + if (clause.getBodyLength() == 1) return newClauses; for (int i = 0; i < bodyLength; ++i) { if (bodyAtoms[i].getDLPredicate() instanceof AtomicConcept) { - AtomicConcept ac = (AtomicConcept) bodyAtoms[i].getDLPredicate(); + AtomicConcept ac = (AtomicConcept) bodyAtoms[i].getDLPredicate(); if (!ac.getIRI().endsWith("_exist")) { Atom[] newBodyAtoms = new Atom[bodyLength - 1]; for (int j = 0; j < bodyLength - 1; ++j) newBodyAtoms[j] = j < i ? bodyAtoms[j] : bodyAtoms[j + 1]; - + Atom negativeAtom = getNegativeAtom(bodyAtoms[i]); tClause = DLClause.create(new Atom[] { negativeAtom }, newBodyAtoms); // addDatalogRule(tClause); newClauses.add(tClause); - } - else { + } else { Atom[] newBodyAtoms = new Atom[bodyLength]; - Atom negativeAtom = null; - org.semanticweb.HermiT.model.Variable E = org.semanticweb.HermiT.model.Variable.create("E"); + Atom negativeAtom = null; + org.semanticweb.HermiT.model.Variable E = org.semanticweb.HermiT.model.Variable.create("E"); AtLeastConcept alc = norm.getLeftAtLeastConcept(ac); - + if (alc.getOnRole() instanceof AtomicRole) newBodyAtoms[i] = Atom.create((AtomicRole) alc.getOnRole(), bodyAtoms[i].getArgument(0), E); - else + else newBodyAtoms[i] = Atom.create(((InverseRole) alc.getOnRole()).getInverseOf(), E, bodyAtoms[i].getArgument(0)); if (alc.getToConcept() instanceof AtomicConcept) negativeAtom = getNegativeAtom(Atom.create((AtomicConcept) alc.getToConcept(), E)); - else + else negativeAtom = getNegativeAtom(Atom.create(((AtomicNegationConcept) alc.getToConcept()).getNegatedAtomicConcept(), E)); - - for (int j = 0; j < bodyLength; ++j) + + for (int j = 0; j < bodyLength; ++j) if (i != j) - newBodyAtoms[j] = bodyAtoms[j]; + newBodyAtoms[j] = bodyAtoms[j]; + - tClause = DLClause.create(new Atom[] { negativeAtom }, newBodyAtoms); // addDatalogRule(tClause); newClauses.add(tClause); @@ -84,55 +73,65 @@ public class RestrictedApplication extends MultiStageUpperProgram { } else if (headLength > 1) { for (int i = 0; i < headLength; ++i) { - DLPredicate p = headAtoms[i].getDLPredicate(); + DLPredicate p = headAtoms[i].getDLPredicate(); if (!(p instanceof AtomicConcept)) { - return newClauses; + return newClauses; } } for (int i = 0; i < headLength; ++i) { - Atom[] newBodyAtoms = new Atom[headLength + bodyLength - 1]; + Atom[] newBodyAtoms = new Atom[headLength + bodyLength - 1]; for (int j = 0; j < headLength + bodyLength - 1; ++j) - newBodyAtoms[j] = j < bodyLength ? bodyAtoms[j] : - j < bodyLength + i ? getNegativeAtom(headAtoms[j - bodyLength]) : - getNegativeAtom(headAtoms[j - bodyLength + 1]); + newBodyAtoms[j] = j < bodyLength ? bodyAtoms[j] : + j < bodyLength + i ? getNegativeAtom(headAtoms[j - bodyLength]) : + getNegativeAtom(headAtoms[j - bodyLength + 1]); - tClause = DLClause.create(new Atom[] { headAtoms[i] }, newBodyAtoms); + tClause = DLClause.create(new Atom[]{headAtoms[i]}, newBodyAtoms); // addDatalogRule(tClause); newClauses.add(tClause); } } else if (headLength == 1) { - DLPredicate p = clause.getHeadAtom(0).getDLPredicate(); + DLPredicate p = clause.getHeadAtom(0).getDLPredicate(); if (p instanceof AtomicConcept) { - Atom negativeHeadAtom = getNegativeAtom(clause.getHeadAtom(0)); - for (int i = 0; i < bodyLength; ++i) - if (bodyAtoms[i].getDLPredicate() instanceof AtomicConcept) { + Atom negativeHeadAtom = getNegativeAtom(clause.getHeadAtom(0)); + for (int i = 0; i < bodyLength; ++i) + if (bodyAtoms[i].getDLPredicate() instanceof AtomicConcept) { Atom[] newBodyAtoms = new Atom[clause.getBodyLength()]; - newBodyAtoms[0] = negativeHeadAtom; + newBodyAtoms[0] = negativeHeadAtom; for (int j = 1; j < bodyLength; ++j) newBodyAtoms[j] = j <= i ? bodyAtoms[j - 1] : bodyAtoms[j]; - - tClause = DLClause.create(new Atom[] {getNegativeAtom(bodyAtoms[i])}, newBodyAtoms); + + tClause = DLClause.create(new Atom[]{getNegativeAtom(bodyAtoms[i])}, newBodyAtoms); // addDatalogRule(tClause); newClauses.add(tClause); } } else if (p instanceof AtLeastConcept && clause.getBodyLength() == 1 && clause.getBodyAtom(0).getDLPredicate() instanceof AtomicConcept) { - AtLeastConcept alc = (AtLeastConcept) p; - AtomicConcept ac = norm.getLeftAuxiliaryConcept(alc, true); + AtLeastConcept alc = (AtLeastConcept) p; + AtomicConcept ac = norm.getLeftAuxiliaryConcept(alc, true); if (ac != null) { - Atom bodyAtom = clause.getBodyAtom(0); -// addDatalogRule(DLClause.create(new Atom[] {getNegativeAtom(bodyAtom)}, + Atom bodyAtom = clause.getBodyAtom(0); +// addDatalogRule(DLClause.create(new Atom[] {getNegativeAtom(bodyAtom)}, // new Atom[] {getNegativeAtom(Atom.create(ac, bodyAtom.getArgument(0)))} )); - newClauses.add(DLClause.create(new Atom[] {getNegativeAtom(bodyAtom)}, - new Atom[] {getNegativeAtom(Atom.create(ac, bodyAtom.getArgument(0)))} )); + newClauses.add(DLClause.create(new Atom[]{getNegativeAtom(bodyAtom)}, + new Atom[]{getNegativeAtom(Atom.create(ac, bodyAtom.getArgument(0)))})); } } } return newClauses; } + private void addNegativeDatalogRules() { + Collection allRules = new LinkedList(rules); + allRules.addAll(constraints); + for (DLClause clause : allRules) { + for (DLClause newClause : addAdditionalDatalogRules(clause, m_bottom, norm)) + addDatalogRule(newClause); + } + allRules.clear(); + } + public Normalisation getNormalisation() { return norm; } diff --git a/src/uk/ac/ox/cs/pagoda/multistage/treatement/Pick4NegativeConcept.java b/src/uk/ac/ox/cs/pagoda/multistage/treatement/Pick4NegativeConcept.java index 3917efc..244eb7a 100644 --- a/src/uk/ac/ox/cs/pagoda/multistage/treatement/Pick4NegativeConcept.java +++ b/src/uk/ac/ox/cs/pagoda/multistage/treatement/Pick4NegativeConcept.java @@ -18,41 +18,34 @@ import uk.ac.ox.cs.pagoda.util.Utility; import java.util.*; public abstract class Pick4NegativeConcept implements Treatment { - - MultiStageQueryEngine engine; - MultiStageUpperProgram program; - RDFoxTripleManager tripleManager; + + public Set addedGroundAtoms = new HashSet(); + MultiStageQueryEngine engine; + MultiStageUpperProgram program; + RDFoxTripleManager tripleManager; PredicateDependency dependencyGraph; - boolean addGap = false; + boolean addGap = false; public Pick4NegativeConcept(MultiStageQueryEngine store, MultiStageUpperProgram multiProgram) { - this.engine = store; + this.engine = store; this.program = multiProgram; this.tripleManager = new RDFoxTripleManager(store.getDataStore(), true); } - + void addTripleByID(Atom atom, Atom gapAtom, Map assignment) { - int[] newTuple = tripleManager.getInstance(atom, assignment); + int[] newTuple = tripleManager.getInstance(atom, assignment); tripleManager.addTripleByID(newTuple); - if (addGap) + if (addGap) tripleManager.addTripleByID(tripleManager.getInstance(gapAtom, assignment)); } - public Set addedGroundAtoms = new HashSet(); - protected boolean makeSatisfied(Violation violation, Comparator comp) { LinkedList tuples = violation.getTuples(); DLClause constraint = violation.getConstraint(); Map assignment = new HashMap(); if (constraint.getHeadLength() > 1) { - Atom[] orderedAtoms = new Atom[constraint.getHeadLength()]; - int index = 0; - - for (Atom headAtom: constraint.getHeadAtoms()) { - orderedAtoms[index++] = headAtom; - } - + Atom[] orderedAtoms = Arrays.copyOf(constraint.getHeadAtoms(), constraint.getHeadLength()); Arrays.sort(orderedAtoms, comp); Set negTuples = new HashSet(); @@ -86,10 +79,9 @@ public abstract class Pick4NegativeConcept implements Treatment { AnswerTupleID lastAdded = null; for (Iterator iter = tuples.iterator(); iter.hasNext(); ) { - - AnswerTupleID tuple = iter.next(); - if (negTuples.contains(MultiStageUpperProgram.project(tuple, violation.getVariables(), subVars))) ; - else { + + AnswerTupleID tuple = iter.next(); + if (!negTuples.contains(MultiStageUpperProgram.project(tuple, violation.getVariables(), subVars))) { if (lastAdded == null || tComp.compare(lastAdded, tuple) != 0) { lastAdded = tuple; tuple.getAssignment(violation.getVariables(), assignment); @@ -103,29 +95,26 @@ public abstract class Pick4NegativeConcept implements Treatment { if (tuples.isEmpty()) return true; } - - if (!tuples.isEmpty()) return false; - + if (!tuples.isEmpty()) return false; } else { - Set headAtoms = new HashSet(); - for (DLClause clause: program.convertExist(constraint, violation.getClause())) { - if (DLClauseHelper.hasSubsetBodyAtoms(clause, constraint)) { - Atom tHeadAtom = clause.getHeadAtom(0); - Atom tGapHeadAtom = addGap ? getGapAtom(tHeadAtom) : null; - if (DLClauseHelper.isGround(tHeadAtom)) { - if (!addedGroundAtoms.contains(tHeadAtom)) { - program.addUpdatedPredicate(tHeadAtom.getDLPredicate()); - addTripleByID(tHeadAtom, tGapHeadAtom, null); - addedGroundAtoms.add(tHeadAtom); - } - } - else headAtoms.add(tHeadAtom); - } - else { - Utility.logError("There might be an error here... Can't happend!!!"); - throw new Error("This condition should not happen!"); + Set headAtoms = new HashSet(); + for (DLClause clause : program.convertExist(constraint, violation.getClause(), violation.getTuples())) { + + if (!DLClauseHelper.hasSubsetBodyAtoms(clause, constraint)) { + Utility.logError("There might be an error here... Cannot happen!!!"); + throw new Error("This condition should not happen!!!"); } + + Atom tHeadAtom = clause.getHeadAtom(0); + Atom tGapHeadAtom = addGap ? getGapAtom(tHeadAtom) : null; + if (DLClauseHelper.isGround(tHeadAtom)) { + if (!addedGroundAtoms.contains(tHeadAtom)) { + program.addUpdatedPredicate(tHeadAtom.getDLPredicate()); + addTripleByID(tHeadAtom, tGapHeadAtom, null); + addedGroundAtoms.add(tHeadAtom); + } + } else headAtoms.add(tHeadAtom); } if (!tuples.isEmpty()) for (Atom atom: headAtoms) diff --git a/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java b/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java index 7999daa..3c0a001 100644 --- a/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java +++ b/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java @@ -44,31 +44,36 @@ public class MyQueryReasoner extends QueryReasoner { boolean equalityTag; boolean multiStageTag; - + TrackingRuleEncoder encoder; + Timer t = new Timer(); + private Collection predicatesWithGap = null; + private Boolean satisfiable; + private ConsistencyManager consistency = new ConsistencyManager(this); + public MyQueryReasoner() { - setup(true, true); + setup(true, true); } - + public MyQueryReasoner(boolean multiStageTag, boolean considerEqualities) { - setup(multiStageTag, considerEqualities); + setup(multiStageTag, considerEqualities); } private BasicQueryEngine getUpperStore(String name, boolean checkValidity) { if (multiStageTag) - return new MultiStageQueryEngine(name, checkValidity); + return new MultiStageQueryEngine(name, checkValidity); // return new TwoStageQueryEngine(name, checkValidity); - else - return new BasicQueryEngine(name); + else + return new BasicQueryEngine(name); } public void setup(boolean multiStageTag, boolean considerEqualities) { - satisfiable = null; - this.multiStageTag = multiStageTag; + satisfiable = null; + this.multiStageTag = multiStageTag; this.equalityTag = considerEqualities; rlLowerStore = new BasicQueryEngine("rl-lower-bound"); elLowerStore = new KarmaQueryEngine("elho-lower-bound"); - + trackingStore = getUpperStore("tracking", false); } @@ -80,113 +85,108 @@ public class MyQueryReasoner extends QueryReasoner { elLowerStore.importRDFData(name, datafile); trackingStore.importRDFData(name, datafile); } - + @Override public void loadOntology(OWLOntology o) { if (!equalityTag) { EqualitiesEliminator eliminator = new EqualitiesEliminator(o); o = eliminator.getOutputOntology(); eliminator.save(); - } + } - ontology = o; + ontology = o; program = new DatalogProgram(ontology, properties.getToClassify()); // program.getLower().save(); // program.getUpper().save(); // program.getGeneral().save(); - - if (multiStageTag && !program.getGeneral().isHorn()) { + + if (multiStageTag && !program.getGeneral().isHorn()) { lazyUpperStore = getUpperStore("lazy-upper-bound", true); // new MultiStageQueryEngine("lazy-upper-bound", true); // } - + + // TODO add new upper store creation + importData(program.getAdditionalDataFile()); - + elho_ontology = new ELHOProfile().getFragment(ontology); elLowerStore.processOntology(elho_ontology); } - - private Collection predicatesWithGap = null; public Collection getPredicatesWithGap() { - return predicatesWithGap; - } - + return predicatesWithGap; + } + @Override public boolean preprocess() { - t.reset(); + t.reset(); Utility.logInfo("Preprocessing ... checking satisfiability ... "); - String name = "data", datafile = importedData.toString(); + String name = "data", datafile = importedData.toString(); rlLowerStore.importRDFData(name, datafile); rlLowerStore.materialise("lower program", program.getLower().toString()); // program.getLower().save(); if (!consistency.checkRLLowerBound()) return false; Utility.logInfo("The number of sameAs assertions in RL lower store: " + rlLowerStore.getSameAsNumber()); - + String originalMarkProgram = OWLHelper.getOriginalMarkProgram(ontology); - + elLowerStore.importRDFData(name, datafile); elLowerStore.materialise("saturate named individuals", originalMarkProgram); elLowerStore.materialise("lower program", program.getLower().toString()); elLowerStore.initialiseKarma(); - if (!consistency.checkELLowerBound()) return false; + if (!consistency.checkELLowerBound()) return false; if (lazyUpperStore != null) { lazyUpperStore.importRDFData(name, datafile); lazyUpperStore.materialise("saturate named individuals", originalMarkProgram); - int tag = lazyUpperStore.materialiseRestrictedly(program, null); + int tag = lazyUpperStore.materialiseRestrictedly(program, null); if (tag != 1) { lazyUpperStore.dispose(); lazyUpperStore = null; } - if (tag == -1) return false; + if (tag == -1) return false; } if (consistency.checkLazyUpper()) { - satisfiable = true; - Utility.logInfo("time for satisfiability checking: " + t.duration()); + satisfiable = true; + Utility.logInfo("time for satisfiability checking: " + t.duration()); } - + + // TODO add new upper store preprocessing + trackingStore.importRDFData(name, datafile); trackingStore.materialise("saturate named individuals", originalMarkProgram); - + // materialiseFullUpper(); - GapByStore4ID gap = new GapByStore4ID(trackingStore); + GapByStore4ID gap = new GapByStore4ID(trackingStore); trackingStore.materialiseFoldedly(program, gap); - predicatesWithGap = gap.getPredicatesWithGap(); + predicatesWithGap = gap.getPredicatesWithGap(); gap.clear(); - + if (program.getGeneral().isHorn()) encoder = new TrackingRuleEncoderWithGap(program.getUpper(), trackingStore); - else - encoder = new TrackingRuleEncoderDisjVar1(program.getUpper(), trackingStore); -// encoder = new TrackingRuleEncoderDisj1(program.getUpper(), trackingStore); -// encoder = new TrackingRuleEncoderDisjVar2(program.getUpper(), trackingStore); -// encoder = new TrackingRuleEncoderDisj2(program.getUpper(), trackingStore); - - program.deleteABoxTurtleFile(); + else + encoder = new TrackingRuleEncoderDisjVar1(program.getUpper(), trackingStore); +// encoder = new TrackingRuleEncoderDisj1(program.getUpper(), trackingStore); +// encoder = new TrackingRuleEncoderDisjVar2(program.getUpper(), trackingStore); +// encoder = new TrackingRuleEncoderDisj2(program.getUpper(), trackingStore); + + program.deleteABoxTurtleFile(); if (!isConsistent()) - return false; - + return false; + consistency.extractBottomFragment(); - return true; + return true; } - private Boolean satisfiable; - private ConsistencyManager consistency = new ConsistencyManager(this); - - TrackingRuleEncoder encoder; - @Override public boolean isConsistent() { if (satisfiable == null) { - satisfiable = consistency.check(); + satisfiable = consistency.check(); Utility.logInfo("time for satisfiability checking: " + t.duration()); } - return satisfiable; + return satisfiable; } - - Timer t = new Timer(); private OWLOntology relevantPart(QueryRecord queryRecord) { AnswerTuples rlAnswer = null, elAnswer = null; @@ -209,22 +209,29 @@ public class MyQueryReasoner extends QueryReasoner { queryUpperBound(upperStore, queryRecord, queryRecord.getQueryText(), queryRecord.getAnswerVariables()); - // TODO log correct partial answers -// Utility.logDebug(toJson("upperBound1", queryRecord)); if (!queryRecord.processed() && !queryRecord.getQueryText().equals(extendedQuery[0])) { queryUpperBound(upperStore, queryRecord, extendedQuery[0], queryRecord.getAnswerVariables()); -// Utility.logDebug(toJson("upperBound2", queryRecord)); } if (!queryRecord.processed() && queryRecord.hasNonAnsDistinguishedVariables()) { queryUpperBound(upperStore, queryRecord, extendedQuery[1], queryRecord.getDistinguishedVariables()); -// Utility.logDebug(toJson("upperBound3", queryRecord)); } - + + Utility.logDebug(toJsonKeyValuePair("upperBound1", queryRecord)); + + // TODO check whether it is harmful. In case is not, implement it properly + // BEGIN: trying to intersect + if (!queryRecord.isBottom() && lazyUpperStore != null) { + queryUpperBound(trackingStore, queryRecord, queryRecord.getQueryText(), queryRecord.getAnswerVariables()); + } + // END: trying to intersect + queryRecord.addProcessingTime(Step.UpperBound, t.duration()); if (queryRecord.processed()) { queryRecord.setDifficulty(Step.UpperBound); return null; } + + // TODO add evaluation on new upper store t.reset(); try { @@ -280,7 +287,7 @@ public class MyQueryReasoner extends QueryReasoner { // int counter = 0; - private String toJson(String key, Object value) { + private String toJsonKeyValuePair(String key, Object value) { HashMap map = new HashMap<>(); map.put(key, value); return QueryRecord.GsonCreator.getInstance().toJson(map); diff --git a/src/uk/ac/ox/cs/pagoda/rules/ExistConstantApproximator.java b/src/uk/ac/ox/cs/pagoda/rules/ExistConstantApproximator.java new file mode 100644 index 0000000..74c531f --- /dev/null +++ b/src/uk/ac/ox/cs/pagoda/rules/ExistConstantApproximator.java @@ -0,0 +1,23 @@ +package uk.ac.ox.cs.pagoda.rules; + +import org.semanticweb.HermiT.model.DLClause; +import uk.ac.ox.cs.pagoda.multistage.AnswerTupleID; + +import java.util.Collection; + +/** + * A wrapper for OverApproxExist. + * */ +public class ExistConstantApproximator implements TupleDependentApproximator { + + private final OverApproxExist overApproxExist; + + public ExistConstantApproximator() { + overApproxExist = new OverApproxExist(); + } + + @Override + public Collection convert(DLClause clause, DLClause originalClause, Collection violationTuples) { + return overApproxExist.convert(clause, originalClause); + } +} diff --git a/src/uk/ac/ox/cs/pagoda/rules/LimitedSkolemisationApproximator.java b/src/uk/ac/ox/cs/pagoda/rules/LimitedSkolemisationApproximator.java new file mode 100644 index 0000000..284edd2 --- /dev/null +++ b/src/uk/ac/ox/cs/pagoda/rules/LimitedSkolemisationApproximator.java @@ -0,0 +1,72 @@ +package uk.ac.ox.cs.pagoda.rules; + +import org.semanticweb.HermiT.model.DLClause; +import uk.ac.ox.cs.pagoda.multistage.AnswerTupleID; + +import java.util.*; + +/** + * Approximates existential rules by a limited form of Skolemisation. + *

+ * Given a rule and a grounding substitution, + * it Skolemises the rule if + * all the terms in the substitution have depth less than a given depth, + * otherwise it approximates using an alternative TupleDependentApproximator. + * + * */ +public class LimitedSkolemisationApproximator implements TupleDependentApproximator { + + private final int maxTermDepth; + private final TupleDependentApproximator alternativeApproximator; + + private Map mapIndividualsToDepth; + + public LimitedSkolemisationApproximator(int maxTermDepth) { + this(maxTermDepth, new ExistConstantApproximator()); + } + + public LimitedSkolemisationApproximator(int maxTermDepth, TupleDependentApproximator alternativeApproximator) { + this.maxTermDepth = maxTermDepth; + this.alternativeApproximator = alternativeApproximator; + this.mapIndividualsToDepth = new HashMap<>(); + } + + @Override + public Collection convert(DLClause clause, DLClause originalClause, Collection violationTuples) { + switch (clause.getHeadLength()) { + case 1: + return overApprox(clause, originalClause, violationTuples); + case 0: + return Arrays.asList(clause); + default: + ArrayList result = new ArrayList<>(); + // TODO implement + return result; + } + + + } + + private Collection overApprox(DLClause clause, DLClause originalClause, Collection violationTuples) { + ArrayList result = new ArrayList<>(); + + for (AnswerTupleID violationTuple : violationTuples) + if (getDepth(violationTuple) > maxTermDepth) + result.addAll(alternativeApproximator.convert(clause, originalClause, null)); + else + result.add(getInstantiatedSkolemisation(clause, originalClause, violationTuple)); + + return result; + } + + + private DLClause getInstantiatedSkolemisation(DLClause clause, DLClause originalClause, AnswerTupleID violationTuple) { + // TODO implement + return null; + } + + private int getDepth(AnswerTupleID violationTuple) { + if (!mapIndividualsToDepth.containsKey(violationTuple)) return 0; + return mapIndividualsToDepth.get(violationTuple); + } +} diff --git a/src/uk/ac/ox/cs/pagoda/rules/OverApproxExist.java b/src/uk/ac/ox/cs/pagoda/rules/OverApproxExist.java index 2ff1673..1099acf 100644 --- a/src/uk/ac/ox/cs/pagoda/rules/OverApproxExist.java +++ b/src/uk/ac/ox/cs/pagoda/rules/OverApproxExist.java @@ -8,87 +8,67 @@ import java.util.*; public class OverApproxExist implements Approximator { - @Override - public Collection convert(DLClause clause, DLClause originalClause) { - Collection ret; - switch (clause.getHeadLength()) { - case 1: - return overApprox(clause.getHeadAtom(0), clause.getBodyAtoms(), originalClause); - case 0: - ret = new LinkedList(); - ret.add(clause); - return ret; - default: - ret = new LinkedList(); - for (Iterator iter = new DisjunctiveHeads(clause, originalClause); iter.hasNext(); ) - ret.add(iter.next()); - return ret; - } - } - + public static final String negativeSuffix = "_neg"; + public static final String skolemisedIndividualPrefix = Namespace.PAGODA_ANONY + "individual"; + private static final Variable X = Variable.create("X"); + private static int individualCounter = 0; + private static Map individualNumber = new HashMap(); + private static int noOfExistential(DLClause originalClause) { - int no = 0; + int no = 0; for (Atom atom: originalClause.getHeadAtoms()) if (atom.getDLPredicate() instanceof AtLeast) - no += ((AtLeast) atom.getDLPredicate()).getNumber(); - return no; + no += ((AtLeast) atom.getDLPredicate()).getNumber(); + return no; } private static int indexOfExistential(Atom headAtom, DLClause originalClause) { - if (!(headAtom.getDLPredicate() instanceof AtLeast)) return -1; + if (!(headAtom.getDLPredicate() instanceof AtLeast)) return -1; AtLeastConcept alc = (AtLeastConcept) headAtom.getDLPredicate(); if (alc.getToConcept() instanceof AtomicConcept) { - AtomicConcept ac = (AtomicConcept) alc.getToConcept(); + AtomicConcept ac = (AtomicConcept) alc.getToConcept(); if (ac.getIRI().endsWith(negativeSuffix)) { alc = AtLeastConcept.create(alc.getNumber(), alc.getOnRole(), AtomicNegationConcept.create(getNegationConcept(ac))); - headAtom = Atom.create(alc, headAtom.getArgument(0)); + headAtom = Atom.create(alc, headAtom.getArgument(0)); } } - - int index = 0; + + int index = 0; for (Atom atom: originalClause.getHeadAtoms()) { - if (atom.equals(headAtom)) - return index; + if (atom.equals(headAtom)) + return index; if (atom.getDLPredicate() instanceof AtLeast) - index += ((AtLeast) atom.getDLPredicate()).getNumber(); + index += ((AtLeast) atom.getDLPredicate()).getNumber(); } - return -1; + return -1; } - - private static final Variable X = Variable.create("X"); - public static final String negativeSuffix = "_neg"; public static AtomicConcept getNegationConcept(DLPredicate p) { if (p.equals(AtomicConcept.THING)) return AtomicConcept.NOTHING; - if (p.equals(AtomicConcept.NOTHING)) return AtomicConcept.THING; - + if (p.equals(AtomicConcept.NOTHING)) return AtomicConcept.THING; + if (p instanceof AtomicConcept) { String iri = ((AtomicConcept) p).getIRI(); - if (iri.endsWith(negativeSuffix)) + if (iri.endsWith(negativeSuffix)) iri = iri.substring(0, iri.length() - 4); - else - iri += negativeSuffix; + else + iri += negativeSuffix; return AtomicConcept.create(iri); } if (p instanceof AtLeastConcept) { // FIXME !!! here - return null; + return null; } - return null; - } - - public static final String skolemisedIndividualPrefix = Namespace.PAGODA_ANONY + "individual"; - - private static int individualCounter = 0; - private static Map individualNumber = new HashMap(); - + return null; + } + public static int getNumberOfSkolemisedIndividual() { - return individualCounter; + return individualCounter; } public static Individual getNewIndividual(DLClause originalClause, int offset) { - Individual ret; + Individual ret; if (individualNumber.containsKey(originalClause)) { ret = Individual.create(skolemisedIndividualPrefix + (individualNumber.get(originalClause) + offset)); } @@ -97,16 +77,34 @@ public class OverApproxExist implements Approximator { ret = Individual.create(skolemisedIndividualPrefix + (individualCounter + offset)); individualCounter += noOfExistential(originalClause); } - return ret; + return ret; } public static int indexOfSkolemisedIndividual(Atom atom) { - Term t; + Term t; for (int index = 0; index < atom.getArity(); ++index) { t = atom.getArgument(index); if (t instanceof Individual && ((Individual) t).getIRI().contains(skolemisedIndividualPrefix)) return index; } - return -1; + return -1; + } + + @Override + public Collection convert(DLClause clause, DLClause originalClause) { + Collection ret; + switch (clause.getHeadLength()) { + case 1: + return overApprox(clause.getHeadAtom(0), clause.getBodyAtoms(), originalClause); + case 0: + ret = new LinkedList(); + ret.add(clause); + return ret; + default: + ret = new LinkedList(); + for (Iterator iter = new DisjunctiveHeads(clause, originalClause); iter.hasNext(); ) + ret.add(iter.next()); + return ret; + } } public Collection overApprox(Atom headAtom, Atom[] bodyAtoms, DLClause originalClause) { @@ -123,7 +121,7 @@ public class OverApproxExist implements Approximator { AtomicConcept atomicConcept = null; if (concept instanceof AtomicNegationConcept) { - // is this already in MultiStageUpperProgram? + // TODO CHECK: is this already in MultiStageUpperProgram? Atom atom1 = Atom.create(atomicConcept = ((AtomicNegationConcept) concept).getNegatedAtomicConcept(), X); Atom atom2 = Atom.create(atomicConcept = getNegationConcept(atomicConcept), X); ret.add(DLClause.create(new Atom[0], new Atom[] {atom1, atom2})); diff --git a/src/uk/ac/ox/cs/pagoda/rules/TupleDependentApproximator.java b/src/uk/ac/ox/cs/pagoda/rules/TupleDependentApproximator.java new file mode 100644 index 0000000..63057c4 --- /dev/null +++ b/src/uk/ac/ox/cs/pagoda/rules/TupleDependentApproximator.java @@ -0,0 +1,16 @@ +package uk.ac.ox.cs.pagoda.rules; + +import org.semanticweb.HermiT.model.DLClause; +import uk.ac.ox.cs.pagoda.multistage.AnswerTupleID; + +import java.util.Collection; + +/** + * It approximates rules according to a specific instantiation of the body. + */ +public interface TupleDependentApproximator { + + Collection convert(DLClause clause, + DLClause originalClause, + Collection violationTuples); +} diff --git a/src/uk/ac/ox/cs/pagoda/util/SparqlHelper.java b/src/uk/ac/ox/cs/pagoda/util/SparqlHelper.java index 31838bc..1e53b9c 100644 --- a/src/uk/ac/ox/cs/pagoda/util/SparqlHelper.java +++ b/src/uk/ac/ox/cs/pagoda/util/SparqlHelper.java @@ -1,49 +1,18 @@ package uk.ac.ox.cs.pagoda.util; -import java.util.Collection; -import java.util.HashSet; -import java.util.Set; - -import org.semanticweb.HermiT.model.AnnotatedEquality; -import org.semanticweb.HermiT.model.AtLeastConcept; -import org.semanticweb.HermiT.model.Atom; -import org.semanticweb.HermiT.model.AtomicConcept; -import org.semanticweb.HermiT.model.AtomicDataRange; -import org.semanticweb.HermiT.model.AtomicRole; -import org.semanticweb.HermiT.model.Constant; -import org.semanticweb.HermiT.model.DLPredicate; -import org.semanticweb.HermiT.model.Equality; -import org.semanticweb.HermiT.model.Individual; -import org.semanticweb.HermiT.model.Inequality; -import org.semanticweb.HermiT.model.Term; -import org.semanticweb.HermiT.model.Variable; - -import uk.ac.ox.cs.pagoda.MyPrefixes; -import uk.ac.ox.cs.pagoda.hermit.RuleHelper; - import com.hp.hpl.jena.graph.Node; import com.hp.hpl.jena.query.Query; import com.hp.hpl.jena.query.QueryFactory; import com.hp.hpl.jena.sparql.core.TriplePath; import com.hp.hpl.jena.sparql.core.Var; -import com.hp.hpl.jena.sparql.syntax.Element; -import com.hp.hpl.jena.sparql.syntax.ElementAssign; -import com.hp.hpl.jena.sparql.syntax.ElementBind; -import com.hp.hpl.jena.sparql.syntax.ElementData; -import com.hp.hpl.jena.sparql.syntax.ElementDataset; -import com.hp.hpl.jena.sparql.syntax.ElementExists; -import com.hp.hpl.jena.sparql.syntax.ElementFilter; -import com.hp.hpl.jena.sparql.syntax.ElementGroup; -import com.hp.hpl.jena.sparql.syntax.ElementMinus; -import com.hp.hpl.jena.sparql.syntax.ElementNamedGraph; -import com.hp.hpl.jena.sparql.syntax.ElementNotExists; -import com.hp.hpl.jena.sparql.syntax.ElementOptional; -import com.hp.hpl.jena.sparql.syntax.ElementPathBlock; -import com.hp.hpl.jena.sparql.syntax.ElementService; -import com.hp.hpl.jena.sparql.syntax.ElementSubQuery; -import com.hp.hpl.jena.sparql.syntax.ElementTriplesBlock; -import com.hp.hpl.jena.sparql.syntax.ElementUnion; -import com.hp.hpl.jena.sparql.syntax.ElementVisitor; +import com.hp.hpl.jena.sparql.syntax.*; +import org.semanticweb.HermiT.model.*; +import uk.ac.ox.cs.pagoda.MyPrefixes; +import uk.ac.ox.cs.pagoda.hermit.RuleHelper; + +import java.util.Collection; +import java.util.HashSet; +import java.util.Set; public class SparqlHelper { @@ -52,7 +21,7 @@ public class SparqlHelper { for (int i = 0; i < atoms.length; ++i) { atoms[i].getVariables(undistinguishedVars); } - int xIndex = 1; + int xIndex = 1; while (undistinguishedVars.contains(Variable.create("X" + xIndex))) ++xIndex; for (String var: vars) -- cgit v1.2.3