Treestructure in SQL

[Thomas Weholt]

Hi,

I need to define tree-like structure for content categories in a simple CMS
project. I got a table in a SQLite database which looks like this :

CREATE TABLE category (
CAT_ID INTEGER PRIMARY KEY,
CAT_PARENT_ID integer,
CAT_NAME varchar(100) NOT NULL,
CAT_DESCRIPTION varchar(250),
);

It makes is possible to create a tree of categories, linking subnodes in the
the tree to parent nodes using the CAT_PARENT_ID and it works nice, but I'm
having trouble visualizing it.

Say I got these records in the table :
Id, Parent-id, Name
1, 0, Games
2, 1, Counter-strike
3, 1, Boardgames
4, 0, Programming
5, 4, Python
6, 4, XML
7, 5, Web

Where 0 as parent-id symbolizes "root"-level of the treestructure.

Now I need either a SQL-statement compatible with SQLite or some code
snippet that will give me :

Games
Games, Counter-strike
Games, Boardgames
Programming
Programming, Python
Programming, Python, Web
Programming, XML

Any clues or hints??

Best regards,
Thomas

[Diez B. Roggisch]

Re: Treestructure in SQL

> Now I need either a SQL-statement compatible with SQLite or some code[color=blue]
> snippet that will give me :
>
> Games
> Games, Counter-strike
> Games, Boardgames
> Programming
> Programming, Python
> Programming, Python, Web
> Programming, XML
>
> Any clues or hints??[/color]

Its not possible in a generic way. what would be possible is to create one
for a certain number of levels:

select lv0.Name, lv1.Name from category lv0, category lv1 where lv0.cat_id =
lv1.parent_id

You can extend this to every level you want.

The reason is that for every parent-child relation, the database needs a
cross-product between the two sets the relation is build upon. On the
cross-product (which will contain _all_ possible relation, e.g
(Games,Python), the filtering criteria is applied.

I'm currently not sure what happens if you look for three levels, but look
at a two-level branch. Maybe outer joins help you there, but I'd have to
play around with that - and for that I'd have to setup a database right
here :)

Regards,

Diez

[Bruno Desthuilliers]

Re: Treestructure in SQL

Thomas Weholt wrote:[color=blue]
> Hi,
>
> I need to define tree-like structure for content categories in a simple CMS
> project. I got a table in a SQLite database which looks like this :
>
> CREATE TABLE category (
> CAT_ID INTEGER PRIMARY KEY,
> CAT_PARENT_ID integer,
> CAT_NAME varchar(100) NOT NULL,
> CAT_DESCRIPTION varchar(250),
> );
>[/color]

(snip)
[color=blue]
>
> Any clues or hints??[/color]

You may want to read this :

http://c2.com/cgi/wiki?TreeInSql

HTH
Bruno

[Peter Otten]

Re: Treestructure in SQL

Thomas Weholt wrote:
[color=blue]
> I need to define tree-like structure for content categories in a simple
> CMS project. I got a table in a SQLite database which looks like this :[/color]

SQL does not support tree structures, so the use of a relational db is
probably not the best choice.
[color=blue]
>
> CREATE TABLE category (
> CAT_ID INTEGER PRIMARY KEY,
> CAT_PARENT_ID integer,
> CAT_NAME varchar(100) NOT NULL,
> CAT_DESCRIPTION varchar(250),
> );
>
> It makes is possible to create a tree of categories, linking subnodes in
> the the tree to parent nodes using the CAT_PARENT_ID and it works nice,
> but I'm having trouble visualizing it.[/color]

Would that mean you already have a userfriendly way to enter the data?
[color=blue]
> Say I got these records in the table :
> Id, Parent-id, Name
> 1, 0, Games
> 2, 1, Counter-strike
> 3, 1, Boardgames
> 4, 0, Programming
> 5, 4, Python
> 6, 4, XML
> 7, 5, Web
>
> Where 0 as parent-id symbolizes "root"-level of the treestructure.
>
> Now I need either a SQL-statement compatible with SQLite or some code
> snippet that will give me :
>
> Games
> Games, Counter-strike
> Games, Boardgames
> Programming
> Programming, Python
> Programming, Python, Web
> Programming, XML
>
> Any clues or hints??[/color]

Well, I wanted to try out sqlite anyway, so I made a little Python wrapper
around your table to print it like shown above.
However, I ended up with much of the data in memory, so I still cannot see
why you favoured a db over pickling a tree of Python objects.

<code>
import sqlite, sys

class Node(object):
def __init__(self, tree, parentId, id, name):
self.tree = tree
self.id = id
self.parentId = parentId
self.name = name

def children(self):
return self.tree.child renFor(self.id)
def __str__(self):
return self.name
def printSelf(self, parents):
if parents is None:
parents = []
parents.append( self)
print ", ".join([str(n) for n in parents])
for child in self.children() :
child.printSelf (parents)
parents.pop()

class RootNode(Node):
def printSelf(self) :
for child in self.children() :
child.printSelf ([])

class Tree(object):
def __init__(self):
self.conn = sqlite.connect( db="db", mode=755)
self.cursor = self.conn.curso r()
def close(self):
self.conn.close ()
def childrenFor(sel f, id):
self.cursor.exe cute("""
SELECT
CAT_PARENT_ID,
CAT_ID,
CAT_NAME
FROM category
WHERE CAT_PARENT_ID = %d;""" % id)
return [Node(self, *row) for row in self.cursor]

def createDb():
conn = sqlite.connect( db="db", mode=755)
cursor = conn.cursor()
sql_create = """
CREATE TABLE category (
CAT_ID INTEGER PRIMARY KEY,
CAT_PARENT_ID integer,
CAT_NAME varchar(100) NOT NULL,
CAT_DESCRIPTION varchar(250)
);"""
cursor.execute( sql_create)

#Id, Parent-id, Name
records = [
(1, 0, "Games"),
(2, 1, "Counter-strike"),
(3, 1, "Boardgames "),
(4, 0, "Programmin g"),
(5, 4, "Python"),
(6, 4, "XML"),
(7, 5, "Web")
]
for record in records:
sql_insert = "INSERT INTO category VALUES (%d, %d, '%s', '');" %
record
cursor.execute( sql_insert)
conn.commit()
conn.close()

def printDb():
tree = Tree()
root = RootNode(tree, 0, 0, "<root>")
root.printSelf( )

def help():
print """
provide one of the following commands:
create - creates a tiny sample database "db"
print - prints the tree
"""

if __name__ == "__main__":
import warnings
warnings.filter warnings("ignor e", module="sqlite" )
try:
cmd = sys.argv[1]
except IndexError:
help()
else:
{"create": createDb, "print": printDb}.get(cm d, help)()
</code>

The script includes the table generation code, in case anyone other than the
OP wants to play with it.

Peter

PS: In the spirit of "It's easier to ask forgiveness than permission", is
there a generally agreed upon upper size limit for usenet posts?

[Kylotan]

Re: Treestructure in SQL

"Thomas Weholt" <2002@weholt.or g> wrote in message news:<KZPwb.142 6$Y06.19413@new s4.e.nsc.no>...
[color=blue]
> Now I need either a SQL-statement compatible with SQLite or some code
> snippet that will give me :
>
> Games
> Games, Counter-strike
> Games, Boardgames
> Programming
> Programming, Python
> Programming, Python, Web
> Programming, XML[/color]

Is it a big problem to make several SELECTS in a loop?

The first select gets all rows where parent_id = 0. Then print that
node, and then for each row in that SELECT result, search for all
nodes that have parent_id equal to this one, and so on. You probably
want to do it recursively rather than iteratively if you want
depth-first traversal as shown in your example.

Alternatively, if I was always showing the entire list of nodes, I'd
just do one SELECT and create their tree order in code.

--
Ben Sizer

[Bruno Desthuilliers]

Re:[OT] Treestructure in SQL

Peter Otten wrote:
(snip core and code)
[color=blue]
>
> PS: In the spirit of "It's easier to ask forgiveness than permission", is
> there a generally agreed upon upper size limit for usenet posts?
>[/color]
I don't know of any formal size limit, but I don't think anyone would
complain about the size of that one.

[Dennis Lee Bieber]

Re: Treestructure in SQL

Peter Otten fed this fish to the penguins on Tuesday 25 November 2003
16:53 pm:

[color=blue]
> SQL does not support tree structures, so the use of a relational db is
> probably not the best choice.
>[/color]
SQL doesn't, but with a enough programming an rdbm can still be used
-- look at how many genealogy programs are built on top of them (the
late Ultimate Family Tree and The Master Genealogist use Visual FoxPro,
Legacy uses JET).

--[color=blue]
> =============== =============== =============== =============== == <
> wlfraed@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
> wulfraed@dm.net | Bestiaria Support Staff <
> =============== =============== =============== =============== == <
> Bestiaria Home Page: http://www.beastie.dm.net/ <
> Home Page: http://www.dm.net/~wulfraed/ <[/color]

[Andy Todd]

Re: Treestructure in SQL

Thomas Weholt wrote:[color=blue]
> Hi,
>
> I need to define tree-like structure for content categories in a simple CMS
> project. I got a table in a SQLite database which looks like this :
>
> CREATE TABLE category (
> CAT_ID INTEGER PRIMARY KEY,
> CAT_PARENT_ID integer,
> CAT_NAME varchar(100) NOT NULL,
> CAT_DESCRIPTION varchar(250),
> );
>
> It makes is possible to create a tree of categories, linking subnodes in the
> the tree to parent nodes using the CAT_PARENT_ID and it works nice, but I'm
> having trouble visualizing it.
>
> Say I got these records in the table :
> Id, Parent-id, Name
> 1, 0, Games
> 2, 1, Counter-strike
> 3, 1, Boardgames
> 4, 0, Programming
> 5, 4, Python
> 6, 4, XML
> 7, 5, Web
>
> Where 0 as parent-id symbolizes "root"-level of the treestructure.
>
> Now I need either a SQL-statement compatible with SQLite or some code
> snippet that will give me :
>
> Games
> Games, Counter-strike
> Games, Boardgames
> Programming
> Programming, Python
> Programming, Python, Web
> Programming, XML
>
> Any clues or hints??
>
> Best regards,
> Thomas
>
>[/color]

Its perfectly reasonable to store a hierarchy in a database. In fact
Oracle has a special extension to SQL to support it (the CONNECT BY ..
START WITH clause). When this isn't available you may want to consider
what Joe Celko calls a 'preorder tree traversal';

http://www.intelligententerprise.com/001020/celko.shtml

Which, I think, is explained in a slightly clearer fashion here;

http://www.sitepoint.com/article/1105

Of course, if you don't want to store the left and right values as this
technique suggests, your existing model is perfectably usable. When
retrieving the data I'd suggest you use some kind of recursive function,
that way you don't care how many 'levels' there are in your hierarchy.

HTH,
Andy
--
--------------------------------------------------------------------------------
From the desk of Andrew J Todd esq - http://www.halfcooked.com/

[JanC]

Re: Treestructure in SQL

Peter Otten <__peter__@web. de> schreef:
[color=blue]
> PS: In the spirit of "It's easier to ask forgiveness than permission", is
> there a generally agreed upon upper size limit for usenet posts?[/color]

There is no official limit, but a generally agreed upon safe upper size
limit by newsserver & newsclient authors is 1 MiB, headers included.

--
JanC

"Be strict when sending and tolerant when receiving."
RFC 1958 - Architectural Principles of the Internet - section 3.9