Pfad suchen - kürzeste Verknüpfung

Computer: Software & Programmierung Microsoft Access
#1

Hallo,

ich suche eine Möglichkeit um eine Analyse-Abfrage mit Access einzurichten. In anderen Programmen kenne ich die Funktion „Pfad suchen“, die mir den kürzesten Weg zwischen zwei Datensätzen anzeigt.

Gibt es irgendetwas ähnliches auch in Access?

Bsp:

Tabelle 1: Datensätze (A, B, C, D, E)
Tabelle 2: Verknüpfungen (A-B, D-E, E-A, C-D)

Gesucht wird z.B. der schnellste Weg von A nach C. Im Beispielfall wäre es A-E-D-C, also 4 Schritte. Es kann natürlich auch sein, dass es einmal verschiedene „Pfade“ gibt. Gesucht wird immer der kürzeste.

Weiterhin wäre es gut eine Art „Radar“ mit einer Funktion einrichten zu können, um die nächsten Datensätze eines bestimmten Typs anzuzeigen.

Bsp:
Tabelle 1: Datensätze (A1, B2, C3, D3, E2)
Tabelle 2: Verknüpfungen (A-B, D-E, E-A, C-D)

Ausgewählt ist Datensatz A. Gesucht wird der nächste Datensatz mit einer 3. Angezeigt werden müßte D. Ist der Datensatz E ausgewählt, so wäre es auch D, bei D selbst dann C etc.

Vielleicht gibt es ja sogar eine leichte Möglichkeit, um das zu bewerkstelligen?

Grüße

Stefan

#2

Hallo Stefan,

ich suche eine Möglichkeit um eine Analyse-Abfrage mit Access
einzurichten.

Analysieren kannst du immer mit den Abfragen.

In anderen Programmen kenne ich die Funktion „Pfad suchen“,

welche Programme meinst du?

die mir den kürzesten Weg zwischen zwei Datensätzen anzeigt.

die Datensätze sind nur Millimeter voneinander entfernt :smile:
Welchen Sinn sollte sowas in einer relationalen DB machen?
Du meinst keinen Index o.ä.?

Gibt es irgendetwas ähnliches auch in Access?

ist mir in den letzten 25 Jahren noch nicht unter gekommen, zumindest habe ich es bisher nicht benötigt!

Bsp:

Tabelle 1: Datensätze (A, B, C, D, E)
Tabelle 2: Verknüpfungen (A-B, D-E, E-A, C-D)

Gesucht wird z.B. der schnellste Weg von A nach C.

also geht es um den Inhalt und nicht um die Datensätze?

Im Beispielfall wäre es A-E-D-C, also 4 Schritte.

ähm, wenn ich das richtig verstanden habe sind es drei Schritte:
A->B->C

Weiterhin wäre es gut eine Art „Radar“ mit einer Funktion
einrichten zu können, um die nächsten Datensätze eines
bestimmten Typs anzuzeigen.

also eine Abfrage, wo immer du die Daten anzeigen möchtest …

Bsp:
Tabelle 1: Datensätze (A1, B2, C3, D3, E2)
Tabelle 2: Verknüpfungen (A-B, D-E, E-A, C-D)

Ausgewählt ist Datensatz A. Gesucht wird der nächste Datensatz
mit einer 3. Angezeigt werden müßte D.

ähm und was ist mit C3?

Ist der Datensatz E ausgewählt, so wäre es auch D, bei D selbst dann C etc.

na dann mal viel Spaß beim programmieren der Abfrage und beim definieren der Beziehungen.

Vielleicht gibt es ja sogar eine leichte Möglichkeit, um das
zu bewerkstelligen?

definiere: leicht
natürlich kannst du das ganze auch per VBA (irgendwie) lösen :smile:
Auf jeden Fall benötigst du ein Haupt- und ein Unterformular bzw. Bericht.

könnte es sein, dass du eine Routenplanung/optimierung programmieren willst?

Grüße aus Schönberg (Lübeck)
Wolfgang
(Netwolf)

#3

Hallo, Stefan!

ich suche eine Möglichkeit um eine Analyse-Abfrage mit Access
einzurichten. In anderen Programmen kenne ich die Funktion
„Pfad suchen“, die mir den kürzesten Weg zwischen zwei
Datensätzen anzeigt.
Gibt es irgendetwas ähnliches auch in Access?

Nein.

Access ist eine relationale Datenbank, kann also mit Relationen umgehen, nicht aber mit Datenbankinhalten. Von Knoten und Kanten, wie Du sie abbildest, weiß Access nichts.

Du müsstest also zunächst Deine Daten in eine eigene Graphenstruktur (schon die nächste Frage: gerichtet oder ungerichtet?) überführen und könntest dann mit mehr oder weniger bekannten Verfahren eine Graphenanalyse durchführen. Das alles ist aber nichts, was Access-Bordmittel zur Verfügung stellen.

Gruß, Manfred

#4

Access ist eine relationale Datenbank, kann also mit
Relationen umgehen, nicht aber mit Datenbankinhalten. Von
Knoten und Kanten, wie Du sie abbildest, weiß Access nichts.

BTW: Ob es AddIns gibt, die sowas können, vermag ich nicht zu beurteilen.

Gruß, Manfred

#5

Moin, Stefan,

mich beschleicht das Gefühl, Du bist hier im falschen Brett. Die Problemstellung scheint doch zu sein, den kürzesten Weg zwischen zwei Knoten zu finden, das hat mit Access absolut nichts zu tun.

Verknüpfungen im Access sind zwar Kanten in einem Graphen, allerdings in dem, der die Datenbank struktur abbildet. Was Du suchst, sind wohl Beziehungen zwischen Individuen.

Graphentheorie fällt ins Brett Mathematik.

Gruß Ralf

#6

Hallo Wolfgang,

vielleicht habe ich die Anfrage auch etwas schwierig formuliert, aber ich glaube du hast den Hintergrund noch nicht richtig verstanden

Analysieren kannst du immer mit den Abfragen.

Klar - aber ich brauche natürlich die spezielle Analyse, die ich im nachfolgenden erkläre…

die Datensätze sind nur Millimeter voneinander entfernt :smile:
Welchen Sinn sollte sowas in einer relationalen DB machen?
Du meinst keinen Index o.ä.?

Nö, keinen Index… - der Sinn ist, dass ich herausfinde, ob es irgendeine Verknüpfung bzw. einen Zusammenhang zwischen zwei Datensätzen gibt.

ähm, wenn ich das richtig verstanden habe sind es drei
Schritte:
A->B->C

Nein, da zwischen B und C keine Verknüpfung besteht.

ähm und was ist mit C3?

Dito - zwischen B und C besteht keine Verknüpfung. Der nächste Datensatz kann daher nicht das C sein.

na dann mal viel Spaß beim programmieren der Abfrage und beim
definieren der Beziehungen.

Drum frage ich hier, ob es nicht eine einfachere Möglichkeit gibt.

definiere: leicht
natürlich kannst du das ganze auch per VBA (irgendwie) lösen

-)

Auf jeden Fall benötigst du ein Haupt- und ein Unterformular
bzw. Bericht.

Leicht heißt, dass ich nicht alle Befehle und Funktionen von Access kenne bzw. kennen kann. Vielleicht gibt es ähnliches schon anderweitig. Ich hab mir auch Gedanken gemacht, wie ich es selbst mit VBA programmieren würde. Ist aber relativ umständlich…

könnte es sein, dass du eine Routenplanung/optimierung
programmieren willst?

Nein - ist aber auch schwierig die endgültige Anwendung zu erklären. Aber die Funktion könnte man dann in der Tat auch für so etwas hernehmen… (Suche den kürzesten Weg zwischen Hamburg und München).

Grüße

Stefan

#7

Hallo Ralf,

es hat nichts mit tatsächlichen Entfernungen oder Graphen zu tun. Ich nehme einfach einmal ein einfaches Beispiel her, damit man die gesuchte Funktion besser versteht… vielleicht kennt ihr ja die Aussage, dass jeder Mensch jeden anderen Menschen der Erde über 7 weitere Personen „kennt“.

Nehmen mit einmal an

Franz kennt Heinz
Franz kennt Axel
Heinz kennt Kurt
Kurt kennt Claudia

Wenn Franz Kontakt zu Claudia aufnehmen will, dann muss er einfach nur über Heinz und Kurt gehen. Zwischen allen Personen gibt es keine räumliche (Graph) Beziehung. Es sind immer nur 1 oder 0 Beziehungen (kennt oder kennt nicht). Franz kennt Kurt nicht. Aber eben Heinz und der kennt Kurt etc.

Ich kann natürlich mit VBA anfangen zu suchen. Ist aber relativ umständlich…

Denn anstatt einen schnellen Weg zu gehen muss ich anfangen alle Freunde der Freunde durchzuzählen…

VBA:

  • Ausgangspunkt: Franz
  • Gesuch wird: Claudia
  • Nimm die Bekannten von Franz (Heinz und Axel)
  • Ist einer der Bekannten Claudia (nein!)
  • Nimm die Bekannten der Bekannten von Franz (Kurt über Heinz)
  • Ist einer der Bekannten Claudia (nein!)
  • Nimm die Bekannten der Bekannten der Bekannten von Franz (Claudia)
  • Ist einer der Bekannten Claudia (ja!)

Im Beispiel geht es noch recht einfach. Aber es sind auch nur wenige Datensätze. Spätestens nach ein paar Dimensionen ufert das ganze recht aus. Zudem muss man sich noch immer den Pfad irgendwie merken, da es mir ja nichts hilft, wenn ich irgendwann beim Richtigen rauskomme, sondern ich will ja auch noch wissen wie.

Das mit dem „Radar“ wird dann noch komplizierter. Die Fragestellung wäre dann z.B. „Kennt Franz eine Frau?“ oder „Wer ist die nächste Frau, die Franz über seine Bekannten kennt?“

Eine Lösung, die ich mir gedacht habe ist, dass man eine Art Bewertungsattribut zum Datensatz schreibt („Kennt eine Frau?“). Zudem könnte man auch ein Tiefenattribut einfügen („Kennt eine Frau um X-Ecken“) und den nächsten Pfad anzeigen („Kennt die nächste Frau über XXX“).

Das Problem an der Sache ist, dass diese Attribute ja fest beim Datensatz verankert sind. Daher müßte bei jeder Änderung ein Schwung Datensätze umgeschrieben werden. Denn was passiert, wenn Heinz Claudia kennenlernt? Der Umweg über Kurt wäre für Franz nicht mehr nötig und die Entfernung zur nächsten Frau würde sich um eines reduzieren. Gleichzeitig dürfte sich für Kurt nichts ändern, da er ja immer noch näher (nämlich direkt) an der Frau dran ist, als wenn er über Heinz geht.

Alles ist irgendwie umständlich und da ist für mich schon die Frage, ob es nicht was schnelleres gibt. Das Beispiel mit den Menschen vereinfacht vielleicht ein bißchen die Fragestellung zu verstehen.

MfG

Stefan

#8

Hi Stefan,

datentechnisch wird so etwas durch eine m:n-Beziehung dargestellt, die jeweils zwei Personen zusammenfasst, die sich kennen (oder was immer ihre Beziehung sein möge):

Person \> Bekanntschaft
 \>

oder als Tabellen:

Person ( **Pers\_ID** , Name)

Bekanntschaft ( **Bek\_ID** , Pers\_ID1, Pers\_ID2), wahlweise ( **Pers\_ID1** , **Pers\_ID2** )

So ist sichergestellt, dass sich das Beziehungsnetz ohne Probleme ändern lässt. Der Rest der Chose wird von SQL leider nicht unterstützt, da heißt es wohl oder übel, die Aufgabenstellung zu programmieren: Suche den kürzesten Weg von Franz zu Susi.

Gruß Ralf

#9

Hallo, Stefan!

es hat nichts mit tatsächlichen Entfernungen oder Graphen zu
tun. Ich nehme einfach einmal ein einfaches Beispiel her,

Tja, da kann man jetzt diskutieren… Die Lösung lässt sich durchaus abbilden, in dem die Daten in einen Graphen überführt werden.

Nehmen mit einmal an

Franz kennt Heinz
Franz kennt Axel
Heinz kennt Kurt
Kurt kennt Claudia

Wenn Franz Kontakt zu Claudia aufnehmen will, dann muss er
einfach nur über Heinz und Kurt gehen. Zwischen allen Personen
gibt es keine räumliche (Graph) Beziehung. Es sind immer nur 1
oder 0 Beziehungen (kennt oder kennt nicht). Franz kennt Kurt
nicht. Aber eben Heinz und der kennt Kurt etc.

Übersetzt: Ich kann einen Graphen definieren, dessen Knoten die Personen sind und dessen Kanten die „kennt“-Beziehung darstellen. Das könnte man jetzt noch mit gerichteten Kanten machen wie bei XING: Kante von A nach B heißt: A kennt B, nicht aber zwangsnotwendig umgekehrt…

Wie auch immer:

Das Thema muss man schon selbst programmieren. Grob skiziiert läuft das wie folgt ab:

  1. Kennt Startperson die Zielperson?
    ja: bingo, fertig, liefere die übergebene Startperson am Ende des Ergebnisses
    nein:
  2. Suche alle Bekannten von Startperson
  3. Nimm jeden Bekannten, füge den in eine „Bekanntenkette“ hinzu (um sich den Pfad zu merken)
  4. Gehe zu 1.: Prüfe, ob Bekannter die Zielperson kennt.

Ich kann natürlich mit VBA anfangen zu suchen. Ist aber
relativ umständlich…

Geht. Per Rechenzeit kann das in der Tat mal lustig werden. Optimierbar wird das ganze, wenn Du auch noch Zyklen vermeidest…

Denn anstatt einen schnellen Weg zu gehen muss ich anfangen
alle Freunde der Freunde durchzuzählen…

Da wirst Du nicht drumherum kommen. Denn selbst wenn Du Dir Deine „Bekanntenketten“ erzeugen willst: Genau so wie oben muss das laufen.

Das Problem an der Sache ist, dass diese Attribute ja fest
beim Datensatz verankert sind. Daher müßte bei jeder Änderung
ein Schwung Datensätze umgeschrieben werden. Denn was
passiert, wenn Heinz Claudia kennenlernt? Der Umweg über Kurt

Tja: Einen Tod muss man sterben. Entweder hast Du die Berechnung zur Abfragezeit oder zwischendrin zur Berechnungszeit. Da aber u. U. viel mehr Datensätze erzeugt werden als wirklich benötigt werden und außerdem zu einem Abfragezeitpunkt nicht wirklich sicher ist, wann/wie aktuell denn die anderen Daten sind, würde ich die Abfragen zur Laufzeit berechnen…

Gruß, Manfred

#10

Hallo Ralf,

datentechnisch wird so etwas durch eine m:n-Beziehung
dargestellt, die jeweils zwei Personen zusammenfasst, die sich
kennen (oder was immer ihre Beziehung sein möge):

eigentlich hatte ich genau das in meinem ersten Posting geschrieben: zwei Tabellen - eine für die Personen, eine für die Bekanntschaften (im ersten Postings noch mit Buchstaben).

Grüße

Stefan

#11

Moin, Stefan,

eigentlich hatte ich genau das in meinem ersten Posting
geschrieben: zwei Tabellen - eine für die Personen, eine für
die Bekanntschaften (im ersten Postings noch mit Buchstaben).

schön, schön. Wenn Du aber im nächsten Schritt auf die Idee kommst, irgendwelche Attribute einzuführen, die nur errechnete Informationen speichern, dann bist Du auf dem Holzweg, weil die bei Änderungen neu berechnet werden müssen. Die Speicherung ist somit nutzlos.

Lies die Tabelle mit den Beziehungen aus und bau daraus eine Matrix, die genau so viele Spalten und Zeilen wie Personen hat, und markiere die bestehenden Beziehungen. Der Rest ist Fleißarbeit: Für alle Personen Wege zu den anderen Personen extrahieren, gewichten, sortieren.

Gruß Ralf