[Mulgara-svn] r231 - branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples
andrae at mulgara.org
andrae at mulgara.org
Tue Apr 17 10:05:56 UTC 2007
Author: andrae
Date: 2007-04-17 05:05:56 -0500 (Tue, 17 Apr 2007)
New Revision: 231
Modified:
branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/LiteralTuples.java
branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperations.java
branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperationsUnitTest.java
branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnboundJoinUnitTest.java
branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnorderedProjection.java
Log:
Catches an error in UnorderedProjection where a call to beforeFirst() with a
prefix is blindly passed on to its operand even if the variable orderings don't
match. As this is an *unordered* projection, prefixed iteration is invalid, so
we throw a TuplesException if this is detected.
This bug was triggered because TuplesOperations.append() was not ensuring the
arguments to OrderedAppend were in fact ordered. As the arguments are
UnorderedProjections whenever projection is required, this can lead to prefixing
of an unordered tuples.
The test added to TuplesOperationsUnitTest demonstrates the problem - the
requirement is a conjunction containing a disjunction that contains an operand
that requires reordering.
{x} ^ ( {x y} v {y x}) is sufficient - although if the tuples involved aren't
distinct and sorted the resulting materialisation can trigger a sort() which
will hide the problem.
The fix is to call sort() on the project()'d operands to OrderedAppend.
Modified: branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/LiteralTuples.java
===================================================================
--- branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/LiteralTuples.java 2007-04-17 09:54:54 UTC (rev 230)
+++ branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/LiteralTuples.java 2007-04-17 10:05:56 UTC (rev 231)
@@ -74,12 +74,23 @@
private int currentTuple;
private boolean[] columnContainsUnbound;
private long[] prefix;
+ private boolean sorted;
+ public LiteralTuples(String[] variableNames, boolean sorted) {
+ List vars = new ArrayList();
+ for (int i = 0; i < variableNames.length; i++) {
+ Variable v = new Variable(variableNames[i]);
+ assert!vars.contains(v);
+ vars.add(v);
+ }
+ init((Variable[]) vars.toArray(new Variable[0]), sorted);
+ }
+
/**
* Creates a literal tuples with specified variables.
*/
public LiteralTuples(Variable[] variables) {
- init(variables);
+ init(variables, false);
}
/**
@@ -87,22 +98,17 @@
* Variables created to match variableNames[].
*/
public LiteralTuples(String[] variableNames) {
- List vars = new ArrayList();
- for (int i = 0; i < variableNames.length; i++) {
- Variable v = new Variable(variableNames[i]);
- assert!vars.contains(v);
- vars.add(v);
- }
- init((Variable[]) vars.toArray(new Variable[0]));
+ this(variableNames, false);
}
- private void init(Variable[] variables) {
+ private void init(Variable[] variables, boolean sorted) {
tuples = new ArrayList();
currentTuple = 0;
tupleIterator = null;
setVariables(Arrays.asList(variables));
columnContainsUnbound = new boolean[variables.length];
Arrays.fill(columnContainsUnbound, false);
+ this.sorted = sorted;
}
/**
@@ -170,7 +176,11 @@
}
public RowComparator getComparator() {
- return null;
+ if (sorted) {
+ return DefaultRowComparator.getInstance();
+ } else {
+ return null;
+ }
}
//
@@ -223,7 +233,7 @@
}
public boolean hasNoDuplicates() throws TuplesException {
- return isUnconstrained();
+ return sorted || isUnconstrained();
}
public Object clone() {
Modified: branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperations.java
===================================================================
--- branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperations.java 2007-04-17 09:54:54 UTC (rev 230)
+++ branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperations.java 2007-04-17 10:05:56 UTC (rev 231)
@@ -204,7 +204,9 @@
while (i.hasNext()) {
Tuples operand = (Tuples)i.next();
Tuples proj = project(operand, variables);
- projected.add(proj);
+ Tuples sorted = sort(proj);
+ projected.add(sorted);
+ proj.close();
operand.close();
}
@@ -218,21 +220,6 @@
}
- private static String printArgs(String header, List args) {
- StringBuffer buff = new StringBuffer(header + "[");
- Iterator i = args.iterator();
- if (i.hasNext()) {
- buff.append(tuplesSummary((Tuples)i.next()));
- }
-
- while (i.hasNext()) {
- buff.append(", " + tuplesSummary((Tuples)i.next()));
- }
- buff.append("]");
- return buff.toString();
- }
-
-
/**
* This is approximately a conjunction.
*/
@@ -986,6 +973,21 @@
}
+ private static String printArgs(String header, List args) {
+ StringBuffer buff = new StringBuffer(header + "[");
+ Iterator i = args.iterator();
+ if (i.hasNext()) {
+ buff.append(tuplesSummary((Tuples)i.next()));
+ }
+
+ while (i.hasNext()) {
+ buff.append(", " + tuplesSummary((Tuples)i.next()));
+ }
+ buff.append("]");
+ return buff.toString();
+ }
+
+
private static StringBuffer indentedTuplesTree(Tuples tuples, String indent) {
StringBuffer buff = new StringBuffer();
Modified: branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperationsUnitTest.java
===================================================================
--- branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperationsUnitTest.java 2007-04-17 09:54:54 UTC (rev 230)
+++ branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/TuplesOperationsUnitTest.java 2007-04-17 10:05:56 UTC (rev 231)
@@ -33,6 +33,9 @@
// Log4J
import org.apache.log4j.Logger;
+// Mulgara
+import org.mulgara.query.Variable;
+
/**
* Test case for {@link TuplesOperationsUnitTest}.
*
@@ -76,8 +79,11 @@
* @return The test suite
*/
public static Test suite() {
+ TestSuite suite = new TestSuite();
- return new TestSuite(TuplesOperationsUnitTest.class);
+ suite.addTest(new TuplesOperationsUnitTest("testReorderedAppend"));
+
+ return suite;
}
/**
@@ -99,8 +105,42 @@
*
* @throws Exception if query fails when it should have succeeded
*/
- public void testFoo() throws Exception {
+ public void testReorderedAppend() throws Exception {
+ LiteralTuples lhs = new LiteralTuples(new String[] {"x"}, true);
+ LiteralTuples rhs1 = new LiteralTuples(new String[] {"x", "y"}, true);
+ LiteralTuples rhs2 = new LiteralTuples(new String[] {"y", "x"}, true);
- // not yet implemented
+ lhs.appendTuple(new long[] { 1 });
+ lhs.appendTuple(new long[] { 6 });
+
+ rhs1.appendTuple(new long[] { 1, 2 });
+ rhs1.appendTuple(new long[] { 1, 3 });
+ rhs1.appendTuple(new long[] { 4, 1 });
+
+ rhs2.appendTuple(new long[] { 5, 1 });
+ rhs2.appendTuple(new long[] { 6, 1 });
+ rhs2.appendTuple(new long[] { 1, 7 });
+
+ Tuples append = TuplesOperations.append(rhs1, rhs2);
+ Tuples join = TuplesOperations.join(lhs, append);
+ append.close();
+
+ logger.warn("join - " + TuplesOperations.formatTuplesTree(join));
+
+ Variable[] vars = join.getVariables();
+ assertEquals(2, vars.length);
+ assertEquals(new Variable("x"), vars[0]);
+ assertEquals(new Variable("y"), vars[1]);
+
+ join.beforeFirst();
+
+ TuplesTestingUtil.testTuplesRow(join, new long[] { 1, 2 });
+ TuplesTestingUtil.testTuplesRow(join, new long[] { 1, 3 });
+ TuplesTestingUtil.testTuplesRow(join, new long[] { 1, 5 });
+ TuplesTestingUtil.testTuplesRow(join, new long[] { 1, 6 });
+
+ assertFalse(join.next());
+
+ TuplesTestingUtil.closeTuples(new Tuples[] { join });
}
}
Modified: branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnboundJoinUnitTest.java
===================================================================
--- branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnboundJoinUnitTest.java 2007-04-17 09:54:54 UTC (rev 230)
+++ branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnboundJoinUnitTest.java 2007-04-17 10:05:56 UTC (rev 231)
@@ -121,6 +121,7 @@
testSuite.addTest(new UnboundJoinUnitTest("testNullPrefixBoundInSuffix"));
testSuite.addTest(new UnboundJoinUnitTest("testNullPropagation"));
testSuite.addTest(new UnboundJoinUnitTest("testLeadingPrefixNull"));
+ testSuite.addTest(new UnboundJoinUnitTest("testPartialMGR36"));
return testSuite;
@@ -577,4 +578,47 @@
TuplesTestingUtil.closeTuples(new Tuples[] { actual, lhs, rhs });
}
+
+ /**
+ * Test {@link UnboundJoin}.n the expected final join of MGR-36 case 2.
+ * <pre>
+ * s s p o x s p o x
+ * | 1 | join | 1 2 3 * | = | 1 2 3 * |
+ * | 2 4 5 * | | 1 5 3 2 |
+ * | 2 4 6 * | | 1 6 3 2 |
+ * | 1 5 3 2 |
+ * | 1 6 3 2 |
+ * </pre>
+ */
+ public void testPartialMGR36() throws Exception {
+ String[] lvars = new String[] { "s" };
+ final long[][] lhsValues = new long[][] {
+ new long[] { 1 } };
+
+ String[] rvars = new String[] { "s", "p", "o", "x" };
+ final long[][] rhsValues = new long[][] {
+ new long[] { 1, 2, 3, Tuples.UNBOUND },
+ new long[] { 1, 5, 3, 2 },
+ new long[] { 1, 6, 3, 2 },
+ new long[] { 2, 4, 5, Tuples.UNBOUND },
+ new long[] { 2, 4, 6, Tuples.UNBOUND } };
+
+
+ LiteralTuples lhs = LiteralTuples.create(lvars, lhsValues);
+ LiteralTuples rhs = LiteralTuples.create(rvars, rhsValues);
+
+ Tuples actual = TuplesOperations.sort(new UnboundJoin(new Tuples[] {lhs, rhs}));
+
+ logger.warn("testPartialMGR36 result = " + actual);
+
+ actual.beforeFirst();
+
+ TuplesTestingUtil.testTuplesRow(actual, new long[] { 1, 2, 3, Tuples.UNBOUND } );
+ TuplesTestingUtil.testTuplesRow(actual, new long[] { 1, 5, 3, 2 } );
+ TuplesTestingUtil.testTuplesRow(actual, new long[] { 1, 6, 3, 2 } );
+
+ assertTrue(!actual.next());
+
+ TuplesTestingUtil.closeTuples(new Tuples[] { actual, lhs, rhs });
+ }
}
Modified: branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnorderedProjection.java
===================================================================
--- branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnorderedProjection.java 2007-04-17 09:54:54 UTC (rev 230)
+++ branches/nuc-disj/src/jar/tuples/java/org/mulgara/store/tuples/UnorderedProjection.java 2007-04-17 10:05:56 UTC (rev 231)
@@ -256,6 +256,11 @@
throw new TuplesException("Suffix truncation not supported");
}
+ if (prefix.length > 0) {
+ throw new TuplesException("Prefix not supported in UnorderedProjection" +
+ "- use TuplesOperations.sort() to provide prefix support");
+ }
+
operand.beforeFirst(prefix, 0);
}
More information about the Mulgara-svn
mailing list