@leo's

Kann man Graphen und Bäume mit SQL durchsuchen? Ja, man kann. Wenn auch mit einigen Einschränkungen, insbesondere muss die Suchtiefe bereits von Beginn weg festgelegt werden.

Aber erst einmal von vorne. Ein Baum (oder Graph) wird in einer Datenbank meist in einer Tabelle abgelegt die über (mindestens) zwei Felder verfügt. Zum einen währen dies ein Feld für die ID des Elternknotens und ein Feld für die ID des Kindknotens. Jeder Knoten kann nun beliebig viele Einträge in dieser Tabelle haben.

Der erste Schritt ist nun noch sehr einfach. Um alle Knoten auf Level 1 zu durchsuchen brauchen wir nicht mehr als eine einfach SQL-Abfrage.

SELECT t.parent AS "Level 0", 
t.child AS "Level 1"
FROM tree AS t
WHERE t.parent = 1
AND t.child = 10;

Wenn wir nun bis Level 2 Durchsuchen wollen müssen wir die Tabelle mit sich selbst verknüpfen. 

SELECT t1.parent AS "Level 0", 
t2.parent AS "Level 1", 
t2.child AS "Level 2"
FROM tree AS t1
RIGHT OUTER JOIN tree t2
ON t1.child = t2.parent
WHERE t1.parent = 1
AND (t1.child = 10
t2.child = 10);

Das ganze kann man dann selbstverständlich nach belieben auf die Spitze treiben. Unten mit einer Suche bis zu Level 4.

SELECT t1.parent AS "Level 0", 
t2.parent AS "Level 1", 
t3.parent AS "Level 2", 
t4.parent AS "Level 3", 
t4.child AS "Level 4"
FROM tree AS t1
RIGHT OUTER JOIN tree t2
RIGHT OUTER JOIN tree t3
RIGHT OUTER JOIN tree t4
ON t3.child = t4.parent
ON t2.child = t3.parent
ON t1.child = t2.parent
WHERE t1.parent = 1
AND (t1.child = 10
OR t2.child = 10
OR i3.child = 10
OR i4.child = 10);

Diese Suche hat natürlich einige Nachteile, so ist es beim Fund eines Knotens nicht möglich die Suche abzubrechen. Alle weiteren Knoten müssen durchsucht werde. Dies kann, wenn man nicht alle Lösungswege braucht, aus Sicht der Performance verheerend sein. Ausserdem muss die Suchtiefe vorbestimmt werden. Allerdings sollte es kein Problem darstellen die Suche dynamisch, zur Laufzweit für die entsprechende Suchtiefe zu generieren, so kann man auch eine nicht erfolgreiche Suche mit einer höheren Tiefe noch einmal laufen lassen.

Der Grosse Vorteil bei der Suche auf der Datenbank ist natürlich das man eine grössere Geschwindigkeit ereichen kann, als wenn jeder Knoten zu einem Clientprogramm transferiert werden muss.

Habe heute ein paar nette Dinge um mit Wikipedia zu basteln entdeckt. Das gesamte deutsche Wikipedia lässt sich hier runterladen. Das dabei ein paar Daten anfallen versteht sich von selbst, die Bildaten belaufen sich gar auf 25 GB. Wenn man die Linktabelle, also die Tabelle die die Verknüpfungen der Seiten untereinander speichert, nicht heruntergeladen wird kann diese auch selbst erstellt werden. Dies dauert aber selbst auf einem schnellen Rechner über eine halbe Stunde.

Wer einige SQL Statments ausführen will ohne gleich den ganzen Datenbestand herunterzuladen kann sich des Services auf wikisign bedienen. Mit diesem kann man SQL Befehle per Webinterface auf die eine Kopie der Wikipediadatenbank absetzen. Man sollte dabie das "limit" in den Statements vernüftig setzen, sonst kann eine Abfrage schnell mal eine Stunde dauern.

Am Freitag haben Dani und ich den Endspurt für die Datenbankprüfungen angesetzt. Auch wenn das ganze mit der trivalen Feststellung gestartet hat das auch seine Firma nicht schneller als Lichtgeschwindigkeit transportieren kann (wer um 14 Uhr in Bern abfährt ist selten um 14 Uhr des selben Tages in Rapperswil ;-)

Ich bereite nun auf Morgen den View, Trigger, Rules und Funktionen Teil vor während er sich nochmals mit jdbc rumschlägt. Am Freitag haben wird dann noch rausgefunden das ein Autoincrement selbst zu implementieren nicht so einfach ist. Nach dem ich mich jetzt erst mal noch mit der Theorie rumgeschlagen habe, habe ich dann das Versucht selbst zu implementieren. Wie man das richtig macht (also ohne Gebastel) steht hier.

Und so hab ich's gemacht. Zuerst macht man eine Tabelle, zb. so:

CREATE TABLE autoincrementtest
(
  id int8 NOT NULL DEFAULT autoincrement(),
  test varchar
)  

Danach die Funktion in pgsql:

CREATE OR REPLACE FUNCTION autoincrement()
  RETURNS int8 AS
$BODY$DECLARE
	maxID int8;
BEGIN
	SELECT MAX(id) 
	INTO maxID
	FROM autoincrementtest;
	
	IF maxID IS NOT NULL THEN
		return maxID+1;
	ELSE
		return 1;
	END IF;
END;$BODY$
  LANGUAGE 'plpgsql' VOLATILE;

Einfügen und abfragen geht dann wie gewohnt:

INSERT INTO autoincrementtest(test)
VALUES('test3');

SELECT * FROM autoincrementtest;