Hierarchical Navigation

Previous Next

Nesting Retrieval Loops

We have shown a simple query in AndSpaces and OrSpaces, but the results of it was a single series of Items. We can also easily navigate a database directly, in a hierarchical way. First, we will show an implementation of Iterator that allows a familiar access pattern in order to scan a set of values. We will use this to do a hierarchical scan, and then we will show the same scan in its most efficient possible no-construction form without the Iterator. The Iterator we show here is a simplified view of the ItemSpaceIterator.

The Basic ItemSpaceIterator

The ItemSpaceIterator encapsulates the native access code. Below is a sketch of the basic capability of it.

public class ItemSpaceIterator implements Iterator {
	ItemSpace db; // the database
	Cu cu; // iterates over the values
	int pl; // 'prefix length' of chars protected from modification

	public ItemSpaceIterator(ItemSpace db, EntityClass ec, Object entity,
			Attribute att) {
		this.db = db;
		cu = Cu.alloc().append(ec).append(entity).append(att);
		pl = cu.length();

	public boolean hasNext() { // Implements iterator
		try {
			return db.next(cu, pl);
		} catch (IOException e) { // not declared by Iterator.hasNext()
			throw new RuntimeException(e);

	public Object next() { // Implements iterator
		return cu.componentAt(pl);
	public void remove() { // Implements Iterator
		try {
		} catch (IOException e) { // not declared by Iterator.remove()
			throw new RuntimeException(e);

	 * Get the current Item (the suffix after pl) into an ItemHolder.
	 * This is more general than next(), which can only return a 'scalar'
	 * component such as a Long, String, Double and so on. An ItemHolder can
	 * handle composite Items any other kind of Item: for example, a Person
	 * class holding a firstName, lastName, and birthdate can implement
	 * ItemHolder and be used here.
	 * @param itemHolder
	 *            obtains the current Item (the suffix of cu after pl)
	 * @throws IOException
	public void next(ItemHolder itemHolder) throws IOException { // Implements iterator
		itemHolder.setItem(cu, pl);

	public void dispose() {

Navigating Using ItemSpaceIterator

Now we will use this iterator to visit a certain supplier using EntityClass SUPPLIER, and for each value of the S_ORDER Attribute, visit the ORDER's and for each order, we visit each O_LINE_ITEM and get the quantity.

package com.infinitydb.manual;

import java.io.IOException;

import com.infinitydb.Attribute;
import com.infinitydb.Cu;
import com.infinitydb.EntityClass;
import com.infinitydb.ItemSpace;

public class HierarchicalAccessIterated {
	// The EntityClasses and Attributes are like enumerations
	// that are the equivalent of tables and columns identifiers.
	static final EntityClass SUPPLIER = new EntityClass(0);
	static final EntityClass ORDER = new EntityClass(1);
	static final EntityClass LINE_ITEM = new EntityClass(2);
	static final Attribute S_ORDER_ID = new Attribute(0);
	static final Attribute O_LINE_ITEM = new Attribute(1);
	static final Attribute L_QUANTITY = new Attribute(2);

	public static void printOrdersOfSupplierWithIterator(ItemSpace db, long supplierId)
			throws IOException {
		ItemSpaceIterator orders = new ItemSpaceIterator(db, SUPPLIER,
				new Long(supplierId), S_ORDER_ID);
		while (orders.hasNext()) {
			Long orderId = (Long)orders.next();
			ItemSpaceIterator lineItems = new ItemSpaceIterator(db, ORDER,
					orderId, O_LINE_ITEM);
			while (lineItems.hasNext()) {
				Long lineItemId = (Long)lineItems.next();
				// We'll show getting quantity as if it needed an Iterator.
				ItemSpaceIterator quantities = new ItemSpaceIterator(db,
						LINE_ITEM, lineItemId, L_QUANTITY);
				if (quantities.hasNext()) {
					Long quantity = (Long)quantities.next();
					// we have a quantity (no surprise) so print it.
					System.out.println("s=" + supplierId + " o=" + orderId +
							" li=" + lineItemId + " q=" + quantity);
			// do other nested loops
			// ..
			// while (hasNext()) {
			// //
			// }

Navigation Natively

Here is the native implementation, not using ItemSpaceIterator for maximum speed.

The yellow lines show that we could eliminate the assumption that line item id's are longs. By treating a line item id as a Cu, it can be composite, perhaps being a combination of order id with a line number within the order. The code can also be agnostic with respect to the data types of the components in the composition. (The Cu.cuAt(int pl) method allocates a new Cu and puts a suffix of this Cu in it).

	public static void printOrdersOfSupplierLowLevel(ItemSpace db,
			long supplierId) throws IOException {
		// We start with a given supplier id
		Cu cuOrder = Cu.alloc().append(SUPPLIER).append(supplierId).append(
		// The 'protected prefix length' 'pl' of the Order Cu.
		int plOrder = cuOrder.length();
		while (db.next(cuOrder, plOrder)) {
			// Now cuOrder ends with a particular order id,
			// no matter what its primitive type or whether
			// it is composite and so on.
			// We know that order id is a long so we extract it from the end.
			long orderId = cuOrder.longAt(plOrder);
			// Use orderId to print facts about the order at the top of the page
			// ..
			// Print the line items.
			Cu cuLineItem = Cu.alloc().append(ORDER).append(orderId).append(
			// The protected prefix length 'pl' of the LineItem Cu.
			int plLineItem = cuLineItem.length();
			while (db.next(cuLineItem, plLineItem)) {
				long lineItemId = cuLineItem.longAt(plLineItem);
//				 Cu lineItemId = cuLineItem.cuAt(plLineItem); 
				Cu cuQuantity = Cu.alloc().append(LINE_ITEM).append(lineItemId)
				int plQuantity = cuQuantity.length();
				if (db.next(cuQuantity, plQuantity)) {
					long quantity = cuQuantity.longAt(plQuantity);
					// we have a quantity (no surprise) so print it.
					System.out.println("s=" + supplierId + " o=" + orderId + " li=" + lineItemId + " q=" + quantity);
//				 lineItemId.dispose(); 
			// do other nested loops
			// ..
			// while (...) {
			// }

The SQL Equivalent

To do the above in SQL we can:

Previous Next

Copyright © 1997-2006 Boiler Bay.