XML-Struktur abbilden - FOREIGN KEY Problem

Hallo NG!

Ich stehe bei einem Problem auf dem Schlauch.

Problem im Allgemeinen:
==================== =====3D=
========
Es soll eine XML-(Baum-)Struktur in einer SQL-Datenbank abgebildet
werden. (Die Rahmenbedingungen sind fest.) Die Struktur besteht aus
Knoten, die selbst Elter eines anderen Knotens sein können.
ZB.:








In einer Tabelle "objekt" befinden sich alle Objekte mit den
dazugehörigen Attributen, aber das ist hier nicht weiter interessant.
Diese Tabelle wird in PHP ausgelesen (geparst) und als XML ausgegeben
(- was hier nicht das Problem darstellt).
Es geht viel mehr um die Relation zwischen den "Objekten" und deren
Pflege (sprich: Löschen von Objekten samt Kindern und dem Verschieben
von einem Objekt in ein anderes.)

Details:
==================== =====3D=
========
(Eine bisherige (sehr weit vom Optimum entfernte) PHP-Lösung sieht
folgendermaßen aus:
Ein Objekt wird gelöscht. Seine Kinder werden gelöscht. Die
Kindes-Kinder werden gelöscht. Usw. Also eine Rekursive Lösung mit
O(n) Queries. Das ist Schlecht!
Tabellen-Schema sah so aus:
[ objekt ]
[ id | parent | ...]
)
Strebenswert wäre eine Lösung mit O(1) Queries, wobei sich die DB
Engine um alles andere kümmert. Meinem Verständnis nach müsste es
mit Fremdschlüsseln (FOREIGN KEYs) realisierbar sein. (Dazu ist
bereits ein Upgrade des MySQL Servers von 3.23 auf 4.1 vorgenommen
worden.)
Ich habe es mit dem DBDesigner 4 versucht zu modellieren. Allerdings
akzeptiert der MySQL Server diese CREATEs nicht, oder nur mit Pfuschen
und dann werden auch die INSERTs verweigert.
Langes Rumprobieren *schäm* und missverständnis der Dokumentation hat
mich komplett verwirrt. Bitte euch also um Hilfe!

Meine Grundidee:
==================== =====3D=
========
Folgendes Schema:

[ objekt ]
[ id | ... ]
/* Darin sind die Objektinformationen */

[ elter ]
[ id | objektid ]
/* "ist-elter-Relation" :=3D Diese Objekt ist Elter */

[ kind ]
[ id | elterid | objektid ]
/* "ist-kind-Relation" :=3D Dieses Objekt ist Kind */

"ist-elter" und "ist-kind" schließen sich nicht aus, da ich von einem
(XML-) Baum ausgehe. Ein Elter kann mehrere Kinder haben (anders ist es
ja eine lineare Liste).
Wenn ich ein Objekt lösche, sollen die Kinder (und Kindes-Kinder,
usw.) ebenfalls gelöscht werden.

Ist es Möglich?
==================== =====3D=
========
Wie erzeuge ich die richtigen Fremdschlüssel so, dass die Kinder
gelöscht werden?
Es müssen doch 2 Fremdschlüssel existieren, damit ein gelöschtes
Kind, das gleichzeitig Elter ist, seine Kinder löscht, usw.

Mit freundlichen Grüßen

Alex Tugarev

Re: XML-Struktur abbilden - FOREIGN KEY Problem

mail@alex-t.de schrieb:
> Hallo NG!
>
> Ich stehe bei einem Problem auf dem Schlauch.
>
> Problem im Allgemeinen:
> =================================
> Es soll eine XML-(Baum-)Struktur in einer SQL-Datenbank abgebildet
> werden. (Die Rahmenbedingungen sind fest.)

Schade. Es gibt sicherlich besser geeignete Werkzeuge zum Speichern
und Verarbeiten von XML als ausgerechnet SQL...

> Die Struktur besteht aus
> Knoten, die selbst Elter eines anderen Knotens sein können.
> Z.B.:
>
>
>
>
>
>
>
>

.... Du könntest mal Google zum Thema 'Trees+SQL' bemühen. Ähnliche
Probleme werden auch hier in der Gruppe gelegentlich behandelt. IIRC
werden dort andere als die von Dir ins Auge gefasste Datenstruktur
präferiert:

> Meine Grundidee:
> =================================
> Folgendes Schema:
>
> [ objekt ]
> [ id | ... ]
> /* Darin sind die Objektinformationen */
>
> [ elter ]
> [ id | objektid ]
> /* "ist-elter-Relation" := Diese Objekt ist Elter */
>
> [ kind ]
> [ id | elterid | objektid ]
> /* "ist-kind-Relation" := Dieses Objekt ist Kind */
>
> "ist-elter" und "ist-kind" schließen sich nicht aus, da ich von einem
> (XML-) Baum ausgehe. Ein Elter kann mehrere Kinder haben (anders ist es
> ja eine lineare Liste).
> Wenn ich ein Objekt lösche, sollen die Kinder (und Kindes-Kinder,
> usw.) ebenfalls gelöscht werden.
>
> Ist es Möglich?

Möglich ist ja fast alles. Du kannst Nägel mit einem Fahrradschloss in
die Wand hauen und auch, genügend Zeit vorausgesetzt, mit dem Finger
Löcher in Beton bohren. Ob das sinnvoll ist, oder ob es möglicherweise
ein für diese Aufgabe besser geeignetes Werkzeug gibt, das steht auf
einem ganz anderen Blatt.

Zumindest scheint es schon Datenbanken zu geben, die XML einigermaßen
nativ verarbeiten können. Ob die dann auch SQL sprechen, weiß ich
nicht ...

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Hi Alex

mail@alex-t.de wrote:
> Es soll eine XML-(Baum-)Struktur in einer SQL-Datenbank abgebildet
> werden. (Die Rahmenbedingungen sind fest.) Die Struktur besteht aus
> Knoten, die selbst Elter eines anderen Knotens sein können.

Du interessierst dich für Nested Sets.
Vielleicht hilft das weiter:
http://www.klempert.de/php/nested_sets/

HTH, Johannes

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Andreas
--
Andreas Kretschmer
Linux - weil ich es mir wert bin!
GnuPG-ID 0x3FFF606C http://wwwkeys.de.pgp.net

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Christian Kirsch schrieb:
> Schade. Es gibt sicherlich besser geeignete Werkzeuge zum Speichern
> und Verarbeiten von XML als ausgerechnet SQL...
Diese Weisheit ist mir auch bekannt.
Nenne weiter unten Gründe für das Beibehalten der "schlechten"
Rahmenbedingungen.


> ... Du könntest mal Google zum Thema 'Trees+SQL' bemühen. Ähnliche
> Probleme werden auch hier in der Gruppe gelegentlich behandelt. IIRC
> werden dort andere als die von Dir ins Auge gefasste Datenstruktur
> präferiert:
Ja und richtig. Die "guten" Lösungen habe ich mir genau angeschaut. Eine
Lösung mit Triggern wäre wahrscheinlich auch möglich und denkbar -
versuche es aber zu nächst über FKs zu lösen, okay?
Der Rest den google ausgibt ist nur das Parsen eines Baumes, und das ist
nicht mein Problem. Mir geht es lediglich um die Konsistenz.


> Möglich ist ja fast alles. ... Ob das sinnvoll ist, oder ob es möglicherweise
> ein für diese Aufgabe besser geeignetes Werkzeug gibt, das steht auf
> einem ganz anderen Blatt.
Ohne zu viele Details zu nennen: Auch wenn es so aussieht, als ob diese
Datenstruktur in dem Falle wenig gut ist, kann ich nur sagen, dass es in
dem speziellen Einsatz auch vorteilhaft ist. Wenn man lange genug
nachdenkt, dann stellt man fest, dass auch diese DS manchmal sehr gut
ist. Einfügen und Auswählen von Datensätzen tritt als Anwendungsfall
sehr(!) viel häufiger in dieser Applikation auf als löschen, und die
Performanz ist hier sehr wichtig.


> Zumindest scheint es schon Datenbanken zu geben, die XML einigermaßen
> nativ verarbeiten können. Ob die dann auch SQL sprechen, weiß ich
> nicht ...
Ja, das stimmt auch. Hast zu 100 Prozent recht. Leider habe ich das
nicht zu entscheiden. Und das ist in 90 Prozent aller Fälle so!
Die Diskussion über passende Werkzeuge erspare ich mir und dir - hoffe
dass da so akzeptiert wird.

Danke für die Antwort!

MfG

AT

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Andreas Kretschmer schrieb:
> Nein, selber hab ich da keine Erfahrung, hab nur den DocBot befragt.

Danke für die Antwort. Habe die Quellen überflogen. Die Lösungen sehen
sehr gut aus! Folgendes Problem: MySQL 4.1 reicht dafür nicht.

Ich müsste entweder auf 5.0 umsteigen (ungerne) oder auf PostgreSQL (in
diesem Falle gibt es da noch einige bessere Lösungen).

Doch wie gesagt, da sind diese Rahmenbedingungen.

MfG

AT


PS: Suche nach einer Lösung mit MySQL 4.1 und wahrscheinlich mit dem
korrekten Einsatz von FKs.

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Johannes Vogel schrieb:
> Du interessierst dich für Nested Sets.
> Vielleicht hilft das weiter:
> http://www.klempert.de/php/nested_sets/

Ebenfalls danke für die Antwort. Ich schaue mir diese Lösung noch
genauer an. Besonders im Hinblick auf die Änderungen in der
Datenhaltung. Soweit diese die Bestehenden (höher priorisierten)
Methoden nicht stört, wäre es eine Überlegung!

Vielen Dank!

MfG

AT

Re: XML-Struktur abbilden - FOREIGN KEY Problem

mail@alex-t.de wrote:

[ "plattgeklopfte" Hierarchie gleichartiger Objekte ]

> Es geht um die Relation zwischen den "Objekten" und deren
> Pflege (sprich: Löschen von Objekten samt Kindern und dem Verschieben
> von einem Objekt in ein anderes.)
....

> Strebenswert wäre eine Lösung mit O(1) Queries, wobei sich die DB
> Engine um alles andere kümmert. Meinem Verständnis nach müsste es
> mit Fremdschlüsseln (FOREIGN KEYs) realisierbar sein.

Ja. Beispiel:

Wir wollen die folgende Hierarchie abbilden:

1
2___20
\_21
3___30__300
\_31

CREATE TABLE t1 (
id INT PRIMARY KEY,
parent INT,
KEY (parent),
FOREIGN KEY (parent) REFERENCES t1 (id) ON DELETE CASCADE
) ENGINE=InnoDB

INSERT INTO t1 (id) VALUES (1), (2), (3);
INSERT INTO t1 (id, parent) VALUES (20,2), (21,2);
INSERT INTO t1 (id, parent) VALUES (30,3), (31,3), (300,30);

SELECT * FROM t1 ORDER BY id;
+-----+--------+
| id | parent |
+-----+--------+
| 1 | NULL |
| 2 | NULL |
| 3 | NULL |
| 20 | 2 |
| 21 | 2 |
| 30 | 3 |
| 31 | 3 |
| 300 | 30 |
+-----+--------+

Wenn wir Knoten 3 löschen, verschwinden all seine Kinder:

DELETE FROM t1 WHERE id=3;
SELECT * FROM t1 ORDER BY id;
+----+--------+
| id | parent |
+----+--------+
| 1 | NULL |
| 2 | NULL |
| 20 | 2 |
| 21 | 2 |
+----+--------+


XL

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Andreas
--
q: why do so many people take an instant dislike to mysql?
a: it saves time (oicu in #postgresql)
Explaining the concept of referential integrity to a mysql user is like
explaining condoms to a catholic (Shadda in #postgresql)

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Axel Schwenke schrieb:
> mail@alex-t.de wrote:
>
> [ "plattgeklopfte" Hierarchie gleichartiger Objekte ]
>
>> Es geht um die Relation zwischen den "Objekten" und deren
>> Pflege (sprich: Löschen von Objekten samt Kindern und dem Verschieben
>> von einem Objekt in ein anderes.)
> ...
>
>> Strebenswert wäre eine Lösung mit O(1) Queries, wobei sich die DB
>> Engine um alles andere kümmert. Meinem Verständnis nach müsste es
>> mit Fremdschlüsseln (FOREIGN KEYs) realisierbar sein.
>
> Ja. Beispiel:
>
> Wir wollen die folgende Hierarchie abbilden:
>
> 1
> 2___20
> \_21
> 3___30__300
> \_31
>
> CREATE TABLE t1 (
> id INT PRIMARY KEY,
> parent INT,
> KEY (parent),
> FOREIGN KEY (parent) REFERENCES t1 (id) ON DELETE CASCADE
> ) ENGINE=InnoDB
>
> INSERT INTO t1 (id) VALUES (1), (2), (3);
> INSERT INTO t1 (id, parent) VALUES (20,2), (21,2);
> INSERT INTO t1 (id, parent) VALUES (30,3), (31,3), (300,30);
>
> SELECT * FROM t1 ORDER BY id;
> +-----+--------+
> | id | parent |
> +-----+--------+
> | 1 | NULL |
> | 2 | NULL |
> | 3 | NULL |
> | 20 | 2 |
> | 21 | 2 |
> | 30 | 3 |
> | 31 | 3 |
> | 300 | 30 |
> +-----+--------+
>
> Wenn wir Knoten 3 löschen, verschwinden all seine Kinder:
>
> DELETE FROM t1 WHERE id=3;
> SELECT * FROM t1 ORDER BY id;
> +----+--------+
> | id | parent |
> +----+--------+
> | 1 | NULL |
> | 2 | NULL |
> | 20 | 2 |
> | 21 | 2 |
> +----+--------+
>
>
> XL

Ich /danke/ dir vielmals!

Und ich habe viel zu weit und viel zu kompliziert gedacht, ausserdem hat
mich von dieser Lösung die MySQL Dokumentation abgehalten, da ich meine
dort gelesen zu haben, dass in 4.1 keine Fremdschlüssel auf die gleiche
Tabelle angelegt werden können. Vielleicht war es eine Dokumentation für
eine frühere Version, aber ich bedauere es nicht ausprobiert zu haben.

Das ist genau das, was ich gesucht habe, quasi ein Einzeiler.

Grüße

AT

Re: XML-Struktur abbilden - FOREIGN KEY Problem

Nachtrag:
Ich bin wirklich ein Schussel. Habe mir das hier
[http://dev.mysql.com/doc/refman/4.1/en/innodb-foreign-key-c onstraints.html]
ausgedruckt und mal /gründlich/ durchgelesen.

Zitat:
"Note that InnoDB supports foreign key references within a table. In
these cases, “child table records” really refers to dependent records
within the same table."