[Mulgara-svn] r751 - branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples
pag at mulgara.org
pag at mulgara.org
Thu Apr 10 04:12:42 UTC 2008
Author: pag
Date: 2008-04-09 21:12:41 -0700 (Wed, 09 Apr 2008)
New Revision: 751
Added:
branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoinUnitTest.java
Modified:
branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoin.java
Log:
LeftJoin seems to be working, and tests pass
Modified: branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoin.java
===================================================================
--- branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoin.java 2008-04-09 10:05:33 UTC (rev 750)
+++ branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoin.java 2008-04-10 04:12:41 UTC (rev 751)
@@ -68,6 +68,12 @@
/** The offset for indexing into the RHS, while avoiding LHS variables */
private int rhsOffset;
+ /** Indicates that the current row is OK, and {@link #next()} will return true. */
+ private boolean currentRowValid = false;
+
+ /** The prefix currently in use on the right */
+ private long[] currentRightPrefix = Tuples.NO_PREFIX;
+
/**
* Configure a subtraction operation for lazy evaluation.
*
@@ -82,7 +88,7 @@
this.lhs = (Tuples)lhs.clone();
this.rhs = (Tuples)rhs.clone();
- // get the variables to subtract with. TODO: get the correct type back from getMatchingVars
+ // get the variables to merge on
commonVars = Collections.unmodifiableSet((Set<Variable>)TuplesOperations.getMatchingVars(lhs, rhs));
if (commonVars.isEmpty()) logger.warn("Tuples should have variables in common for optional join to occur");
@@ -181,7 +187,11 @@
/** {@inheritDoc} */
public RowComparator getComparator() {
- return lhs.getComparator();
+ RowComparator lhsComp = lhs.getComparator();
+ RowComparator rhsComp = lhs.getComparator();
+ // build a new comparator, if both left and right have comparators, else null
+ if (lhsComp == null || rhsComp == null) return null;
+ return new MergedComparator(lhsComp, rhsComp);
}
@@ -204,47 +214,103 @@
}
- /** {@inheritDoc} */
+ /**
+ * {@inheritDoc}
+ * This method matches what it can on the LHS, and saves the rest for later searches
+ * on the RHS. Searches on the RHS only happen when the LHS iterates to valid data.
+ */
public void beforeFirst(long[] prefix, int suffixTruncation) throws TuplesException {
- int nrVars = lhs.getNumberOfVariables();
- int tailLen = prefix.length - nrVars;
+ int lhsVars = lhs.getNumberOfVariables();
+ // The tail of the prefix is the part that searches on the RHS
+ int lhsOnlyVars = (lhsVars - commonVars.size());
+ int tailLen = prefix.length - lhsOnlyVars;
if (tailLen <= 0) {
- // search on the LHS
+ // search on the LHS only
lhs.beforeFirst(prefix, suffixTruncation);
- matchRight();
+ // store the prefix for use on the right
+ currentRightPrefix = Tuples.NO_PREFIX;
} else {
// search on the LHS, and do the remainder of the search of the RHS
- lhs.beforeFirst(prefix, nrVars);
- matchRight();
- // if there is data on the right, then search in it
- if (rightMatches) {
- long[] tailPrefix = new long[tailLen];
- for (int i = 0; i < tailLen; i++) tailPrefix[i] = prefix[i + nrVars];
- rhs.beforeFirst(tailPrefix, 0);
- }
+ lhs.beforeFirst(reduce(prefix, lhsVars), suffixTruncation);
+ // store the data to search on the right
+ currentRightPrefix = reduce(prefix, lhsOnlyVars, tailLen);
}
+ currentRowValid = false;
+ rightMatches = false;
}
+
/** {@inheritDoc} */
public boolean next() throws TuplesException {
- // check if we are currently in a match
+ // check if we are already on a matched line
if (rightMatches) {
- // if there is more, then return
- if (rhs.next()) return true;
- // no more, so move on the left...
+ // we are, so move on the right
+ rightMatches = rhs.next();
+ // if we moved off on the right, then we need to move on the left
+ if (!rightMatches) {
+ currentRowValid = lhs.next();
+ // now that the left has moved, need to search on the right
+ updateRight();
+ }
+ return currentRowValid;
}
+ // There was no current match on the right, so always move on the left
+ currentRowValid = lhs.next();
+ // now that the left has moved, need to search on the right
+ updateRight();
+ return currentRowValid;
+ }
- // not in a match, so move
- if (!lhs.next()) return false;
- // attempt match on the right
- matchRight();
- return true;
+
+ /**
+ * Moves the RHS to data matching the LHS, if the LHS is valid.
+ * Sets the value of {@link #rightMatches} to indicate if the RHS has matching data.
+ * @throws TuplesException If there is an error searching the RHS or moving to the first matching row.
+ */
+ private void updateRight() throws TuplesException {
+ // for a valid row on the left, search on the right
+ if (currentRowValid) {
+ long[] prefix = calculateRHSPrefix();
+ // always doing a bound search, so a null search means no common vars
+ if (prefix.length > 0) {
+ rhs.beforeFirst(prefix, 0);
+ // and see if the rhs data was found
+ rightMatches = rhs.next();
+ } else {
+ // no search required
+ assert commonVars.isEmpty();
+ rightMatches = false;
+ }
+ } else {
+ // since the left is not valid, neither is the right
+ rightMatches = false;
+ }
}
/**
+ * Determine the prefix to use on the RHS, given a possible search already set for this tuples.
+ * @return The prefix to be used for finding a current RHS row.
+ * @throws TuplesException If the LHS could not be accessed.
+ */
+ private long[] calculateRHSPrefix() throws TuplesException {
+ // if the currentRightPrefix is longer than the matching vars, then just return it
+ if (currentRightPrefix.length >= commonVars.size()) return currentRightPrefix;
+ // fill in a prefix with the currentRightPrefix
+ long[] prefix = new long[commonVars.size()];
+ for (int c = 0; c < currentRightPrefix.length; c++) {
+ prefix[c] = currentRightPrefix[c];
+ assert prefix[c] == lhs.getColumnValue(varMap[c]);
+ }
+ // finish the prefix with the columns that are supposed to match
+ for (int c = currentRightPrefix.length; c < prefix.length; c++) {
+ prefix[c] = lhs.getColumnValue(varMap[c]);
+ }
+ return prefix;
+ }
+
+ /**
* Closes all the operands.
- *
* @throws TuplesException If either the lhs or the rhs can't be closed.
*/
public void close() throws TuplesException {
@@ -268,17 +334,277 @@
//
- // Internal methods
+ // Internal methods and classes
//
- private void matchRight() throws TuplesException {
- long[] prefix = new long[varMap.length];
- // copy the variables from the current lhs row into the prefix
- for (int i = 0; i < varMap.length; i++) prefix[i] = lhs.getColumnValue(varMap[i]);
- // find the entry in the rhs
- rhs.beforeFirst(prefix, 0);
- // mark the RHS has matching if the search found anything
- rightMatches = rhs.next();
+
+ /**
+ * A comparator that is only relevant to the LeftJoin operation. Orders first on the left, then on the right
+ * This comparator passes portions of the comparison down to the left and the right.
+ */
+ class MergedComparator implements RowComparator {
+
+ /** The LHS comparator */
+ private RowComparator left;
+
+ /** The RHS comparator */
+ private RowComparator right;
+
+ /**
+ * Constructs a merging of the two comparators.
+ * @param l The comparator for the LHS.
+ * @param r The comparator for the RHS.
+ */
+ MergedComparator(RowComparator l, RowComparator r) {
+ left = l;
+ right = r;
+ }
+
+ /**
+ * Compares tuples with the presumption that they are both LeftJoin operations.
+ * @see org.mulgara.store.tuples.RowComparator#compare(org.mulgara.store.tuples.Tuples, org.mulgara.store.tuples.Tuples)
+ */
+ public int compare(Tuples first, Tuples second) throws TuplesException {
+ if (!(first instanceof LeftJoin) || !(second instanceof LeftJoin)) throw new IllegalArgumentException("Merged Comparators can only operate on LeftJoins");
+ int nrVars = lhs.getNumberOfVariables();
+ int result = left.compare(new ReducedTuples(first, nrVars), new ReducedTuples(second, nrVars));
+ if (result != 0) return result;
+ nrVars = rhs.getNumberOfVariables() - commonVars.size();
+ return right.compare(new ReducedTuples(first, rhsOffset, nrVars), new ReducedTuples(second, rhsOffset, nrVars));
+ }
+
+ /**
+ * Compares an array and a tuples, part at a time. Makes the presumption that the
+ * tuples is a LeftJoin operation.
+ * @see org.mulgara.store.tuples.RowComparator#compare(long[], org.mulgara.store.tuples.Tuples)
+ */
+ public int compare(long[] array, Tuples tuples) throws TuplesException {
+ if (!(tuples instanceof LeftJoin)) throw new IllegalArgumentException("Merged Comparators can only operate on LeftJoins");
+ int nrVars = lhs.getNumberOfVariables();
+ int result = left.compare(reduce(array, nrVars), reduce(tuples, nrVars));
+ if (result != 0) return result;
+ nrVars = rhs.getNumberOfVariables() - commonVars.size();
+ return right.compare(reduce(array, rhsOffset, nrVars), reduce(tuples, rhsOffset, nrVars));
+ }
+
+ /**
+ * Compares two arrays, part at a time.
+ * @see org.mulgara.store.tuples.RowComparator#compare(long[], long[])
+ */
+ public int compare(long[] first, long[] second) throws TuplesException {
+ int nrVars = lhs.getNumberOfVariables();
+ int result = left.compare(reduce(first, nrVars), reduce(second, nrVars));
+ if (result != 0) return result;
+ nrVars = rhs.getNumberOfVariables() - commonVars.size();
+ return right.compare(reduce(first, rhsOffset, nrVars), reduce(second, rhsOffset, nrVars));
+ }
}
+ /**
+ * Truncates an array to a given width.
+ * @param array The array to truncate.
+ * @param width The width to reduce to.
+ * @return If width is smaller than the array length,
+ * then a truncated array, else the original array.
+ */
+ private static long[] reduce(long[] array, int width) {
+ if (width < array.length) {
+ long[] tmp = new long[width];
+ System.arraycopy(array, 0, tmp, 0, width);
+ array = tmp;
+ }
+ return array;
+ }
+
+ /**
+ * Slices an array down to a subarray.
+ * @param array The array to truncate.
+ * @param offset The offset for the slice.
+ * @param width The width of the slice.
+ * @return If width is smaller than the array length,
+ * then a truncated array, else the original array.
+ */
+ private static long[] reduce(long[] array, int offset, int width) {
+ if (width < array.length || offset > 0) {
+ if (offset + width > array.length) throw new IllegalArgumentException("Cannot slice an array outside of its bounds");
+ long[] tmp = new long[width];
+ System.arraycopy(array, offset, tmp, 0, width);
+ array = tmp;
+ }
+ return array;
+ }
+
+ /**
+ * Truncates a Tuples to a given width.
+ * @param tuples The tuples to truncate.
+ * @param width The width to reduce to.
+ * @return A new Tuples which contains the same data as the original, but with fewer columns.
+ */
+ private static Tuples reduce(Tuples tuples, int width) {
+ return new ReducedTuples(tuples, width);
+ }
+
+ /**
+ * Reduces a tuples to a given subset of the original columns.
+ * @param tuples The tuples to truncate.
+ * @param offset The offset for the slice.
+ * @param width The width of the slice.
+ * @return A new Tuples which contains the same data as the original, but with fewer columns.
+ */
+ private static Tuples reduce(Tuples tuples, int offset, int width) {
+ return new ReducedTuples(tuples, offset, width);
+ }
+
+ /** Wraps a tuples, reducing its width according to a set of parameters. */
+ static class ReducedTuples implements Tuples {
+
+ /** The Tuples to wrap. */
+ private Tuples wrapped;
+
+ /** The offset of the variables being exposed. */
+ private int offset;
+
+ /** The number of variables in this tuples. */
+ private int nrVars;
+
+ /**
+ * Wrap a tuples, reducing its width.
+ * @param t The tuples to wrap.
+ * @param w The width to present.
+ */
+ ReducedTuples(Tuples t, int w) {
+ wrapped = t;
+ offset = 0;
+ nrVars = w;
+ }
+
+ /**
+ * Wrap a tuples, reducing its width.
+ * @param t The tuples to wrap.
+ * @param o the offset to start presenting variables.
+ * @param w The width to present.
+ */
+ ReducedTuples(Tuples t, int o, int w) {
+ wrapped = t;
+ offset = o;
+ nrVars = w;
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#clone() */
+ public Object clone() {
+ return new ReducedTuples(wrapped, offset, nrVars);
+ }
+
+ /**
+ * Pass through, but reduce the prefix if it is too long.
+ * @see org.mulgara.store.tuples.Tuples#beforeFirst(long[], int)
+ */
+ public void beforeFirst(long[] prefix, int suffixTruncation) throws TuplesException {
+ // Unable to manage this if selecting on th RHS of a LeftJoin
+ if (offset > 0) throw new UnsupportedOperationException("Unable to perform beforeFirst on an optional sub-tuples");
+ wrapped.beforeFirst(reduce(prefix, nrVars), suffixTruncation);
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#getAnnotation(java.lang.Class) */
+ public Annotation getAnnotation(Class<?> annotationClass) throws TuplesException {
+ return wrapped.getAnnotation(annotationClass);
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#getColumnIndex(org.mulgara.query.Variable) */
+ public int getColumnIndex(Variable variable) throws TuplesException {
+ int col = wrapped.getColumnIndex(variable);
+ if (col >= nrVars || col < offset) throw new TuplesException("No such variable: " + variable);
+ return col - offset;
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#getColumnValue(int) */
+ public long getColumnValue(int column) throws TuplesException {
+ if (column >= nrVars) throw new TuplesException("Invalid column: " + column);
+ return wrapped.getColumnValue(column + offset);
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#getComparator() */
+ public RowComparator getComparator() {
+ return wrapped.getComparator();
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#getOperands() */
+ public List<Tuples> getOperands() {
+ return wrapped.getOperands();
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#getRowCount() */
+ public long getRowCount() throws TuplesException {
+ return wrapped.getRowCount();
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#getVariables() */
+ public Variable[] getVariables() {
+ Variable[] vars = wrapped.getVariables();
+ // cut down the variables to those selected
+ if (vars.length > nrVars || offset > 0) {
+ assert offset + nrVars <= vars.length;
+ Variable[] tmp = new Variable[nrVars];
+ System.arraycopy(vars, offset, tmp, 0, nrVars);
+ vars = tmp;
+ }
+ return vars;
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#hasNoDuplicates() */
+ public boolean hasNoDuplicates() throws TuplesException {
+ return wrapped.hasNoDuplicates();
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#isColumnEverUnbound(int) */
+ public boolean isColumnEverUnbound(int column) throws TuplesException {
+ return wrapped.isColumnEverUnbound(column);
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#isMaterialized() */
+ public boolean isMaterialized() {
+ return wrapped.isMaterialized();
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#isUnconstrained() */
+ public boolean isUnconstrained() throws TuplesException {
+ return wrapped.isUnconstrained();
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#next() */
+ public boolean next() throws TuplesException {
+ return wrapped.next();
+ }
+
+ /** @see org.mulgara.store.tuples.Tuples#renameVariables(org.mulgara.query.Constraint) */
+ public void renameVariables(Constraint constraint) {
+ wrapped.renameVariables(constraint);
+ }
+
+ /** @see org.mulgara.query.Cursor#beforeFirst() */
+ public void beforeFirst() throws TuplesException {
+ wrapped.beforeFirst();
+ }
+
+ /** @see org.mulgara.query.Cursor#close() */
+ public void close() throws TuplesException {
+ wrapped.close();
+ }
+
+ /** @see org.mulgara.query.Cursor#getNumberOfVariables() */
+ public int getNumberOfVariables() {
+ return nrVars;
+ }
+
+ /** @see org.mulgara.query.Cursor#getRowCardinality() */
+ public int getRowCardinality() throws TuplesException {
+ return wrapped.getRowCardinality();
+ }
+
+ /** @see org.mulgara.query.Cursor#getRowUpperBound() */
+ public long getRowUpperBound() throws TuplesException {
+ return wrapped.getRowUpperBound();
+ }
+
+ }
}
Added: branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoinUnitTest.java
===================================================================
--- branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoinUnitTest.java (rev 0)
+++ branches/mgr-61-sparql/src/jar/tuples/java/org/mulgara/store/tuples/LeftJoinUnitTest.java 2008-04-10 04:12:41 UTC (rev 751)
@@ -0,0 +1,348 @@
+/*
+ * The contents of this file are subject to the Open Software License
+ * Version 3.0 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.opensource.org/licenses/osl-3.0.txt
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ */
+
+package org.mulgara.store.tuples;
+
+// Third party packages
+import junit.framework.*; // JUnit
+import org.apache.log4j.Logger; // Log4J
+
+// Locally written packages
+import org.mulgara.query.Variable;
+import static org.mulgara.store.tuples.Tuples.UNBOUND;
+
+/**
+ * Test case for {@link LeftJoin}. This is the
+ * <a href="http://www.w3.org/TR/rdf-sparql-query/#optionals">OPTIONAL</a> operation in SPARQL.
+ *
+ * @created 2008-04-08
+ * @author <a href="mailto:pgearon at users.sourceforge.net">Paul Gearon</a>
+ * @copyright © 2008 <A href="http://www.topazproject.org/">The Topaz Project</A>
+ * @licence <a href="{@docRoot}/../../LICENCE">Open Software License v3.0</a>
+ */
+public class LeftJoinUnitTest extends TestCase {
+
+ /**Logger. */
+ @SuppressWarnings("unused")
+ private static final Logger logger = Logger.getLogger(LeftJoinUnitTest.class);
+
+ /** Test variable. */
+ final Variable x = new Variable("x");
+
+ /** Test variable. */
+ final Variable y = new Variable("y");
+
+ /** Test variable. */
+ final Variable z = new Variable("z");
+
+ /** Test variable. */
+ final Variable w = new Variable("w");
+
+ /** Test variable. */
+ final Variable u = new Variable("u");
+
+ /** Test variable. */
+ final Variable v = new Variable("v");
+
+ /**
+ * Constructs a new test with the given name.
+ * @param name the name of the test
+ */
+ public LeftJoinUnitTest(String name) {
+ super(name);
+ }
+
+ /**
+ * Hook for test runner to obtain a test suite from.
+ *
+ * @return The test suite
+ */
+ public static Test suite() {
+ TestSuite testSuite = new TestSuite();
+ testSuite.addTest(new LeftJoinUnitTest("testNoCommonVars"));
+ testSuite.addTest(new LeftJoinUnitTest("testOneIntersectingVar"));
+ testSuite.addTest(new LeftJoinUnitTest("testIntersectingVars"));
+ return testSuite;
+ }
+
+ /**
+ * Default text runner.
+ * @param args The command line arguments
+ */
+ public static void main(String[] args) {
+ junit.textui.TestRunner.run(suite());
+ }
+
+ /**
+ * Create test instance.
+ */
+ public void setUp() {
+ }
+
+ /**
+ * The teardown method for JUnit
+ */
+ public void tearDown() {
+ // null implementation
+ }
+
+ //
+ // Test cases
+ //
+
+ /**
+ * Test {@link LeftJoin}. When passed two arguments without common
+ * variables, an IllegalArgumentException should be thrown.
+ * @throws Exception if query fails when it should have succeeded
+ */
+ public void testNoCommonVars() throws Exception {
+
+ Tuples lhs = TuplesFactory.newInstance().newTuples(
+ new TestTuples(x, 1).and(y, 2).or(x, 3).and(y, 4));
+
+ Tuples rhs = TuplesFactory.newInstance().newTuples(
+ new TestTuples(z, 5).and(w, 6).or(z, 7).and(w, 8));
+
+ Tuples tuples = new LeftJoin(lhs, rhs);
+ tuples.beforeFirst();
+ assertTrue(tuples.next());
+ assertTrue(tuples.next());
+ assertFalse(tuples.next());
+
+ TuplesTestingUtil.closeTuples(new Tuples[] { lhs, rhs, tuples });
+ }
+
+
+ /**
+ * Test {@link LeftJoin}. When passed arguments with some common variables,
+ * the result should be the first argument, plus any matching rows from the
+ * second, or unbound in the columns from the RHS.
+ * @throws Exception if query fails when it should have succeeded
+ */
+ public void testOneIntersectingVar() throws Exception {
+ String[] lvars = new String[] {"x", "y"};
+ String[] rvars = new String[] {"y", "z"};
+
+ LiteralTuples lhs = new LiteralTuples(lvars);
+ lhs.appendTuple(new long[] {1, 2});
+ lhs.appendTuple(new long[] {3, 4});
+ lhs.appendTuple(new long[] {5, 6});
+ lhs.appendTuple(new long[] {7, 8});
+ lhs.appendTuple(new long[] {9, 10});
+ lhs.appendTuple(new long[] {11, 12});
+ lhs.appendTuple(new long[] {13, 14});
+
+ LiteralTuples rhs = new LiteralTuples(rvars);
+ rhs.appendTuple(new long[] {4, 11});
+ rhs.appendTuple(new long[] {6, 12});
+ rhs.appendTuple(new long[] {12, 31});
+ rhs.appendTuple(new long[] {12, 32});
+ rhs.appendTuple(new long[] {15, 16});
+
+ Tuples actual = new LeftJoin(lhs, rhs);
+// Tuples actual = TuplesOperations.sort(opt);
+//
+// // check the variables
+// Variable[] variables = opt.getVariables();
+// assertEquals(3, variables.length);
+// assertEquals(x, variables[0]);
+// assertEquals(y, variables[1]);
+// assertEquals(z, variables[2]);
+
+ Variable[] variables = actual.getVariables();
+ assertEquals(3, variables.length);
+ assertEquals(x, variables[0]);
+ assertEquals(y, variables[1]);
+ assertEquals(z, variables[2]);
+
+ // First, try a straightforward iteration through all rows
+ actual.beforeFirst();
+
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {1, 2, UNBOUND});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {3, 4, 11});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {5, 6, 12});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {7, 8, UNBOUND});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {9, 10, UNBOUND});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {11, 12, 31});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {11, 12, 32});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {13, 14, UNBOUND});
+ assertTrue(!actual.next());
+
+ // Second, try prefix searches
+ actual.beforeFirst(new long[] { 7 }, 0);
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {7, 8, UNBOUND });
+ assertTrue(!actual.next());
+
+ // Third, try more prefix searches
+ actual.beforeFirst(new long[] { 9, 10 }, 0);
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {9, 10, UNBOUND });
+ assertTrue(!actual.next());
+
+ // Fourth, try a prefix search into the last column
+ actual.beforeFirst(new long[] { 9, 10, UNBOUND }, 0);
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {9, 10, UNBOUND });
+ assertTrue(!actual.next());
+
+ // Fifth, try a prefix search into the last column with a bound value
+ actual.beforeFirst(new long[] { 5, 6, 12 }, 0);
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {5, 6, 12 });
+ assertTrue(!actual.next());
+
+ actual.close();
+
+ // Try joining in the opposite order (RHS to LHS)
+
+ // first, re-order the lhs
+ lvars = new String[] {"y", "x"};
+ lhs = new LiteralTuples(lvars);
+ lhs.appendTuple(new long[] {2, 1});
+ lhs.appendTuple(new long[] {4, 3});
+ lhs.appendTuple(new long[] {6, 5});
+ lhs.appendTuple(new long[] {8, 7});
+ lhs.appendTuple(new long[] {10, 9});
+ lhs.appendTuple(new long[] {12, 11});
+ lhs.appendTuple(new long[] {14, 13});
+
+ actual = new LeftJoin(rhs, lhs);
+
+ variables = actual.getVariables();
+ assertEquals(3, variables.length);
+ assertEquals(y, variables[0]);
+ assertEquals(z, variables[1]);
+ assertEquals(x, variables[2]);
+
+ actual.beforeFirst();
+
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {4, 11, 3});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {6, 12, 5});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {12, 31, 11});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {12, 32, 11});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {15, 16, UNBOUND});
+
+ assertTrue(!actual.next());
+
+ TuplesTestingUtil.closeTuples(new Tuples[] {actual, lhs, rhs});
+ }
+
+ /**
+ * Test {@link LeftJoin}. When passed arguments with some common variables,
+ * the result should be the first argument, regardless of matching rows from the second.
+ * @throws Exception if query fails when it should have succeeded
+ */
+ public void testIntersectingVars() throws Exception {
+ // lhs intersect rhs = rhs
+ String[] lvars = new String[] {"x", "y", "z"};
+ String[] rvars = new String[] {"y", "z"};
+
+ LiteralTuples lhs = new LiteralTuples(lvars);
+ lhs.appendTuple(new long[] {1, 2, 3});
+ lhs.appendTuple(new long[] {4, 5, 6});
+ lhs.appendTuple(new long[] {7, 5, 6});
+ lhs.appendTuple(new long[] {9, 10, 11});
+ lhs.appendTuple(new long[] {12, 13, 14});
+ lhs.appendTuple(new long[] {15, 16, 17});
+ lhs.appendTuple(new long[] {15, 7, 14});
+
+ LiteralTuples rhs = new LiteralTuples(rvars);
+ rhs.appendTuple(new long[] {5, 6});
+ rhs.appendTuple(new long[] {6, 14});
+ rhs.appendTuple(new long[] {7, 14});
+ rhs.appendTuple(new long[] {8, 9});
+
+ LeftJoin join = new LeftJoin(lhs, rhs);
+ Tuples actual = TuplesOperations.sort(join);
+
+ // check the variables
+ Variable[] variables = actual.getVariables();
+ assertEquals(3, variables.length);
+ assertEquals(x, variables[0]);
+ assertEquals(y, variables[1]);
+ assertEquals(z, variables[2]);
+
+ // First, try a straightforward iteration through all rows
+ actual.beforeFirst();
+
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {1, 2, 3});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {4, 5, 6});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {7, 5, 6});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {9, 10, 11});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {12, 13, 14});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {15, 7, 14});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {15, 16, 17});
+ assertTrue(!actual.next());
+
+ assertEquals(actual.getRowCount(), 7);
+
+ // Second, try prefix searches
+ actual.beforeFirst(new long[] {9}, 0);
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {9, 10, 11});
+ assertTrue(!actual.next());
+
+ // Third, try more prefix searches
+ actual.beforeFirst(new long[] {12, 13}, 0);
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {12, 13, 14});
+ assertTrue(!actual.next());
+
+ // Now test the end
+ actual.beforeFirst(new long[] {15}, 0);
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {15, 7, 14});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {15, 16, 17});
+ assertTrue(!actual.next());
+
+ actual.close();
+
+ // variables: lhs intersect rhs = lhs
+ // first, reorder the lhs
+ lvars = new String[] {"y", "z", "x"};
+ lhs = new LiteralTuples(lvars);
+ lhs.appendTuple(new long[] {2, 3, 1});
+ lhs.appendTuple(new long[] {5, 6, 4});
+ lhs.appendTuple(new long[] {5, 6, 7});
+ lhs.appendTuple(new long[] {10, 11, 9});
+ lhs.appendTuple(new long[] {13, 14, 12});
+ lhs.appendTuple(new long[] {16, 17, 15});
+ lhs.appendTuple(new long[] {7, 14, 15});
+
+ actual = TuplesOperations.sort(new LeftJoin(rhs, lhs));
+
+ actual.beforeFirst();
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {5, 6, 4});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {5, 6, 7});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {6, 14, UNBOUND});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {7, 14, 15});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {8, 9, UNBOUND});
+ assertTrue(!actual.next());
+
+ TuplesTestingUtil.closeTuples(new Tuples[] {actual, lhs, rhs});
+
+ // variables: rhs intersect lhs != rhs != lhs
+ rvars = new String[] {"y", "z", "a"};
+ rhs = new LiteralTuples(rvars);
+ rhs.appendTuple(new long[] {5, 6, 3});
+ rhs.appendTuple(new long[] {6, 14, 1});
+ rhs.appendTuple(new long[] {7, 14, 2});
+ rhs.appendTuple(new long[] {8, 9, 11});
+
+ actual = TuplesOperations.sort(new LeftJoin(rhs, lhs));
+
+ actual.beforeFirst();
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {5, 6, 3, 4});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {5, 6, 3, 7});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {6, 14, 1, UNBOUND});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {7, 14, 2, 15});
+ TuplesTestingUtil.testTuplesRow(actual, new long[] {8, 9, 11, UNBOUND});
+ assertTrue(!actual.next());
+
+ TuplesTestingUtil.closeTuples(new Tuples[] {actual, lhs, rhs});
+ }
+
+}
More information about the Mulgara-svn
mailing list