DB Baumstruktur nächste Fundstelle

[ibp]

Hi,

ich habe einen klassischen Parent-Child Baum und suche nach einem Algorithmus der mir den nächsten Eintrag mit einer bestimmten Eigenschaft zurück gibt.

Einstieg ist an einem beliebigen Knoten des Baumes. Alle Kinder zu durchsuchen ist kein Problem. Das Problem ist wenn der "nächste Zielknoten" nicht innerhalb des Startastes liegt.

Im Prinzip möchte ich einen Algorithmus, möglichst per StroredProcedure (InterBase), der mir ähnlich TreeNode.GetNext den nächsten "globalen" Knoten liefert.

Irgendwie hänge ich da gerade... :cry:

Danke schon mal....

[marabu]

Wenn Du von "klassischem Parent-Child Baum" schreibst, dann meinst Du eine Struktur der Form K (id, parent_id, index, ...)? Die auf diesen Strukturen operierenden Funktionen sind sehr aufwändig. Vielleicht möchtest Du für deine Tabelle das Konzept "Nested Sets" ins Auge fassen. Die Struktur ist dann N (id, left_, right_, ...) und die von Dir gesuchte Funktion, wie auch viele andere Funktionen auf dieser Struktur, ist dann sehr einfach:

Code:

CREATE PROCEDURE successor (
    id Bigint )
RETURNS (
    nextid BIGINT )
AS
BEGIN
  SELECT FIRST 1 id 
  FROM n 
  WHERE left_ > (SELECT left_ FROM n WHERE id = :id)
  ORDER BY left_
  INTO :nextid;
END

Grüße vom marabu

[ibp]

Zitat:

Zitat von marabu (Beitrag 1074117)

Wenn Du von "klassischem Parent-Child Baum" schreibst, dann meinst Du eine Struktur der Form K (id, parent_id, index, ...)?

Ja meinte ich..

Zitat:

Zitat von marabu (Beitrag 1074117)

...Die auf diesen Strukturen operierenden Funktionen sind sehr aufwändig.

manchmal

Zitat:

Zitat von marabu (Beitrag 1074117)

...Vielleicht möchtest Du für deine Tabelle das Konzept "Nested Sets" ins Auge fassen.

Mir sind die Vorzüge dieser Verknüpfungen bekannt aber es kommt für diese Projekt nicht in Frage. Das Projekt existiert seit über 12 Jahren und die dazu entsprechenden Datenbanken bei XXX-Kunden. Dieser Anpassungsaufwand wäre zu hoch, auch im Programm selber.

[mkinzler]

Man könnte sich aber den Einsatz einer CTE überlegen

[marabu]

Bei klassischen BOM-Strukturen brauche ich eine strenge Ordnung der siblings. Ich lege eine Tabelle bom (id bigint, name varchar(32), parentid bigint) zu Grunde, wobei das Feld name die geforderte Ordnung herstellt, d.h. name ist (lokal) eindeutig.

Anders als bei nested sets muss ich mich mit dem rekursiven Charakter der Struktur auseinandersetzen - das ist der hier sichtbare Aufwand, den ich in meinem vorigen Beitrag ansprach.

Code:

SET TERM ^ ;
CREATE PROCEDURE successor ( id Bigint ) RETURNS ( nextid Bigint ) AS
DECLARE VARIABLE parentid bigint; 
DECLARE VARIABLE place varchar(32); 
BEGIN
  SELECT parentid, name FROM bom WHERE id = :id INTO :parentid, :place;
  /* try first child */
  SELECT FIRST 1 id FROM bom WHERE parentid = :id ORDER BY name INTO :nextid;
  WHILE ( :nextid IS NULL AND :parentid IS NOT NULL ) DO
  BEGIN
    /* try next sibling */
    SELECT FIRST 1 id FROM bom WHERE parentid = :parentid AND name > :place ORDER BY name INTO :nextid;
    /* prepare backtracking */
    IF ( :nextid IS NULL ) THEN
      SELECT parentid, name FROM bom WHERE id = :parentid INTO :parentid, :place;
  END
END^
SET TERM ; ^

Das solltest Du an deine eigenen Anforderungen anpassen können.

Freundliche Grüße

[ibp]

Zitat:

Zitat von marabu (Beitrag 1074629)

Bei klassischen BOM-Strukturen brauche ich eine strenge Ordnung der siblings. Ich lege eine Tabelle bom (id bigint, name varchar(32), parentid bigint) zu Grunde, wobei das Feld name die geforderte Ordnung herstellt, d.h. name ist (lokal) eindeutig.

Dein Hinweis auf die "strenge Ordnung" hat den Durchbruch gebracht :-D . An diesem fehlenden Punkt "name > :place" ist meine Lösung gescheitert.

1K-Dank :thumb:

Zitat:

Zitat von marabu (Beitrag 1074629)

Anders als bei nested sets muss ich mich mit dem rekursiven Charakter der Struktur auseinandersetzen - das ist der hier sichtbare Aufwand, den ich in meinem vorigen Beitrag ansprach.

Das stimmt, wobei sich der Aufwand bisher in Grenzen hielt. Mir ist der Vorteil von Nested Sets schon klar, jedoch werden in der Anwendung sehr viele Daten innerhalb des Baumes gespeichert, gelöscht und verschoben. Da kommen bei einer mittleren Projekt-DB schon mal and die 500.000-1 Mio Baumknoten zusammen. Bei Nested Sets würden ständig sehr viele Daten aktualisiert werden müssen.