Kategoriebaum aus DB einlesen

Installation und Anwendung von Datenbankschnittstellen wie SQLite, PostgreSQL, MySQL, der DB-API 2.0 und sonstigen Datenbanksystemen.
Benutzeravatar
Whitie
User
Beiträge: 111
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Kategoriebaum aus DB einlesen

Beitragvon Whitie » Samstag 14. Oktober 2006, 19:20

Hallo Forum,
ich bräuchte mal einen kleinen Denkanstoß. Ich habe einen (fest vorgegebenen) Tabellenaufbau in der DB.

[code=]| int_id | int_parent_id | ...
+-------+---------------+----
| 1 | 0 |
| 2 | 1 |[/code]
usw.

Ich fange nun an und lese die Kategorie mit der int_parent_id = 0 aus (Oberkategorie).
Wie kann ich alle abhängigen Kategorien (id's) in eine Liste bringen ? Mir wäre eine nicht rekursive Lösung sehr angenehm, da man nicht weiß, auf wie viel Unterkategorien das ganze mal anwächst. Eine eigene Klasse für die Kategorien könnte man machen (hab ich z. Z. auch), aber diese darf keinen eigenen DB-Zugriff haben. Das erzeugte Objekt muss also die DB-Werte von außen erhalten.

Vielleicht seh ich auch nur den Wald vor lauter Bäumen nicht, bin für jede Anregung dankbar.

Gruß, Whitie
BlackJack

Beitragvon BlackJack » Samstag 14. Oktober 2006, 21:35

Beschreib' das Gewünschte mal etwas genauer. Mehr Zeilen aus der DB, was genau bedeuten die Werte in den Spalten und wie sieht die Eingabe aus und was soll daraufhin in der Ergebnisliste stehen.
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5554
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Telfs (Tirol)
Kontaktdaten:

Re: Kategoriebaum aus DB einlesen

Beitragvon gerold » Samstag 14. Oktober 2006, 21:47

Whitie hat geschrieben:Wie kann ich alle abhängigen Kategorien (id's) in eine Liste bringen?

Hi Whitie!

[code=]SELECT DISTINCT
int_id AS unterkategorie
FROM
tabellenname
WHERE
(int_parent_id = 0)[/code]
Wenn du eine bessere Antwort willst, dann musst du besser erklären was du willst. :K Und -- bessere Angaben machen. (Datenbank, Datenbankschnittstelle,...)

mfg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Benutzeravatar
Whitie
User
Beiträge: 111
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Beitragvon Whitie » Samstag 14. Oktober 2006, 22:23

OK, ich erkläre das mal etwas genauer:

Zur Geschichte:
Es handelt sich um Einstellungstests. Die alte Software (die noch läuft und teuer war) ist in Pascal geschrieben und hat die Kategorien und Testfragen fest im Quelltext eingebaut. Da diese Software eine Datenbank in Form einer Textdatei auf einer Windowsfreigabe benutzt, kommt es häufiger zu Datenverlust und Programmhängern.

Das Projekt:
Um das ganze lästige diskutieren mit dem Chef (Datenverlust liegt immer an mir, nie an der Software) zu vermeiden, habe ich mit einem Kollegen angefangen das ganze Webbasiert zu entwickeln. Das fertige Programm wird später freie Software werden, da wir nur unsere Freizeit für das Projekt opfern und nichts während der Arbeitszeit passiert. Die Testfragen wird mein Chef allerdings nicht freigeben :wink:

Vorraussetzungen:
Das Projekt läuft auf einem abgesicherten LAMPP Paket (Apachefriends) mit mod_python und MySQL 5.0.21. Als Handler dient PSE (Python Servlet Engine).

Probleme:
Die Kategorietabelle sieht so aus:
[code=]--
-- Tabellenstruktur für Tabelle `tab_category`
--

CREATE TABLE `tab_category` (
`int_cat_id` int(11) NOT NULL auto_increment,
`int_parent_id` int(11) NOT NULL default '0' COMMENT 'ID der Oberkategorie aus tab_category',
`str_cat_name` varchar(50) collate utf8_unicode_ci NOT NULL COMMENT 'Name der Kategorie',
`str_cat_opening` text collate utf8_unicode_ci COMMENT 'Einleitung für die Kategorie.',
`bool_active` tinyint(1) NOT NULL default '0' COMMENT 'Kategorie für Test aktiviert ?',
`int_cat_time` tinyint(4) NOT NULL default '0' COMMENT 'Zeit für diese Kategorie in Minuten',
`bool_use_item_time` tinyint(1) NOT NULL default '0' COMMENT 'Zeit pro Item benutzen ?',
PRIMARY KEY (`int_cat_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci COMMENT='Verwaltung der Kategorien' AUTO_INCREMENT=5 ;[/code]

Alle Kategorien die als int_parent_id eine 0 haben sind also eigenständige Tests.
Z.B. Naturwissenschaftliche Berufe, Kaufmännische Berufe, usw.
Jede Kategorie kann erstens Fragen enthalten und zweitens beliebig viele Unterkategorien. Jetzt muss ich einen Kategoriebaum aufbauen, der die Oberkategorie (parent=0) mitsamt aller Unterkategorien und den darin enthaltenen Fragen repräsentiert. Die Fragen sind kein Problem, aber die Kategorien sinvoll auszulesen und in eine Python-Struktur zu bringen.

Ich hoffe, das war genug Information ?

Whitie
BlackJack

Beitragvon BlackJack » Samstag 14. Oktober 2006, 22:58

Bei einer rekursiven Datenstruktur wirst Du um eine rekursive Funktion nicht herumkommen.

Ungetestet und sehr minimal:

Code: Alles auswählen

from itertools import imap


class Category(object):
    def __init__(self, category_id=0):
        self.id = category_id
        self.subcategories = list()
   
    def __iter__(self):
        return iter(self.subcategories)
   
    def add_subcategories(self, subcategories):
        self.subcategories.extend(subcategories)


def _get_categories(cursor, node):
    cursor.execute('SELECT int_cat_id '
                   'FROM tab_category '
                   'WHERE int_parent_id = ? ', node.id)
    node.add_subcategories(imap(Category, cursor))
    for subnode in node:
        get_categories(cursor, subnode)


def get_categories(cursor):
    root = Category()
    _get_categories(cursor, root)
    return root
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5554
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Telfs (Tirol)
Kontaktdaten:

Beitragvon gerold » Sonntag 15. Oktober 2006, 01:21

BlackJack hat geschrieben:

Code: Alles auswählen

    cursor.execute('SELECT int_cat_id '
                   'FROM tab_category '
                   'WHERE int_parent_id = ? ', node.id)

Hi BlackJack!

Bei 20 Hauptkategorien musst du 21 mal auf die Datenbank zugreifen. Wenn ich etwas mit der Zeit gelernt habe, dann dass Datenbankzugriffe teuer sind. 21 Datenbankzugriffe für nur eine Liste mit Werten ist ziemlich viel und bremst das System. Deshalb empfehle ich, alle benötigten Werte in nur einer Abfrage zu holen und dann in einem Rutsch in eine Python-Datenstruktur zu stecken.

Ich zeige mal, wie ich mir das grob vorstelle. Allerdings funktioniert folgender Code nur dann, wenn es nur zwei Ebenen gibt. Also Hauptkategorien mit zugehörigen Unterkategorien. Möchte man unter eine Unterkategorie wieder eine Unterkategorie stellen können, dann müsste man den Code umschreiben.:

Code: Alles auswählen

#!/usr/bin/env python -O
# -*- coding: iso-8859-1 -*-

try:
    # Ab Python 2.5
    import sqlite3
except ImportError:
    # Vor Python 2.5 --> pysqlite --> http://initd.org/tracker/pysqlite
    from pysqlite2 import dbapi2 as sqlite3

from pprint import pprint


conn = sqlite3.connect(":memory:")
cur = conn.cursor()

sql = """
CREATE TABLE tab_category (
  cat_id INTEGER PRIMARY KEY,
  parent_id INTEGER NOT NULL DEFAULT 0,
  cat_name TEXT NOT NULL
);

INSERT INTO tab_category (cat_id, parent_id, cat_name)
  VALUES (1000, 0, 'Erste Oberkategorie');
INSERT INTO tab_category (cat_id, parent_id, cat_name)
  VALUES (2000, 0, 'Zweite Oberkategorie');
INSERT INTO tab_category (cat_id, parent_id, cat_name)
  VALUES (1001, 1000, 'Erste Unterkategorie');
INSERT INTO tab_category (cat_id, parent_id, cat_name)
  VALUES (1002, 1000, 'Zweite Unterkategorie');
INSERT INTO tab_category (cat_id, parent_id, cat_name)
  VALUES (2001, 2000, 'Erste Unterkategorie');
INSERT INTO tab_category (cat_id, parent_id, cat_name)
  VALUES (2002, 2000, 'Zweite Unterkategorie');

CREATE INDEX ix_tab_category_parent_id ON tab_category (parent_id);
"""

cur.executescript(sql)
conn.commit()

cat_dict = {}
sql = """
SELECT parent_id, cat_id, cat_name FROM tab_category
ORDER BY parent_id, cat_id
"""
cur.execute(sql)
for row in iter(cur.fetchone, None):
    parent_id = row[0]
    cat_id = row[1]
    cat_name = row[2]
   
    if parent_id == 0:
        cat_dict[cat_id] = {
            "name": cat_name,
            "subcategories": {}
        }
    else:
        cat_dict[parent_id]["subcategories"][cat_id] = {
            "name": cat_name
        }

cur.close()
conn.close()

pprint(cat_dict)

# hk = Hauptkategorie; uk = Unterkategorie
for hk_key in sorted(cat_dict.keys()):
    hk = cat_dict[hk_key]
    print hk_key, hk["name"]
    for uk_key in sorted(hk["subcategories"].keys()):
        uk = hk["subcategories"][uk_key]
        print "    ", uk_key, uk["name"]

Ja, ich weiß, dass obiger Code wahrscheinlich nur für den der ihn schreibt sofort klar ist. :roll:

Hier das Ergebnis:
[code=]{1000: {'name': u'Erste Oberkategorie',
'subcategories': {1001: {'name': u'Erste Unterkategorie'},
1002: {'name': u'Zweite Unterkategorie'}}},
2000: {'name': u'Zweite Oberkategorie',
'subcategories': {2001: {'name': u'Erste Unterkategorie'},
2002: {'name': u'Zweite Unterkategorie'}}}}
1000 Erste Oberkategorie
1001 Erste Unterkategorie
1002 Zweite Unterkategorie
2000 Zweite Oberkategorie
2001 Erste Unterkategorie
2002 Zweite Unterkategorie[/code]
lg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs

Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Benutzeravatar
Whitie
User
Beiträge: 111
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Beitragvon Whitie » Sonntag 15. Oktober 2006, 19:01

Danke für die Anregungen. Ich probier jetzt mal ein wenig rum und poste dann die Lösung.

Gruß, Whitie
Benutzeravatar
Whitie
User
Beiträge: 111
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Beitragvon Whitie » Sonntag 15. Oktober 2006, 19:49

Hi Leute,
nach Probieren hab ich eine (etwas kürzere) rekursive Lösung genommen. Bestimmt nicht die Schnellste, wegen der DB-Zugriffe, aber funktioniert erstmal.
Ich nehme auch nicht an, das mal mehr als ca. 20 Unterkategorien zu einer Oberkategorie gehören.

Code: Alles auswählen

def parse_categories(category_id, db_connection, list_of_cat_ids = []):
    '''
    Liest den Kategoriebaum rekursiv aus der DB.
    :param category_id Integer ID der Oberkategorie
    :param db_connection Object Instanz der DB-Verbindungsklasse
    :param list_of_cat_ids Leere Liste für die Kategorien
    :return List Liste der ID's aller abhängigen Kategorien.
                 Enthält Oberkategorie als erstes Element.
    '''
    list_of_cat_ids.append(int(category_id))
    data = db_connection.fetch('SELECT int_cat_id FROM tab_category WHERE '
                               'int_parent_id=%s AND bool_active=%s' %
                               (category_id, 1))
    if not data:
        return list_of_cat_ids
    else:
        for db_row in data:
            list_of_cat_ids = parse_categories(db_row[0], db_connection, list_of_cat_ids)
        return list_of_cat_ids

Kategorieliste = parse_categories(Oberkategorie_ID, DB-Verbindung)


Da das ganze nur eine Funktion ist, sollte sich ja bei Bedarf einfach aufrüsten lassen.

Gruß, Whitie
Zuletzt geändert von Whitie am Montag 16. Oktober 2006, 07:13, insgesamt 1-mal geändert.
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Beitragvon Y0Gi » Sonntag 15. Oktober 2006, 23:52

SitePoint: Storing Hierarchical Data in a Database - ist zwar für PHP, aber problemlos übertragbar.
BlackJack

Beitragvon BlackJack » Montag 16. Oktober 2006, 01:00

Whitie hat geschrieben:Hi Leute,
nach Probieren hab ich eine (etwas kürzere) rekursive Lösung genommen. Bestimmt nicht die Schnellste, wegen der DB-Zugriffe, aber funktioniert erstmal.


Nö, funktioniert nicht. Bzw. nur einmal wirklich korrekt. Defaultwerte für Schlüsselwort-Argumente werden nur *einmal* ausgewertet, nämlich wenn ``def`` ausgeführt wird, und *nicht* bei jedem Aufruf der Funktion! Es wird also nicht bei jedem Funktionsaufruf mit einer leeren Liste begonnen.

Und die `fetch()`-Methode auf Connection-Objekten gehört nicht zur DB-API 2.0.
Benutzeravatar
Whitie
User
Beiträge: 111
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Beitragvon Whitie » Montag 16. Oktober 2006, 07:24

BlackJack hat geschrieben:Nö, funktioniert nicht. Bzw. nur einmal wirklich korrekt.

Stimmt. Ich hab in der Eile die Zuweisung vergessen. Habe jetzt das Posting oben editiert. Hat wahrscheinlich nur funktioniert, weil ich kaum Kategorien in der Test-DB habe.

Code: Alles auswählen

for db_row in data:
            list_of_cat_ids = parse_categories(db_row[0], db_connection, list_of_cat_ids)

BlackJack hat geschrieben:Defaultwerte für Schlüsselwort-Argumente werden nur *einmal* ausgewertet, nämlich wenn ``def`` ausgeführt wird, und *nicht* bei jedem Aufruf der Funktion! Es wird also nicht bei jedem Funktionsaufruf mit einer leeren Liste begonnen.

Das ist auch gewollt, da beim nächsten Aufruf mindestens ein Element (erste Kategorie) in der Liste ist und diese ja übergeben wird.

BlackJack hat geschrieben:Und die `fetch()`-Methode auf Connection-Objekten gehört nicht zur DB-API 2.0.

Da hast Du wieder recht. Ich benutze eine eigene Klasse, die die DB-Verbindungen kapselt. Mein `fetch()` macht praktisch `connect()`, `execute()` und `fetchall()` in einem.

Bei mir sieht die Funktion jetzt anders aus. Ich hab die DB-Verbindung ganz rausgenommen und die Funktion als Methode der DB-Klasse geschrieben.

Gruß, Whitie
BlackJack

Beitragvon BlackJack » Montag 16. Oktober 2006, 11:29

Whitie hat geschrieben:
BlackJack hat geschrieben:Nö, funktioniert nicht. Bzw. nur einmal wirklich korrekt.

Stimmt. Ich hab in der Eile die Zuweisung vergessen. Habe jetzt das Posting oben editiert. Hat wahrscheinlich nur funktioniert, weil ich kaum Kategorien in der Test-DB habe.

Code: Alles auswählen

for db_row in data:
            list_of_cat_ids = parse_categories(db_row[0], db_connection, list_of_cat_ids)

BlackJack hat geschrieben:Defaultwerte für Schlüsselwort-Argumente werden nur *einmal* ausgewertet, nämlich wenn ``def`` ausgeführt wird, und *nicht* bei jedem Aufruf der Funktion! Es wird also nicht bei jedem Funktionsaufruf mit einer leeren Liste begonnen.

Das ist auch gewollt, da beim nächsten Aufruf mindestens ein Element (erste Kategorie) in der Liste ist und diese ja übergeben wird.


Das ist sicher nicht gewollt. Und jetzt funktioniert's auch nicht weil Du bei jedem rekursiven Aufruf die bisherigen Ergebnisse einfach wegwirfst. Was auch immer von der "Ebene darüber" in `list_of_cat_ids` stand, wird durch die Zuweisung verworfen.
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Montag 16. Oktober 2006, 13:02

@Whitie: Schau dir vielleicht http://www.sqlalchemy.org mal an... :)

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Benutzeravatar
Whitie
User
Beiträge: 111
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Beitragvon Whitie » Montag 16. Oktober 2006, 13:16

@YOGi
Danke für den Link. Der Traversal Tree hört sich sehr interessant an, aber ich kann die DB-Struktur leider nicht mehr ändern.

@jens
Kenn ich. Ich hab noch keine Zeit gehabt mich mal damit zu befassen. Erstmal bleibe ich bei meinen guten alten SQL-Statements.

@BlackJack
Ich hab es jetzt mal mit mehr verschachtelten Kategorien ausprobiert. Die Funktion tut es so wie sie ist. Auch bei einer Tiefe von 20 Unterkategorien, wo die 19te wiederum 5 Kategorien auf gleicher Ebene enthält. Sie liefert immer genau die Liste, die ich erwarte.

Ich hab das ganze nochmal in Form gebracht und aus meiner Klasse rausgenommen:

Code: Alles auswählen

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import MySQLdb

def parse_categories(category_id, db_cursor, list_of_cat_ids = []):
    '''
    Liest den Kategoriebaum rekursiv aus der DB.
    :param category_id Integer ID der Oberkategorie
    :param db_cursor Object Cursor-Objekt einer DB-Verbindung
    :param list_of_cat_ids Leere Liste für die Kategorien
    :return List Liste der ID's aller abhängigen Kategorien.
                 Enthält Oberkategorie als erstes Element.
    '''
    # Übergebene ID an die Liste anhängen.
    list_of_cat_ids.append(int(category_id))
    sql = ('SELECT int_cat_id FROM tab_category WHERE int_parent_id=%s '
           'AND bool_active=%s')
    # SQL-Abfrage
    db_cursor.execute(sql, (category_id, 1))
    # Alle gefundenen Datensätze abholen
    data = db_cursor.fetchall()
    # Wenn keine Datensätze gefunden wurden, Liste zurückgeben.
    if not data:
        return list_of_cat_ids
    # Wenn Datensätze gefunden wurden, einzeln bearbeiten.
    else:
        for db_row in data:
            # Für jede gefundene ID die Funktion nochmal mit gefundener ID als
            # category_id aufrufen. Die Liste wird mit übergeben, dadurch
            # bleiben bereits vorhandene Einträge erhalten bei der Zuweisung
            # (neue ID wird beim Aufruf angehängt).
            list_of_cat_ids = parse_categories(db_row[0], db_cursor,
                                               list_of_cat_ids)
        # Fertige Liste zurückgeben.
        return list_of_cat_ids

if __name__ == '__main__':
    conn = MySQLdb.connect(host, user, passwd, db)
    cursor = conn.cursor()
    cat_list = parse_categories(4, cursor)
    print cat_list


Ob das guter Stil ist, wage ich zu bezweifeln, aber es funktioniert zuverlässig.

Gruß, Whitie

Edit:
Die übergebenen ID's beziehen sich auf meine DB-Struktur.
BlackJack

Beitragvon BlackJack » Montag 16. Oktober 2006, 15:08

Whitie hat geschrieben:@BlackJack
Ich hab es jetzt mal mit mehr verschachtelten Kategorien ausprobiert. Die Funktion tut es so wie sie ist.


Ja, genau einmal. Ruf sie doch einfach mal ein zweites mal auf.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder