Zirkuläre Referenz erkennen

[Mario]

Hallo,

viele kennen wahrscheinlich von Excel die schöne Fehlermeldung, wenn man bei Zellen im Kreis referenziert, was ja eine Endlosschleife ergibt. Genau so einen Fall könnte ich haben und möchte ich auch vorbeugen.

Situation:
Eine Datenbank enthält im wesentlichen zwei Spalten
Idx, IdxRef

Beispielinhalt:
1,0
2,1
3,1
4,2

Das bedeutet:
Die 1 enthält kein weiteres Element.
Die 2 enthält auch das Element 1.
Die 3 enthält auch das Element 1.
Die 4 enthält das Element 2 und somit auch die 1.

Füge ich zum Beispiel in der Datenbank noch den Satz:
1,4 hinzu, habe ich ein Problem. 1 enthält 4, 4 enthält 2, 2 enthält 1 und der Kreis schließt sich.

Wie kann ich diese Fehler schnell und effektiv finden? Meine einzige Idee ist momentan einfach jeden Artikel durchzutesten. Also einen Datensatz einlesen und in einer Liste mitschreiben, an welchen Zahlen ich schon vorbeigekommen bin. Bei Wiederholung Fehler. Das ist natürlich nicht sehr elegant

[Leuselator]

wenn es also um das Zusammenstellen von Produktpaketen geht, epfehle ich folgende
Tabellenstruktur & referenzielle Integritäten:

SQL-Code:

                          +-----------------------+
                          |Table Produkte_Pakete  |      +------------------+
+------------------+      +-------------------+---+      |Table Pakete      |
|Table Produkte    |      |idProdukte_Pakete  |i  |      +--------------+---+
+--------------+---+      |idPaket            |i  |----->|idPaket       |i  |
|idProdukt     |i  |<-----|idProdukt          |i  |      |...           |   |
|...           |   |      |Aktiv              |L  |      +--------------+---+
+--------------+---+      +-------------------+---+

aktuelle PaketInhalte erhältst Du mit:

SQL-Code:

    select PR.*
      from Pakete PA
inner join Produkte_Pakete PP
        on PP.idPaket = PA.idPaket
       and PP.Aktiv = TRUE -- oder wie auch immer der Wert für 
                           -- Logisch wahr in Paradox ist
inner join Produkte PR
        on PR.idProdukt = PP.idProdukt
     where PA.idPaket = :IdPaket -- Id des gewünschten Paketes

nicht im Paket enthaltene Produkte (um sie z.B. dem Paket hinzuzufügen)
bekommst Du mit:

SQL-Code:

select * 
  from Produkte 
 where idProdukt not in (select distinct PP.idProdukt 
                           from Pakete PA 
                     inner join Produkte_Pakete PP 
                             on PP.idPaket = PA.idPaket 
                            and PP.Aktiv = 1
                          where PA.idPaket = :IdPaket) -- Id des gewünschten Paketes

gruß Tim
Edit1: Tabellendarstellung war mist
Edit2: 2.SQL-Statement war noch größerer Mist
Edit3: macht Paradox unterabfragen (wie im 2. SQL-Statement) mit?

[Mario]

Besten Dank erst mal, dass Du Dir offensichtlich sehr viel Mühe damit gegeben hast.

Zu Punkt 3: Unterabfragen unterstützt Paradox nicht, wenn ich mich an meinen letzten Versuch noch richtig entsinne, dass wäre aber nicht so kritisch. Da könnte ich mit einer Zwischentabelle arbeiten, da diese ja nur bei der Dateneingabe notwendig ist und nicht nach der Auslieferung der Tabellen (der Anwender kann die Pakete nicht beeinflussen).

Prinzipiell ist Dein Gedankengang klar. Du schaffst die Probleme beiseite, indem Du festlegst, dass jedes Paket seine Artikel enthält. Es ist jetzt aber damit leider nicht mehr möglich, bereits angelegt Pakete einem weiteren Paket zuzufügen, oder?

Lasse mich mal kurz ein kleines Beispiel machen:
vorhandene Artikel:

Code:

Schraube M8
Schraube M10
Schraube M12
Mutter für M8
Mutter für M10
Mutter für M12
Unterlegscheibe für M8
Unterlegscheibe für M10
Unterlegscheibe für M12

Ein Paket "Mutter mit Scheibe M8" könnte dann so aussehen:

Code:

Mutter für M8
Unterlegscheibe für M8

Ein Paket "Schraube mit Mutter M8" müsste dann so aussehen:

Code:

Mutter mit Scheibe M8
Schraube M8

Auf den ersten Blick sieht das natürlich wie Haarspalterei aus, weil ich das Paket natürlich auch so bilden könnte:

Code:

Mutter für M8
Unterlegscheibe für M8
Schraube M8

Das ist richtig, aber die größten Pakete enthalten locker mal 100 Einzelteil, weßhalb die struckturierte Zusammenfassung zwingend notwendig ist. Ich vermute mal, dass ich da mit der von Dir dargestellten Logik nicht weiter komme oder ich habe Deine Logik nicht vollständig verstanden.

[Leuselator]

Doch kommst Du
Wenn Du auf der Oberfläche die Pakete anbietest, wie Du sie mit der ersten Query erhältst, kannst Du auch anbieten, ein existentes Paket einem anderen existenten oder einem neuen Paket hinzuzufügen (Drag/Drop?).
Du solltest dann beim Einfügen des ausgewählten Paketes nur fragen, ob Bestandteile des hinzuzufügenden Paketes, die schon im Zielpaket enthalten sind nochmals hinzugefügt, oder weggelassen werden sollen. Dann fügst Du alle (oder nur die noch nicht vorhandenen) Produkte des QuellPaketes dem Zielpaket hinzu.
Diese Variante hat den Nachteil, dass Du anschließende Änderungen im Quellpaket nicht in das Zielpaket übertragen bekommst, da ja immer die im QuellPaket enthaltenen Produkte in das ZielPaket eingefügt werden.

Wenn Du die Datenbank um 2 Tabellen erweiterst (siehe Bild im Anhang), dann kannst Du Bundles erzeugen. Im einfachsten Fall ist 1 Bundle = 1 Paket. Du kannst aber beliebig viele Pakete zu einem Bundle schnüren und für jedes Paket festlegen, ob es vollständig oder nur mit den noch nicht im Bundle enthaltenen Bestandteilen in das Bundle einfließt.

An der Stelle will ich's gut sein lassen mit dem Zerbrechen fremder Köpfe
Gruß

[Robert Marquardt]

Das ist ein echtes Uni-Thema.
Der Algorithmus fuer den allgemeinen Fall der zirkulaeren Bezuege ist nicht einfach und wenn ich mich recht erinnere ist die Entscheidung nicht immer moeglich.
Du hast einen Graphen von Bezuegen (Excel ist ein typischer Fall). Jedes Element kann auf mehrere beliebige andere Elemente zeigen. Jeder Bezug ist gerichtet (von einem zum anderen, aber nicht zurueck).

Genaugenommen muss man von jedem Element aus rekursiv mit Backtracking alle Wege abklappern.

[Mario]

Hallo noch mal,

also ich denke, daß ich die DB jetzt im Griff habe, das funktioniert prächtig. Die Prüfung der Integrität lief auch überraschend gut, jedenfalls werden Kreisverweise problemlos gefunden. Ich baue mir einfach anhand eines beliebigen Startartikels einen Baum auf und protokolliere bei jedem Ast die dafür verwandten Artikel. Logischerweise darf nie ein Artikel doppelt vorkommen, sonst gehts in eine Endlosschleife. In diesem Fall breche ich ab und zeige den fehlerhaften Ast.

[Robert Marquardt]

Die Gemeinheit ist das du dabei nicht garantiert alle Knoten erreichst.
Drei Knoten. Zwei weisen auf einen in der Mitte.
Vom linken und rechten erreichst du nur den in der Mitte.
Vom mittleren aus gar keinen.

[Mario]

Hmm, verstehe ich jetzt nicht so ganz, wie Du es meinst.

Wenn ich an einem Knoten drei weitere Wege habe, so laufe ich alle drei Wege lang, um zu prüfen, was passiert. Mir ist dabei nicht ganz klar, wo die Lücke entstehen könnte?

[Robert Marquardt]

Bei deinem Beispiel handelt es sich um einen Baum und nicht um einen Graphen.

Das hier ist ein Graph, aber kein Baum:
1 -> 2 <- 3
Gemeinerweise kann man weder von 1 nach 3 noch von 3 nach 1 kommen
(nicht vergessen die Kanten sind gerichtet).
Es ist also moeglich unverbundene Teilgraphen zu haben.
Deshalb kann man nicht einen beliebigen Knoten nehmen und erwarten alle anderen
Knoten erreichen zu koennen.

[Mario]

Ok, ich denke, ich weiß jetzt, was Du meinst. Einzelne Paket, die durch keinen anderen erreicht werden, stellen kein Problem dar, sind sogar bewußt zugelassen. Ergänzend muss ich noch sagen, alle von mir in den Baum gezeichneten Striche sind eigentlich Pfeile (von links nach rechts). Der umgekehrte Weg ist also sowieso nicht möglich. Vermutlich vereinfacht das die Problematik sowieso.

Uns ist es nur wichtig, nicht in irgendeine Endlosschleife mit den angelegten Daten zu rennen und dazu bietet sich die Überprüfung des Baumes an.

Danke für Deine Gedankenanstöße.