Wie Netzwerke abbilden?

Beitrag von **ender** » 06.08.2010, 12:50

Wie bildet man mit einer Datenbank Netzwerkbeziehungen von Links ab, sodass z.B. auch die Entfernung zwischen zwei Knotenpunkten abfragbar ist?

Wenn ich z.B. mit MySQL für jede Domain die eingehenden und ausgehenden Links in Tabellen schreibe, komme ich bei mehr als zwei Hops schnell an das Problem nicht mehr die Zwischenstationen herausfinden zu können.

Gibt es vielleicht ein Datenbanksystem, das wie geschaffen für solche Strukturen ist, bzw. ein passendes Modell für MySQL?

von **Anzeige von ABAKUS** »

Beitrag von **smilla** » 10.08.2010, 22:47

Mit Hilfe von Graphen solltest du das berechnen können

Beitrag von **Jannick** » 11.08.2010, 01:13

SQL kann keine Rekursion, da gibt es auch keine DB-Struktur. Es gibt sicherlich DB-Systeme mit Rekursion aber wahrscheinlich eher akademische Spielereien, denn nutzbare Systeme.
Um mit SQL so etwas umzusetzen brauchst du eine Programmiersprache, die darauf aufbaut. PS/SQL für Oracle wäre so etwas, womit auch rekursive Abfragen möglich sind, ob es vergleichbares für MySQL gibt, weiß ich leider nicht.

von **Anzeige von ABAKUS** »

Beitrag von **ender** » 11.08.2010, 01:35

Graphen sind ein guter Tipp, vor allem für die Visualisierung. Wegstrecken sollten recht einfach mit dem Dijkstra´s Algorithmus berechenbar sein. Und bei der Datenbankabbildung schau ich mal, wie weit ich mit MySQL komme, sonst werf ich mal nen Blick auf Oracle PS/SQL.

Beitrag von **nerd** » 11.08.2010, 08:16

Jannick hat geschrieben:SQL kann keine Rekursion, da gibt es auch keine DB-Struktur.

Voelliger quatsch. Du kannst entweder das Adjacency List Model oder das Nested Set Model verwenden, womit du hierarchien abbilden kannst. Rekursionen bekommst du mit self-joins hin. Adjacency List Model ist einfacher zu handhaben, Nested Set Model ist allerdings beim lesezugriff schneller und flexibler.

ich beziehe mich hier auf das nested set model, damit kannst du:
- von jeder stelle aus mit einer einfachgen abfrage den pfad zurueck zu root rausbekommen
- weisst bei jedem element wieviele nodes darin enthalten sind
- eine liste aller in x enthaltenen nodes auslesen
- weisst bei jedem eintrag ob es untergeordnete elemente hat oder nicht (letztes element im zweig)
- beliebig in alle richtungen erweiterbar ohne das du was an der db-struktur aendern musst

https://dev.mysql.com/tech-resources/ar ... -data.html => ctrl+f "The Nested Set Model".

die beispiele und abfragen auf der seite sind allerdings falsch, statt "GROUP BY node.name" sollte es immer "GROUP BY node.id" heissen sonst bekommst du probleme wenn ein name doppelt vergeben ist.
ich habs hier vor einiger zeit umgesetzt um plaetze in eine datenbank zu speichern. Plaetze koennen bei mir entweder Laender, Regionen, Stadte, Strassen oder Hausnummern sein.
Am besten an der sache ist natuerlich das man nur ein feld abfragen muss wenn man was sucht, und keine konstrukte wie "where country=test OR region=test OR city=test" bauen muss und trotzdem noch die abfrage einschraenken kann und z.b. nur plaetze aus Schweden, oder nur stadte, oder nur Stadte mit mehr als 10 strassen in betracht ziehen kann.

noch ein tipp:
wenn du mehr als 1000 zeilen in deiner DB hast solltest du werte wie "tiefe" (entfernung zu root) und pfad (textdarstellung des weges zu root : Welt::Italien::Rom) noch mit in deiner tabelle Cachen - ansosnten bekommst du schnell performance probleme wenn du ein grosses set hast und von mehreren hundert plaetzen nur die "Stadte" haben willst oder den erwaehnen pfad zu root brauchst.

Klingt toll, ist es auch nachdem man sich eine klasse oder mysql-funktionen geschrieben hat die es erlauben diese werte pflegeleicht in der db zu speichern, umzusortieren und zu loeschen

Beitrag von **Beloe007** » 11.08.2010, 09:12

Ich glaube das was du suchst kann man übertragen aus dem Navigationsbereich. Vielleicht die einzelnen Links als Vektoren darstellen, wobei z.B. die Anzahl der Links die Länge darstellen könnte und der Pagerank (falls er interessiert) die Richtung.

https://de.wikipedia.org/wiki/Geodaten

Jeder einzelne Link wäre dann ein Vektor, die Regeln könntest du auch nachträglich noch ändern um eine andere/bessere Darstellung zu erreichen.

Optimal wäre als Ergebnis dann eine art Landkarte die man lesen kann, mit positiven und negativen Regionen... vergleichbar mit Sibirien und der Karibik... das ganze dann noch in 3D und du kannst einen Globus machen.. mit noch Flugrouten usw... denke schon das man so etwas sehr komplex umsetzen könnte, das aber nach und nach wachsen kann, also man muss nicht sofort alles fertig machen.

Aber guck dir mal https://www.touchgraph.com/TGGoogleBrowser.html an... da die Facebook-Version könnte ein weiteres Beispiel einer grafischen Darstellmöglichkeit sein.

Würde aber zu Vektoren tendieren, weil du dann auch für die Zukunft frei bist und die Regeln recht einfach anpassen kannst und auch Matrizen anwenden könntest... auch wenn es am Anfang sicher sehr kompliziert ist, so wärst du später frei und kannst beliebig Wertigkeit und sonst was frei definieren.

Nur mal so als Brainstorming

Beitrag von **Wolke23** » 11.08.2010, 11:50

Wow, das ist ein Thread, der zeigt, dass es in diesem Forum auch richtig hochqualitativ abgehen kann. Bin gespannt, was Ender zaubert

Beitrag von **Jannick** » 11.08.2010, 12:29

nerd hat geschrieben:
Jannick hat geschrieben:SQL kann keine Rekursion, da gibt es auch keine DB-Struktur.
Voelliger quatsch. Du kannst entweder das Adjacency List Model oder das Nested Set Model verwenden, womit du hierarchien abbilden kannst. Rekursionen bekommst du mit self-joins hin.

Abgesehen davon, dass ich deinen Beitrag für sehr gut halte, erweckst du mit der Verneinung meiner Aussage einen falschen Eindruck. Das Adjacency List Model funktioniert nur dann "rekursiv", wenn man die Anzahl der "Nodes" beschränken kann("The main limitation of such an approach is that you need one self-join for every level in the hierarchy"). Das Nested Set Model funktioniert ebenfalls nicht, um eine Reihenfolge von beliebig vielen Nodes zu bekommen.
Angenommen du hast eine unbegrenzte Anzahl von Städten, sowie die Verbindungen zwischen ihnen und du möchtest einen Weg von A nach B mit allen Zwischenorten ausgeben(das ist ja enders Problem). Rekursion wäre es dann, wenn du egal, wie viele Orte zwischen A und B sind diese Reihenfolge ausgeben könntest und das ist, korrigier mich, falls ich falsch liege, mit purem SQL nicht zu machen.
@ender, falls du weißt, dass nie mehr als x Knoten zwischen zwei Knoten in deinem Netzwerk sind, dann ist der obige Tip sehr gut, wenn du echte Rekursion brauchst, dann bleibt dir nur ein anderer Weg.

Beitrag von **ender** » 11.08.2010, 12:50

Erstmal danke für die rege Beteiligung

Ich kann mich auf 10-15 Zwischenknoten beschränken. Sobald mein Testdatenset steht, werd ich sehen, wie lange die einzelnen self-joins brauchen. Dann wird sich zeigen, ob MySQL für mich passt.

Beitrag von **Jannick** » 11.08.2010, 13:23

ender hat geschrieben:Erstmal danke für die rege Beteiligung
Ich kann mich auf 10-15 Zwischenknoten beschränken. Sobald mein Testdatenset steht, werd ich sehen, wie lange die einzelnen self-joins brauchen. Dann wird sich zeigen, ob MySQL für mich passt.

10-15 Selfjoins hört sich schon nach viel an, aber wenn die Tabelle in den cache passt und du Indizes drauf hast, dann dürfte das machbar sein. Du hast dann ja ca. log(|Tabelle|)*15 Index-Zugriffe, das geht schnell, wenn der Index im Speicher liegt, sonst kannst du es, falls du das Ergebnis halbwegs schnell brauchst vergessen.

PS. Ich wäre interessiert daran, zu hören wie es ausgegangen ist und wie schnell das Ganze funktioniert. Kannst dann den thread ja nochmal ausgraben.

Beitrag von **SloMo** » 11.08.2010, 14:03

Kann mir mal einer auf die Sprünge helfen, wie man mit Nested-Sets eine n:m-Beziehung abbildet? Da braucht man pro ausgehendem Link ein Set, oder? Es kommt mir für diesen Anwendungsfall sehr ungeeignet vor.

Beitrag von **nerd** » 11.08.2010, 15:04

achso, du willst wissen wie man von punkt a am schnellsten nach punkt b kommt wenn du nicht weisst wieviele punke dazwischen sind? das hab ich ueberlesen.
ich hatte da vor langer zeit mal ein ausfuehrliches beispiel gesehen wie das z.b. bei fahrplaenen funktioniert, habe aber den link nichtmehr. :/
ich schau morgen nochmal hier vorbei; ist schon 2uhr frueh hier.

Beitrag von **SloMo** » 11.08.2010, 15:09

Für Routenplanung gibts doch Ameisen. Das müsste IMHO der einzige Grund sein, warum die überhaupt auf der Erde sind. Siehe: https://www.ameisenalgorithmus.de

Beitrag von **nerd** » 12.08.2010, 04:23

Hier noch ein paar links zu deinem Route finden problem. Die meisten loesungen beziehen sich auf das traveling salesman problem; was du ja auch dein "wieviel links ist seite A von seite B entfernt" ableiten kannst:

Routenplaner beispiel, Oracle Syntax
("CONNECT BY query"? ist das noch sql? noch nie gesehen....)
https://technology.amis.nl/blog/1221/bu ... in-a-graph

Ueber wieviele freunde kennt person A person B, eigentlich das gleiche prinzip:
https://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77262
https://oracleofbacon.org/how.php

ansonsten mal nach "Traveling salesman problem mysql select" oder so suchen.