GOV Entwicklung Relationen-Index - Versionsgeschichte

Jzedlitz am 27. März 2009 um 09:47 Uhr

2009-03-27T09:47:29Z

PLingnau: /* Kategorie:GOV-Intern */

2007-12-15T17:07:43Z

Kategorie:GOV-Intern

← Nächstältere Version		Version vom 15. Dezember 2007, 19:07 Uhr
Zeile 83:		Zeile 83:
	$anzahl_pfade = SELECT count(*)+1 FROM p;		$anzahl_pfade = SELECT count(*)+1 FROM p;
	ALTER TABLE n AUTO_INCREMENT = $anzahl_pfade		ALTER TABLE n AUTO_INCREMENT = $anzahl_pfade

			[[Kategorie:GOV-Intern]]

Jzedlitz: /* Initialisieren */

2006-11-19T22:33:32Z

Initialisieren

← Nächstältere Version		Version vom 20. November 2006, 00:33 Uhr
Zeile 65:		Zeile 65:

	* Alle Kanten selbst als Pfade der Länge 1 eintragen:		* Alle Kanten selbst als Pfade der Länge 1 eintragen:
	INSERT INTO p SELECT ~~nummer~~,~~anfang~~,~~ende~~,1 FROM k;		INSERT INTO p SELECT id, child, parent,1 FROM Relation;
	INSERT INTO pk SELECT nummer, nummer FROM p;		INSERT INTO pk SELECT nummer, nummer FROM p;
	ALTER TABLE n AUTO_INCREMENT = 1000		ALTER TABLE n AUTO_INCREMENT = 1000

Jzedlitz: /* Initialisieren */

2004-08-23T09:09:53Z

Initialisieren

← Nächstältere Version		Version vom 23. August 2004, 11:09 Uhr
Zeile 73:		Zeile 73:
	INSERT INTO n SELECT 0, p1.nummer, p2.nummer FROM p p1, p p2 WHERE p1.ende = p2.anfang AND p1.laenge = $laenge;		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		wenn dieses kein Ergebnis liefert -> fertig
	'''die Anzahl der Ergebnisse ist streng monoton fallend'''		'''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 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.v;

Jzedlitz: /* Einfügen einer neuen Kante */

2004-08-17T14:50:49Z

Einfügen einer neuen Kante

← Nächstältere Version		Version vom 17. August 2004, 16:50 Uhr
Zeile 49:		Zeile 49:
	den Rest (die letzte Bedingung schließen den Pfad, der nur aus der neuen Kante besteht, aus)		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.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, pk.kante FROM pk, n WHERE pk.pfad = n.n AND (n.n > 0 OR n.v > 0 );
	INSERT INTO pk SELECT n.nummer, pk.~~kante~~ FROM pk, n WHERE pk.~~kante~~=pk.~~nummer~~ 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 ==		== Löschen einer Kante ==

Jzedlitz: /* Einfügen einer neuen Kante */

2004-08-17T14:06:38Z

Einfügen einer neuen Kante

← Nächstältere Version		Version vom 17. August 2004, 16:06 Uhr
Zeile 14:		Zeile 14:

	== Einfügen einer neuen Kante ==		== Einfügen einer neuen Kante ==
	~~Sei ''kn''~~ neue Kante ~~mit~~ Anfangsknoten ''ka'' und Endknoten ''ke'' (genauer ~~ist ''kn'' die Nummer der Kante,~~ ''ka'' und ''ke'' die Nummern der Knoten).		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:		Die neue Kante in die Tabelle der neuen Pfade eintragen:
Zeile 45:		Zeile 45:

	die eine neue Kante:		die eine neue Kante:
	INSERT INTO pk SELECT n.nummer,~~''kn''~~ FROM n WHERE n.v=0 AND n.n=0;		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)		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.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, pk.kante FROM pk, n WHERE pk.pfad = n.n AND (n.n > 0 OR n.v > 0 );
	INSERT INTO pk SELECT n.nummer, pk.kante FROM pk, n WHERE pk.kante=~~''kn''~~ AND (n.n > 0 OR n.v > 0 );		INSERT INTO pk SELECT n.nummer, pk.kante FROM pk, n WHERE pk.kante=pk.nummer AND (n.n > 0 OR n.v > 0 );

	== Löschen einer Kante ==		== Löschen einer Kante ==

Jzedlitz: /* Löschen einer Kante */

2004-08-17T14:06:33Z

Löschen einer Kante

← Nächstältere Version		Version vom 17. August 2004, 16:06 Uhr
Zeile 53:		Zeile 53:

	== Löschen einer Kante ==		== Löschen einer Kante ==
	Habe die zu löschende Kante den Anfangsknoten ''ka' und den Endknoten ''ke''.		Habe die zu löschende Kante den Anfangsknoten ''ka'' und den Endknoten ''ke''.

	CREATE TEMPORARY TABLE d (id int);		CREATE TEMPORARY TABLE d (id int);

Jzedlitz: /* Löschen einer Kante */

2004-08-17T14:06:11Z

Löschen einer Kante

← Nächstältere Version		Version vom 17. August 2004, 16:06 Uhr
Zeile 53:		Zeile 53:

	== Löschen einer Kante ==		== Löschen einer Kante ==
			Habe die zu löschende Kante den Anfangsknoten ''ka' und den Endknoten ''ke''.

	CREATE TEMPORARY TABLE d (id int);		CREATE TEMPORARY TABLE d (id int);
	INSERT INTO d SELECT pfad FROM pk WHERE kante = ''kn'';		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 p USING p,d WHERE p.nummer = d.id;
	DELETE FROM pk USING pk,d WHERE pk.pfad = d.id;		DELETE FROM pk USING pk,d WHERE pk.pfad = d.id;

Jzedlitz: /* Löschen einer Kante */

2004-08-16T22:14:58Z

Löschen einer Kante

← Nächstältere Version		Version vom 17. August 2004, 00:14 Uhr
Zeile 53:		Zeile 53:

	== Löschen einer Kante ==		== Löschen einer Kante ==
			CREATE TEMPORARY TABLE d (id int);
	INSERT INTO d SELECT pfad FROM pk WHERE kante = ''kn'';		INSERT INTO d SELECT pfad FROM pk WHERE kante = ''kn'';
	DELETE FROM p WHERE p.nummer ~~IN ( SELECT * FROM~~ d );		DELETE FROM p USING p,d WHERE p.nummer = d.id;
	DELETE FROM pk WHERE pfad ~~IN ( SELECT * FROM~~ d );		DELETE FROM pk USING pk,d WHERE pk.pfad = d.id;

	== Initialisieren ==		== Initialisieren ==

Jzedlitz: /* Einfügen einer neuen Kante */

2004-08-16T22:07:57Z

Einfügen einer neuen Kante

← Nächstältere Version		Version vom 17. August 2004, 00:07 Uhr
Zeile 48:		Zeile 48:

	den Rest (die letzte Bedingung schließen den Pfad, der nur aus der neuen Kante besteht, aus)		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 OR pk.pfad = n.n OR pk.kante=8 AND (n.n > 0 OR n.v > 0 );		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, pk.kante FROM pk, n WHERE pk.kante=''kn'' AND (n.n > 0 OR n.v > 0 );

	== Löschen einer Kante ==		== Löschen einer Kante ==

← Nächstältere Version		Version vom 27. März 2009, 11:47 Uhr
Zeile 17:		Zeile 17:

	Die neue Kante in die Tabelle der neuen Pfade eintragen:		Die neue Kante in die Tabelle der neuen Pfade eintragen:
	INSERT INTO n (v,n) VALUES (0,0);		<source lang="sql">INSERT INTO n (v,n) VALUES (0,0);</source>

	alle Vorgänger-Pfade in die Tabelle der neuen Pfade eintragen:		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'';		<source lang="sql">INSERT INTO n (v,n) SELECT nummer,0 FROM p WHERE p.ende = ''ka'';</source>

	alle Nachfolger-Pfade in die Tabelle der neuen Pfade eintragen:		alle Nachfolger-Pfade in die Tabelle der neuen Pfade eintragen:
	INSERT INTO n (v,n) SELECT 0,nummer FROM p WHERE p.anfang = ''ke'';		<source lang="sql">INSERT INTO n (v,n) SELECT 0,nummer FROM p WHERE p.anfang = ''ke'';</source>

	alle Pfade, die über die neue Kante laufen:		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'';		<source lang="sql">INSERT INTO n (v,n) SELECT p1.nummer, p2.nummer FROM p p1, p p2 WHERE p1.ende=''ka'' AND p2.anfang=''ke'';</source>

	aus N neue Einträge in P erstellen:		aus N neue Einträge in P erstellen:

	die eine neue Kante:		die eine neue Kante:
	INSERT INTO p SELECT n.nummer,''ka'',''ke'',1 FROM n WHERE n.v=0 AND n.n=0;		<source lang="sql">INSERT INTO p SELECT n.nummer,''ka'',''ke'',1 FROM n WHERE n.v=0 AND n.n=0;</source>

	alle Pfade, die die neue Kante als letzte Kante haben:		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;		<source lang="sql">INSERT INTO p SELECT n.nummer,p.anfang, ''ke'', p.laenge+1 FROM n,p WHERE n.v = p.nummer AND n.n=0;</source>

	alle Pfade, die die neue Kante als erste Kante haben:		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;		<source lang="sql">INSERT INTO p SELECT n.nummer, ''ka'' ,p.ende,p.laenge+1 FROM n,p WHERE n.n = p.nummer AND n.v=0;</source>

	alle Pfade, die die neue Kante in der Mitte enthalten:		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;		<source lang="sql">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;</source>

	in PK eintragen:		in PK eintragen:

	die eine neue Kante:		die eine neue Kante:
	INSERT INTO pk SELECT n.nummer,n.nummer FROM n WHERE n.v=0 AND n.n=0;		<source lang="sql">INSERT INTO pk SELECT n.nummer,n.nummer FROM n WHERE n.v=0 AND n.n=0;</source>

	den Rest (die letzte Bedingung schließen den Pfad, der nur aus der neuen Kante besteht, aus)		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 );		<source lang="sql">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, 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 );		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 );</source>

	== Löschen einer Kante ==		== Löschen einer Kante ==
	Habe die zu löschende Kante den Anfangsknoten ''ka'' und den Endknoten ''ke''.		Habe die zu löschende Kante den Anfangsknoten ''ka'' und den Endknoten ''ke''.

	CREATE TEMPORARY TABLE d (id int);		<source lang="sql"> 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'';		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 p USING p,d WHERE p.nummer = d.id;
	DELETE FROM pk USING pk,d WHERE pk.pfad = d.id;		DELETE FROM pk USING pk,d WHERE pk.pfad = d.id;</source>

	== Initialisieren ==		== Initialisieren ==
	* Die Zwischentabelle n erzeugen:		* Die Zwischentabelle n erzeugen:
	CREATE TABLE n ( nummer int primary key auto_increment, v int, n int);		<source lang="sql"> CREATE TABLE n ( nummer int primary key auto_increment, v int, n int);</source>

	* Alle Kanten selbst als Pfade der Länge 1 eintragen:		* Alle Kanten selbst als Pfade der Länge 1 eintragen:
	INSERT INTO p SELECT id, child, parent,1 FROM Relation;		<source lang="sql">INSERT INTO p SELECT id, child, parent,1 FROM Relation;
	INSERT INTO pk SELECT nummer, nummer FROM p;		INSERT INTO pk SELECT nummer, nummer FROM p;
	ALTER TABLE n AUTO_INCREMENT = 1000		ALTER TABLE n AUTO_INCREMENT = 1000</source>

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