Re: Other tree representations in SQL

--CELKO-- wrote:

> The first people to come up with the code and some explanation of how
> it works for inorder and postorder trees will get credit in my next
> book on trees and hierarchies in SQL.  Not exactly as good as a beer,
> but some chance for fame and glory along with a free copy of the book
> when it is published.

Excuse me for jumping on the train, Joe.

Since hardly anyone here seems to understand that there are usecases where object databases work better than relational databases, I would like to provide some sample code, to prove it. Since the code is straight-forward OO withouth the need for rocket science SQL, it took me just a little more than an hour to write. It contains all the tasks outlined in your posting and the class model directly defines the scheme to be used by the database engine.

I challenge any relational system to provide the same functionality with an equally small number of lines of code. I challenge any relational system for a performance race on any kind of tree search or tree traversal.

The attached code uses S.O.D.A. for querying. http://sourceforge.net/projects/sodaquery

If you would like to experiment with the running code yourself, all you need is a Java environment and the db4o.jar library, included in the zip directly downloadable from here:
http://www.db4o.com/db4o/db4o2.5.zip

Just one more question for SQL trees:
I wonder how you would balance them?
With an object database the task is dead simple:

- load the tree into memory from the root
- balance the tree
- store the root

Kind regards,
Carl

And here comes the code.
The method names hopefully are self-documenting.

import java.io.*;
import com.db4o.*;
import com.db4o.query.*;

public class Tree {

    public static void main(String[] args) {

        new File(DATABASE_FILE).delete();
        objectContainer = Db4o.openFile(DATABASE_FILE);

        storeTree();

        Tree a = queryForRootA();

        System.out.println("\n\nInorder");
        a.traverseInorder(printer());

        System.out.println("\n\nPreorder");
        a.traversePreorder(printer());

        System.out.println("\n\nPostorder");
        a.traversePostorder(printer());

        Tree f = a.subsequent.preceding;
        Tree c = queryForParent(f);
        System.out.println("\n\nQuery for parent of" + f);
        System.out.println(c);

        System.out.println("\nLeft child of" + a);
        System.out.println(a.preceding);

        System.out.println("\nRight child of" + a);
        System.out.println(a.subsequent);

        objectContainer.close();

    static Tree createTree() {

        Tree b = new Tree("B", new Tree("D"), new Tree("E"));
        Tree c = new Tree("C", new Tree("F"), new Tree("G"));
        return new Tree("A", b, c);

    static void storeTree() {

        objectContainer.set(createTree());
}

    static Tree queryForRootA() {

        Query q = objectContainer.query();
        q.constrain(Tree.class);
        q.descend("data").constrain("A");
        ObjectSet objectSet = q.execute();
        return (Tree) objectSet.next();

    void traverseInorder(Visitor visitor) {

        if (preceding != null) {
            preceding.traverseInorder(visitor);
        }
        visitor.visit(this);
        if (subsequent != null) {
            subsequent.traverseInorder(visitor);
        }

    void traversePreorder(Visitor visitor) {

        visitor.visit(this);
        if (preceding != null) {
            preceding.traversePreorder(visitor);
        }
        if (subsequent != null) {
            subsequent.traversePreorder(visitor);
        }

    void traversePostorder(Visitor visitor) {

        if (preceding != null) {
            preceding.traversePostorder(visitor);
        }
        if (subsequent != null) {
            subsequent.traversePostorder(visitor);
        }
        visitor.visit(this);

    static Tree queryForParent(Tree tree) {

        Query q = objectContainer.query();
        q.constrain(Tree.class);
        q.descend("preceding").constrain(tree).identity().or(
            q.descend("subsequent").constrain(tree).identity());
        ObjectSet objectSet = q.execute();
        return (Tree) objectSet.next();

    public String toString() {

        return " " + data + " ";
}

    static Visitor printer() {

        return new Visitor() {
            public void visit(Object obj) {
                System.out.print(obj);
            }
        };

    static interface Visitor {

        void visit(Object obj);
}

    public Tree() {
}

    public Tree(String data) {

        this.data = data;
}

    public Tree(String data, Tree preceding, Tree subsequent) {

        this.data = data;
        this.preceding = preceding;
        this.subsequent = subsequent;

    Tree preceding;
    Tree subsequent;
    String data;

    static final String DATABASE_FILE = "tree.yap";     static ObjectContainer objectContainer; } Received on Wed Dec 04 2002 - 14:33:24 CET