GOV Entwicklung Relationen-Index

Definitionen

Kante

Eine Kante ist eine Relationen zwischen zwei GOV-Objekten. Sie ist gerichtet und hat einen Anfangs- und einen End-Knoten. Im Beispiel sind Kanten mit dem Buchstaben 'K' beschriftet.

Pfade

Ein Pfad ist eine Menge von adjazenten Kanten. Er ist gerichtet und hat einen Anfangs- und einen End-Knoten. Zwischen zwei GOV-Objekten kann es zwei oder mehr verschiedene Pfade geben. Im Beispiel sind Pfade rot eingezeichnet und mit dem Buchstaben 'P' beschriftet.

Datenstruktur

Der Relationen-Index ist in drei Tabellen abgelegt:

• Menge aller Relationen (diese Tabelle gibt es bereits) - Nummer, Anfangsknoten, Endknoten
• Menge alle Pfade - Nummer, Anfangsknoten, Endknoten (im Beispiel p.nummer, p.anfang, p.ende, p.laenge)
• Menge von (p,k)-Paaren wenn Kante k auf Pfad p - Pfad, Kante (im Beispiel pk.pfad, pk.kante)

Einfügen einer neuen Kante

Habe die neue Kante die Anfangsknoten ka und Endknoten ke (genauer sind ka und ke die Nummern der Knoten).

Die neue Kante in die Tabelle der neuen Pfade eintragen:

INSERT INTO n (v,n) VALUES (0,0);

alle Vorgänger-Pfade in die Tabelle der neuen Pfade eintragen:

INSERT INTO n (v,n) SELECT nummer,0 FROM p WHERE p.ende = ''ka'';

alle Nachfolger-Pfade in die Tabelle der neuen Pfade eintragen:

INSERT INTO n (v,n) SELECT 0,nummer FROM p WHERE p.anfang  = ''ke'';

alle Pfade, die über die neue Kante laufen:

INSERT INTO n (v,n) SELECT p1.nummer, p2.nummer FROM p p1, p p2 WHERE p1.ende=''ka'' AND p2.anfang=''ke'';

aus N neue Einträge in P erstellen:

die eine neue Kante:

INSERT INTO p SELECT n.nummer,''ka'',''ke'',1 FROM n WHERE n.v=0 AND n.n=0;

alle Pfade, die die neue Kante als letzte Kante haben:

INSERT INTO p SELECT n.nummer,p.anfang, ''ke'', p.laenge+1 FROM n,p WHERE n.v = p.nummer AND n.n=0;

alle Pfade, die die neue Kante als erste Kante haben:

INSERT INTO p SELECT n.nummer, ''ka'' ,p.ende,p.laenge+1  FROM n,p WHERE n.n = p.nummer AND n.v=0;

alle Pfade, die die neue Kante in der Mitte enthalten:

INSERT INTO p SELECT n.nummer, p1.anfang , p2.ende,p1.laenge+p2.laenge+1  FROM n, p p1, p p2 WHERE p1.nummer = n.v AND p2.nummer = n.n AND n.v!=0 AND n.n!=0;

in PK eintragen:

die eine neue Kante:

INSERT INTO pk SELECT n.nummer,n.nummer  FROM n WHERE n.v=0 AND n.n=0;

den Rest (die letzte Bedingung schließen den Pfad, der nur aus der neuen Kante besteht, aus)

INSERT INTO pk SELECT n.nummer, pk.kante FROM pk, n WHERE pk.pfad =n.v AND (n.n > 0 OR  n.v > 0 );
 INSERT INTO pk SELECT n.nummer, pk.kante FROM pk, n WHERE pk.pfad = n.n AND (n.n > 0 OR  n.v > 0 );
 INSERT INTO pk SELECT n.nummer, p.nummer FROM n, p  WHERE p.anfang=''ka'' AND p.ende=''ke'' AND (n.n > 0 OR n.v > 0 );

Löschen einer Kante

Habe die zu löschende Kante den Anfangsknoten ka und den Endknoten ke.

 CREATE TEMPORARY TABLE d (id int);
 INSERT INTO d SELECT pfad FROM pk,p WHERE kante=p.nummer AND p.anfang= ''ka'' AND ende=''ke'';
 DELETE FROM p  USING p,d  WHERE p.nummer = d.id;
 DELETE FROM pk USING pk,d WHERE pk.pfad  = d.id;

Initialisieren

• Die Zwischentabelle n erzeugen:

 CREATE TABLE n ( nummer int primary key auto_increment, v int, n int);

• Alle Kanten selbst als Pfade der Länge 1 eintragen:

INSERT INTO p SELECT id, child, parent,1 FROM Relation;
 INSERT INTO pk SELECT nummer, nummer FROM p;
 ALTER TABLE n AUTO_INCREMENT = 1000

• Nun die bekannten Pfade um eine Kante verlängern:

for( $laenge = 1 .. n ) {
  INSERT INTO n SELECT 0, p1.nummer, p2.nummer FROM p p1, p p2 WHERE p1.ende = p2.anfang AND p1.laenge = $laenge;
  wenn dieses kein Ergebnis liefert -> fertig 
  die Anzahl der Ergebnisse ist ab $laenge=2 streng monoton fallend
  INSERT INTO p SELECT n.nummer,p1.anfang, p2.ende, p1.laenge+p2.laenge FROM p p1, p p2,n  WHERE n.v = p1.nummer AND n.n = p2.nummer;
  INSERT INTO pk SELECT n.nummer, pk.kante  FROM pk, n WHERE pk.pfad = n.v; 
  INSERT INTO pk SELECT n.nummer, pk.kante  FROM pk, n WHERE pk.pfad = n.n;
  DELETE FROM n;
}

• Am Ende einmal den Zähler für die Zwischentabelle einstellen:

$anzahl_pfade = SELECT count(*)+1 FROM p;
ALTER TABLE n AUTO_INCREMENT = $anzahl_pfade