From 4f98cb7df7f2921808d825cdcd82f95a0899640e Mon Sep 17 00:00:00 2001 From: yujiao Date: Mon, 25 May 2015 22:07:14 -0700 Subject: fixed a bug in the process of generating gap tuples, see test in TestGapMappedToLower.java --- src/uk/ac/ox/cs/pagoda/approx/RLPlusOntology.java | 7 +- src/uk/ac/ox/cs/pagoda/endomorph/Clique.java | 1 + .../endomorph/plan/OpenEndMultiThreadPlan.java | 2 +- .../ox/cs/pagoda/endomorph/plan/OpenEndPlan.java | 61 ++++++--- .../ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java | 2 +- src/uk/ac/ox/cs/pagoda/query/GapByStore4ID.java | 31 +++-- src/uk/ac/ox/cs/pagoda/query/GapByStore4ID2.java | 146 +++++++++++++++++++++ src/uk/ac/ox/cs/pagoda/query/GapByTriple.java | 5 - src/uk/ac/ox/cs/pagoda/query/GapTupleIterator.java | 4 +- .../ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java | 3 +- .../cs/pagoda/reasoner/light/BasicQueryEngine.java | 4 +- src/uk/ac/ox/cs/pagoda/tracking/QueryTracker.java | 2 +- .../tracking/TrackingRuleEncoderWithGap.java | 9 +- 13 files changed, 226 insertions(+), 51 deletions(-) create mode 100644 src/uk/ac/ox/cs/pagoda/query/GapByStore4ID2.java (limited to 'src/uk/ac/ox/cs/pagoda') diff --git a/src/uk/ac/ox/cs/pagoda/approx/RLPlusOntology.java b/src/uk/ac/ox/cs/pagoda/approx/RLPlusOntology.java index a60b664..1ed8ba6 100644 --- a/src/uk/ac/ox/cs/pagoda/approx/RLPlusOntology.java +++ b/src/uk/ac/ox/cs/pagoda/approx/RLPlusOntology.java @@ -99,7 +99,12 @@ public class RLPlusOntology implements KnowledgeBase { try { String path = OWLHelper.getOntologyPath(inputOntology); - String name = path.substring(path.lastIndexOf(Utility.JAVA_FILE_SEPARATOR)); + String name; + if (path.contains(Utility.JAVA_FILE_SEPARATOR)) + name = path.substring(path.lastIndexOf(Utility.JAVA_FILE_SEPARATOR)); + else + name = path.substring(path.lastIndexOf(":")); + String originalExtension = name.lastIndexOf(".") >= 0 ? name.substring(name.lastIndexOf(".")) : ""; if (inputOntology.getOntologyID().getOntologyIRI() == null) diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java b/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java index 1c269ea..9daea7e 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java @@ -13,6 +13,7 @@ public class Clique { public Clique(NodeTuple u) { nodeTuples = new HashSet(); representative = u; + nodeTuples.add(u); } public boolean addNodeTuple(NodeTuple nodeTuple) { diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java index 8c7ce6a..4e2fc5f 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java @@ -69,7 +69,7 @@ public class OpenEndMultiThreadPlan implements CheckPlan { int count = 0; for (Clique c: dGraph.getTopologicalOrder()) { if (validated.contains(c)) - count += c.getNodeTuples().size() + 1; + count += c.getNodeTuples().size(); } return count; } diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java index 202021d..a740833 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java @@ -1,7 +1,6 @@ package uk.ac.ox.cs.pagoda.endomorph.plan; import java.util.Collection; -import java.util.Deque; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; @@ -23,35 +22,39 @@ public class OpenEndPlan implements CheckPlan { Checker checker; DependencyGraph dGraph; QueryRecord m_record; + int m_answerArity; public OpenEndPlan(Checker checker, DependencyGraph dGraph, QueryRecord record) { this.checker = checker; this.dGraph = dGraph; - m_record = record; + m_record = record; + m_answerArity = record.getAnswerVariables().length; } + Set validated = new HashSet(); + Set falsified = new HashSet(); + Set passedAnswers = new HashSet(); + @Override public int check() { - Deque topo = new LinkedList(dGraph.getTopologicalOrder()); + LinkedList topo = new LinkedList(dGraph.getTopologicalOrder()); Utility.logInfo("Entrances: " + dGraph.getEntrances().size() + " Exists: " + dGraph.getExits().size()); - Set validated = new HashSet(); - Set falsified = new HashSet(); boolean flag = true; Clique clique; Timer t = new Timer(); - - AnswerTuple answerTuple; + AnswerTuple answerTuple; while (!topo.isEmpty()) { if (flag) { - clique = topo.removeFirst(); + clique = topo.removeFirst(); + if (redundant(clique)) continue; if (validated.contains(clique)) continue; if (falsified.contains(clique)) { flag = false; continue; } Utility.logDebug("start checking front ... " + (answerTuple = clique.getRepresentative().getAnswerTuple())); if (checker.check(answerTuple)) { Utility.logDebug(answerTuple.toString() + " is verified."); - setMarkCascadely(clique, validated, dGraph.getOutGoingEdges()); + setMarkCascadelyValidated(clique); } else { falsified.add(clique); @@ -64,10 +67,10 @@ public class OpenEndPlan implements CheckPlan { if (validated.contains(clique)) { flag = true; continue; } Utility.logDebug("start checking back ... " + (answerTuple = clique.getRepresentative().getAnswerTuple())); if (!checker.check(answerTuple)) - setMarkCascadely(clique, falsified, dGraph.getInComingEdges()); + setMarkCascadelyFasified(clique); else { Utility.logDebug(answerTuple.toString() + " is verified."); - validated.add(clique); + addProjections(clique); flag = true; } } @@ -80,9 +83,8 @@ public class OpenEndPlan implements CheckPlan { Collection validAnswers = new LinkedList(); for (Clique c: dGraph.getTopologicalOrder()) if (validated.contains(c)) { - count += c.getNodeTuples().size() + 1; - validAnswers.add(c.getRepresentative().getAnswerTuple()); - + count += c.getNodeTuples().size(); +// validAnswers.add(c.getRepresentative().getAnswerTuple()); for (NodeTuple nodeTuple: c.getNodeTuples()) { ans = nodeTuple.getAnswerTuple(); validAnswers.add(ans); @@ -95,12 +97,35 @@ public class OpenEndPlan implements CheckPlan { return count; } - private void setMarkCascadely(Clique clique, Set marked, Map> edges) { - marked.add(clique); + private boolean redundant(Clique clique) { + for (NodeTuple nodeTuple: clique.getNodeTuples()) + if (!passedAnswers.contains(AnswerTuple.create(nodeTuple.getAnswerTuple(), m_answerArity))) + return false; + return true; + } + + private void addProjections(Clique clique) { + for (NodeTuple nodeTuple: clique.getNodeTuples()) + passedAnswers.add(AnswerTuple.create(nodeTuple.getAnswerTuple(), m_answerArity)); + } + + private void setMarkCascadelyValidated(Clique clique) { + validated.add(clique); + addProjections(clique); + Map> edges = dGraph.getOutGoingEdges(); + if (edges.containsKey(clique)) + for (Clique c: edges.get(clique)) + if (!validated.contains(c)) + setMarkCascadelyValidated(c); + } + + private void setMarkCascadelyFasified(Clique clique) { + falsified.add(clique); + Map> edges = dGraph.getInComingEdges(); if (edges.containsKey(clique)) for (Clique c: edges.get(clique)) - if (!marked.contains(c)) - setMarkCascadely(c, marked, edges); + if (!falsified.contains(c)) + setMarkCascadelyFasified(c); } } diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java index d6067d0..6931ccc 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java @@ -22,7 +22,7 @@ public class PlainPlan implements CheckPlan { int count = 0; for (Clique clique: toCheck) if (checker.check(clique.getRepresentative().getAnswerTuple())) { - count += clique.getNodeTuples().size() + 1; + count += clique.getNodeTuples().size(); for (NodeTuple nodeTuple: clique.getNodeTuples()) Utility.logDebug(nodeTuple.getAnswerTuple().toString()); } diff --git a/src/uk/ac/ox/cs/pagoda/query/GapByStore4ID.java b/src/uk/ac/ox/cs/pagoda/query/GapByStore4ID.java index 1c0eb48..84929ad 100644 --- a/src/uk/ac/ox/cs/pagoda/query/GapByStore4ID.java +++ b/src/uk/ac/ox/cs/pagoda/query/GapByStore4ID.java @@ -8,6 +8,7 @@ import uk.ac.ox.cs.pagoda.MyPrefixes; //import uk.ac.ox.cs.pagoda.multistage.AnswerTupleID; import uk.ac.ox.cs.pagoda.reasoner.light.BasicQueryEngine; import uk.ac.ox.cs.pagoda.reasoner.light.RDFoxTripleManager; +import uk.ac.ox.cs.pagoda.util.Namespace; import uk.ac.ox.cs.pagoda.util.Timer; import uk.ac.ox.cs.pagoda.util.Utility; import uk.ac.ox.cs.JRDFox.JRDFStoreException; @@ -17,14 +18,14 @@ import uk.ac.ox.cs.JRDFox.store.TupleIterator; //public class GapByStore4ID extends GapTupleIterator { public class GapByStore4ID extends GapTupleIterator { - private MyPrefixes prefixes = MyPrefixes.PAGOdAPrefixes; - private TupleIterator iterator = null; + protected MyPrefixes prefixes = MyPrefixes.PAGOdAPrefixes; + protected TupleIterator iterator = null; // AnswerTupleID tuple; - int[] tuple; - private BasicQueryEngine m_engine; - private DataStore m_store; - private RDFoxTripleManager tripleManager; + protected int[] tuple; + protected BasicQueryEngine m_engine; + protected DataStore m_store; + protected RDFoxTripleManager tripleManager; public GapByStore4ID(BasicQueryEngine engine) { m_engine = engine; @@ -32,7 +33,7 @@ public class GapByStore4ID extends GapTupleIterator { tripleManager = new RDFoxTripleManager(m_store, false); } - long multi; + protected long multi; @Override public void compile(String program) throws JRDFStoreException { @@ -117,7 +118,7 @@ public class GapByStore4ID extends GapTupleIterator { return predicatesWithGap; } - private Integer getGapPredicateID(int originalID) { + protected Integer getGapPredicateID(int originalID) { Integer gapID; if ((gapID = original2gap.get(originalID)) != null) return gapID; @@ -136,11 +137,14 @@ public class GapByStore4ID extends GapTupleIterator { return gapID; } - private boolean isAuxPredicate(String originalPredicate) { - return originalPredicate.contains("_AUX"); + protected boolean isAuxPredicate(String originalPredicate) { + if (originalPredicate.equals(Namespace.EQUALITY_QUOTED)) return false; + return originalPredicate.contains("_AUX") || + originalPredicate.startsWith("<" + Namespace.OWL_NS) || + originalPredicate.startsWith("<" + Namespace.PAGODA_ORIGINAL); } - private boolean isRDF_TYPE() { + protected boolean isRDF_TYPE() { // return tripleManager.isRdfTypeID(tuple.getTerm(1)); return tripleManager.isRdfTypeID(tuple[1]); } @@ -150,8 +154,6 @@ public class GapByStore4ID extends GapTupleIterator { Utility.logError("Unsupported operation!"); } - private boolean valid = false; - @Override public void save(String file) { Utility.logError("Unsupported Operation..."); @@ -168,7 +170,6 @@ public class GapByStore4ID extends GapTupleIterator { ++tupleCounter; tripleManager.addTripleByID(tuple); } - valid = true; long tripleCounter = m_store.getTriplesCount(); Utility.logDebug("There are " + tupleCounter + " tuples in the gap between lower and upper bound materialisation.", @@ -183,8 +184,6 @@ public class GapByStore4ID extends GapTupleIterator { } } - public boolean isValid() {return valid; } - @Override public void addTo(DataStore store) throws JRDFStoreException { Utility.logError("Unsupported Operation..."); diff --git a/src/uk/ac/ox/cs/pagoda/query/GapByStore4ID2.java b/src/uk/ac/ox/cs/pagoda/query/GapByStore4ID2.java new file mode 100644 index 0000000..f8e1709 --- /dev/null +++ b/src/uk/ac/ox/cs/pagoda/query/GapByStore4ID2.java @@ -0,0 +1,146 @@ +package uk.ac.ox.cs.pagoda.query; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedList; +import java.util.Map; +import java.util.Set; + +import uk.ac.ox.cs.pagoda.reasoner.light.BasicQueryEngine; +import uk.ac.ox.cs.pagoda.util.UFS; +import uk.ac.ox.cs.JRDFox.JRDFStoreException; +import uk.ac.ox.cs.JRDFox.store.TupleIterator; + +public class GapByStore4ID2 extends GapByStore4ID { + + private BasicQueryEngine m_baseEngine; + private UFS m_equality = null, m_baseEquality = null; + + public GapByStore4ID2(BasicQueryEngine engine, BasicQueryEngine baseEngine) { + super(engine); + m_baseEngine = baseEngine; + } + + @Override + public boolean hasNext() { + if (getNewGapTuple(iterator, -1)) return true; + if (iterator != null) { + iterator.dispose(); + iterator = null; + } + return getNextGapFactAboutEquality(); + } + + private boolean getNewGapTuple(TupleIterator it, int firstElement) { + if (it == null) return false; + int firstIndex = 0; + tuple = new int[3]; + if (firstElement > 0) { + tuple[0] = firstElement; + firstIndex = 1; + } + Integer predicate; + try { + for (; multi != 0; multi = it.getNext()) { + for (int i = firstIndex; i < 3; ++i) + tuple[i] = (int) it.getResourceID(i - firstIndex); + + if (isRDF_TYPE()) { + predicate = getGapPredicateID(tuple[2]); + if (predicate == null) continue; + tuple[2] = predicate; + } + else { + predicate = getGapPredicateID(tuple[1]); + if (predicate == null) continue; + tuple[1] = predicate; + } + return true; + } + } catch (JRDFStoreException e) { + e.printStackTrace(); + return false; + } + return false; + } + + private LinkedList toAddedIndividuals = null; + private TupleIterator iter_individual = null; + private int currentID = -1; + + private boolean getNextGapFactAboutEquality() { + if (toAddedIndividuals == null) { + m_equality = m_engine.getEqualityGroups(false); + m_baseEquality = m_baseEngine.getEqualityGroups(false); + toAddedIndividuals = new LinkedList(); + Map rep2cnt = new HashMap(); + Map rep2cnt_base = new HashMap(); + count(m_engine, m_equality, rep2cnt); + count(m_baseEngine, m_baseEquality, rep2cnt_base); + Set visitedrep = new HashSet(); + for (String individual : m_equality.keySet()) { + String rep = m_equality.find(individual); + if (visitedrep.contains(rep)) continue; + visitedrep.add(rep); + String rep_base = m_baseEquality.find(individual); + if (!rep2cnt.get(rep).equals(rep2cnt_base.get(rep_base))) { + toAddedIndividuals.add(rep); + } + } + + } + while (true) { + if (getNewGapTuple(iter_individual, currentID)) return true; + if (iter_individual != null) { + iter_individual.dispose(); + iter_individual = null; + } + if (toAddedIndividuals.isEmpty()) { + currentID = -1; + return false; + } + String individual = toAddedIndividuals.remove(); + currentID = tripleManager.getResourceID(individual); + try { + iter_individual = m_engine.internal_evaluateNotExpanded(String.format("select distinct ?y ?z where { <%s> ?y ?z }", individual)); + multi = iter_individual.open(); + } catch (JRDFStoreException e) { + e.printStackTrace(); + } + } + } + + private void count(BasicQueryEngine engine, UFS equality, Map map) { + for (String ind : equality.keySet()) { + Integer exist = map.get(ind); + if (exist == null) + map.put(equality.find(ind), 1); + else + map.put(equality.find(ind), ++exist); + } + } + + @Override + public int[] next() { + try { + if (iterator != null) + multi = iterator.getNext(); + else if (iter_individual != null) + multi = iter_individual.getNext(); + else + multi = 0; + } catch (JRDFStoreException e) { + e.printStackTrace(); + } + return tuple; + } + + public void clear() { + super.clear(); + if (iter_individual != null) { + iter_individual.dispose(); + iter_individual = null; + } + } + +} diff --git a/src/uk/ac/ox/cs/pagoda/query/GapByTriple.java b/src/uk/ac/ox/cs/pagoda/query/GapByTriple.java index a1c1b0e..d2e9b90 100644 --- a/src/uk/ac/ox/cs/pagoda/query/GapByTriple.java +++ b/src/uk/ac/ox/cs/pagoda/query/GapByTriple.java @@ -163,11 +163,6 @@ public class GapByTriple extends GapTupleIterator { addTo(upperStore); } - @Override - public boolean isValid() { - return true; - } - @Override public void clear() { iterator.dispose(); diff --git a/src/uk/ac/ox/cs/pagoda/query/GapTupleIterator.java b/src/uk/ac/ox/cs/pagoda/query/GapTupleIterator.java index 58303bb..61b6364 100644 --- a/src/uk/ac/ox/cs/pagoda/query/GapTupleIterator.java +++ b/src/uk/ac/ox/cs/pagoda/query/GapTupleIterator.java @@ -17,8 +17,6 @@ public abstract class GapTupleIterator implements Iterator { public void compile(String programText) throws JRDFStoreException {} - public abstract boolean isValid(); - public abstract void save(String file); public abstract void addBackTo() throws JRDFStoreException; @@ -26,5 +24,5 @@ public abstract class GapTupleIterator implements Iterator { public abstract void addTo(DataStore store) throws JRDFStoreException; public abstract void clear(); - + } diff --git a/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java b/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java index 17838ae..55ecb81 100644 --- a/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java +++ b/src/uk/ac/ox/cs/pagoda/reasoner/MyQueryReasoner.java @@ -145,7 +145,8 @@ public class MyQueryReasoner extends QueryReasoner { trackingStore.materialise("saturate named individuals", originalMarkProgram); // materialiseFullUpper(); - GapByStore4ID gap = new GapByStore4ID(trackingStore); +// GapByStore4ID gap = new GapByStore4ID(trackingStore); + GapByStore4ID gap = new GapByStore4ID2(trackingStore, rlLowerStore); trackingStore.materialiseFoldedly(program, gap); predicatesWithGap = gap.getPredicatesWithGap(); gap.clear(); diff --git a/src/uk/ac/ox/cs/pagoda/reasoner/light/BasicQueryEngine.java b/src/uk/ac/ox/cs/pagoda/reasoner/light/BasicQueryEngine.java index 11588ce..79be8aa 100644 --- a/src/uk/ac/ox/cs/pagoda/reasoner/light/BasicQueryEngine.java +++ b/src/uk/ac/ox/cs/pagoda/reasoner/light/BasicQueryEngine.java @@ -309,8 +309,8 @@ public class BasicQueryEngine extends RDFoxQueryEngine { private UFS equalityGroups = null; - public UFS getEqualityGroups() { - if (equalityGroups != null) return equalityGroups; + public UFS getEqualityGroups(boolean reuse) { + if (reuse && equalityGroups != null) return equalityGroups; equalityGroups = new UFS(); diff --git a/src/uk/ac/ox/cs/pagoda/tracking/QueryTracker.java b/src/uk/ac/ox/cs/pagoda/tracking/QueryTracker.java index f836212..2973109 100644 --- a/src/uk/ac/ox/cs/pagoda/tracking/QueryTracker.java +++ b/src/uk/ac/ox/cs/pagoda/tracking/QueryTracker.java @@ -54,7 +54,7 @@ public class QueryTracker { m_record = queryRecord; m_manager = m_encoder.getOntology().getOWLOntologyManager(); - equalityGroups = m_dataStore.getEqualityGroups(); + equalityGroups = m_dataStore.getEqualityGroups(true); } diff --git a/src/uk/ac/ox/cs/pagoda/tracking/TrackingRuleEncoderWithGap.java b/src/uk/ac/ox/cs/pagoda/tracking/TrackingRuleEncoderWithGap.java index 555f0af..99028ca 100644 --- a/src/uk/ac/ox/cs/pagoda/tracking/TrackingRuleEncoderWithGap.java +++ b/src/uk/ac/ox/cs/pagoda/tracking/TrackingRuleEncoderWithGap.java @@ -1,6 +1,7 @@ package uk.ac.ox.cs.pagoda.tracking; import java.util.Collection; +import java.util.HashSet; import java.util.LinkedList; import java.util.Set; @@ -37,7 +38,8 @@ public class TrackingRuleEncoderWithGap extends TrackingRuleEncoder { AtomicRole trackingSameAs = AtomicRole.create(Namespace.EQUALITY + "_tn"); OWLOntology onto = program.getOntology(); Atom[] headAtom = new Atom[] {Atom.create(trackingSameAs, X, X)}, bodyAtom; - for (OWLClass cls: onto.getClassesInSignature(true)) { + for (OWLOntology o: onto.getImportsClosure()) + for (OWLClass cls: o.getClassesInSignature()) { String clsIRI = cls.getIRI().toString(); unaryPredicates.add(clsIRI); bodyAtom = new Atom[] { @@ -47,7 +49,10 @@ public class TrackingRuleEncoderWithGap extends TrackingRuleEncoder { } Variable Y = Variable.create("Y"); - Set setOfProperties = onto.getObjectPropertiesInSignature(true); + Set setOfProperties = new HashSet(); + for (OWLOntology o: onto.getImportsClosure()) + for (OWLObjectProperty prop: o.getObjectPropertiesInSignature()) + setOfProperties.add(prop); setOfProperties.add(onto.getOWLOntologyManager().getOWLDataFactory().getOWLObjectProperty(IRI.create(Namespace.INEQUALITY))); for (OWLObjectProperty prop: setOfProperties) { String propIRI = prop.getIRI().toString(); -- cgit v1.2.3