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]

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??

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]

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),
);

(snip)


Any clues or hints??

You may want to read this :
http://c2.com/cgi/wiki?TreeInSql

HTH
Bruno

 

[Peter Otten]

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 :

SQL does not support tree structures, so the use of a relational db is
probably not the best choice.

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.

Would that mean you already have a userfriendly way to enter the data?

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??

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.childrenFor(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.cursor()
def close(self):
self.conn.close()
def childrenFor(self, id):
self.cursor.execute("""
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, "Programming"),
(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.filterwarnings("ignore", module="sqlite")
try:
cmd = sys.argv[1]
except IndexError:
help()
else:
{"create": createDb, "print": printDb}.get(cmd, 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]

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

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.

 

[Bruno Desthuilliers]

Peter Otten wrote:
(snip core and code)

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?

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]

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

SQL does not support tree structures, so the use of a relational db is
probably not the best choice.

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).

--

 

[Andy Todd]

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

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

 

[JanC]

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?

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