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/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 +- 4 files changed, 46 insertions(+), 20 deletions(-) (limited to 'src/uk/ac/ox/cs/pagoda/endomorph') 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()); } -- cgit v1.2.3