Re: Other tree representations in SQL
Date: Thu, 5 Dec 2002 22:10:03 +0100
Message-ID: <asoerg$dt8$07$1_at_news.t-online.com>
Alfredo Novoa wrote:
> > 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. > > I have counted 131 lines. > > This is a solution using Tutorial D: > > var Tree = real relation { N Char, P Char } key { N, P }; > Tree := relation { tuple { 'A', 'A' }, tuple { 'B', 'A' }, tuple { 'C', 'A' }, > tuple { 'D', 'B' }, tuple { 'E', 'B' }, tuple { 'F', 'C' }, > tuple { 'G', 'C' } }; > TClose(Tree);
I don't think your solution is nice relational code, Alfredo. How would you rename the data part of a Tree node, let's say if "A" had to become "Z"?
Joe was looking for three different tree traversals and for two queries. Where are they in your example?
You do not quite seem to understand the code that I posted. Its actually executable and it produces the following output:
Inorder
D B E A F C G
Preorder
A B D E C F G
Postorder
D E B F G C A
Query for parent of F
C
Left child of A
B
Right child of A
C
I am looking forward to your complete relational example that provides equal functionality, Alfredo.
Below is another step-by-step explanation, what my code actually does. Maybe you can understand small chunkgs a little better than a long source file. I have tried to explain each single functionality block.
// (1) The model: a Java class and a data model at the same time.
public class Tree {
Tree preceding;
Tree subsequent;
String data;
}
// (2) The database file to be used
static final String DATABASE_FILE = "tree.yap";
// (3) A static reference to the database engine
static ObjectContainer objectContainer;
// (4) Three constructors to simplify the creation
// of "Tree" objects with one line of code.
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;
}
// (5) A method that helps to output a "Tree" object to the console
public String toString() {
return " " + data + " ";
}
// (6) A generic "Visitor" interface. Using a Visitor is a common design
// pattern in Java to simulate method pointers
static interface Visitor {
void visit(Object obj);
}
// (7) A Visitor (method pointer, if you like) to be able to print out
// an object.
static Visitor printer() {
return new Visitor() {
public void visit(Object obj) {
System.out.print(obj);
}
};
}
// (8) The normal entry point to Java classes to be able to execute them
public static void main(String[] args) {
}
// (9) Delete the old database file to make sure the example can be run
// multiple times in a row.
new File(DATABASE_FILE).delete();
// (10) Open or create a database with the specified file name
objectContainer = Db4o.openFile(DATABASE_FILE);
// (11) Create a sample tree
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);
}
// (12) Store this sample tree with all nodes.
// This line does a lot of things at the same time: // - the class schema is analysed and created automatically // - all reachable nodes of the tree are traversed and stored
objectContainer.set(createTree());
// (13) This is a S.O.D.A. query for the root node.
// In SQL pseudocode it would read:
// SELECT FROM Tree WHERE Tree.data.equals("A");
//
// Here it loads the complete Tree into memory.
//
// I may post an explanation about memory management
// as an answer to Joe's posting.
Query q = objectContainer.query();
q.constrain(Tree.class);
q.descend("data").constrain("A");
ObjectSet objectSet = q.execute();
return (Tree) objectSet.next();
// (14) Recursive inorder traversal code, using the Visitor
// as a "method pointer".
//
// The visitor could perform any task that you wish on
// each Tree node.
void traverseInorder(Visitor visitor) {
if (preceding != null) {
preceding.traverseInorder(visitor);
}
visitor.visit(this);
if (subsequent != null) {
subsequent.traverseInorder(visitor);
}
}
// (15) Recursive preorder traversal code, using the Visitor
// as a "method pointer".
//
// The visitor could perform any task that you wish on
// each Tree node.
void traversePreorder(Visitor visitor) {
visitor.visit(this);
if (preceding != null) {
preceding.traversePreorder(visitor);
}
if (subsequent != null) {
subsequent.traversePreorder(visitor);
}
}
// (16) Recursive postorder traversal code, using the Visitor
// as a "method pointer".
//
// The visitor could perform any task that you wish on
// each Tree node.
void traversePostorder(Visitor visitor) {
if (preceding != null) {
preceding.traversePostorder(visitor);
}
if (subsequent != null) {
subsequent.traversePostorder(visitor);
}
visitor.visit(this);
}
// (17) A S.O.D.A. query for the parent of a Tree node, using
// identity comparison.
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();
}
// (18) Trivial navigation to the left child of a Tree node
// printing out it's "data". // // This is where object systems are more convenient // and faster than relational databases.
System.out.println(a.preceding);
// (19) Trivial navigation to the right child of a Tree node
// printing out it's "data".
System.out.println(a.subsequent);
// (20) Closing the database file.
objectContainer.close();
Kind regards,
Carl
-- Carl Rosenberger db4o - database for objects - http://www.db4o.comReceived on Thu Dec 05 2002 - 22:10:03 CET