Treestructure in SQL

[Peter Otten]

Thomas Weholt wrote:

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