Datenmodell für "Ich kenne jemanden, der jemanden kennt, der ..."

Ciao

Wie sieht ein Datenbank Modell (resp. Abfragen) aus, mit welchem ich die
kürzeste Bekanntschafts-Kette zwischen Personen ermitteln kann.
(Beispielsweise eingesetzt bei OpenBC.)

Nick

Re: Datenmodell für"Ich kenne jemanden, derjemanden kennt, der ..."

Moin,

Nick Gerber schrieb:
> Wie sieht ein Datenbank Modell (resp. Abfragen) aus, mit welchem ich die
> kürzeste Bekanntschafts-Kette zwischen Personen ermitteln kann.
> (Beispielsweise eingesetzt bei OpenBC.)

Du suchst Pfadfindealgorithmen. Da gibt es mehrere, für den Zweck
braucht es allerdings dummerweise einen der langsamen, da keine
"Abschätzung" zwischendurch getroffen werden kann. Näheres dazu kannst
du bei Beschreibungen von Suchalgorithmen finden.

Aber ich glaube das ist ziemlich OT, da es meiner Meinung nach
blödsinnig wäre, einen Pfadfindealgorithmus in einem Datenbanksystem
laufen zu lassen. Dass heisst du schreibst ein Programm, dass den Pfad
sucht, und je nachdem, was du da für Eingaben brauchst, formulierst du
dann Datenstrukturen und Abfragen.

Ein Vorschlag wäre:

TABLE ( id1 INT, id2 INT)
(Also eine Kreuztabelle, mit der zwei Datenelemente (bei OpenBC eben
Personen) verbunden werden.)

In deinem Algorithmuss kannst du dann mit diesem Statement alle
"Nachbarn" einer ID wiederbekommen:

SELECT id2 FROM tabelle WHERE id1 = $id
UNION
SELECT id1 FROM tabelle WHERE id2 = $id;

Ich hoffe ich konnte dir helfen.

Grüße,
--
Philipp Tölke
PGP: 0x96A1FE7A

Re: Datenmodell für "Ich kenne jemanden, der jemanden kennt, der ..."

Merci für die Antwort.

Der Begriff 'Pfadfindealgoritmus' fehlte mir in meinem Recherche-Trip
durchs Web.

Und erste Suchhits deuten nun auch an, dass 'Pfadfinden' auch kein Task
für die Datenbank zu sein schein, sondern, wie du empfiehlst, in der
Applikation gelöst wird.

Philipp Tölke wrote:
> Moin,
>
> Nick Gerber schrieb:
>> Wie sieht ein Datenbank Modell (resp. Abfragen) aus, mit welchem ich die
>> kürzeste Bekanntschafts-Kette zwischen Personen ermitteln kann.
>> (Beispielsweise eingesetzt bei OpenBC.)
>
> Du suchst Pfadfindealgorithmen. Da gibt es mehrere, für den Zweck
> braucht es allerdings dummerweise einen der langsamen, da keine
> "Abschätzung" zwischendurch getroffen werden kann. Näheres dazu kannst
> du bei Beschreibungen von Suchalgorithmen finden.
>
> Aber ich glaube das ist ziemlich OT, da es meiner Meinung nach
> blödsinnig wäre, einen Pfadfindealgorithmus in einem Datenbanksystem
> laufen zu lassen. Dass heisst du schreibst ein Programm, dass den Pfad
> sucht, und je nachdem, was du da für Eingaben brauchst, formulierst du
> dann Datenstrukturen und Abfragen.
>
> Ein Vorschlag wäre:
>
> TABLE ( id1 INT, id2 INT)
> (Also eine Kreuztabelle, mit der zwei Datenelemente (bei OpenBC eben
> Personen) verbunden werden.)
>
> In deinem Algorithmuss kannst du dann mit diesem Statement alle
> "Nachbarn" einer ID wiederbekommen:
>
> SELECT id2 FROM tabelle WHERE id1 = $id
> UNION
> SELECT id1 FROM tabelle WHERE id2 = $id;
>
> Ich hoffe ich konnte dir helfen.
>
> Grüße,