[MySQL] Streckenberechnung

Diskutiere das Thema [MySQL] Streckenberechnung im Forum Web-Programmierung. Angenommen ich habe eine Tabelle die Streckenabschnitte enthält. Z.B. so...

D

dms

Angenommen ich habe eine Tabelle die Streckenabschnitte enthält. Z.B. so:

Code:
+------------+------------------+------+-----+---------+----------------+
| Field      | Type             | Null | Key | Default | Extra          |
+------------+------------------+------+-----+---------+----------------+
| id         | int(10) unsigned |      | PRI | NULL    | auto_increment |
| punkt_a    | int(11)          |      |     | 0       |                |
| punkt_b    | int(11)          |      |     | 0       |                |
| entfernung | float(6,2)       |      |     | 0.00    |                |
+------------+------------------+------+-----+---------+----------------+
Code:
+----+---------+---------+------------+
| id | punkt_a | punkt_b | entfernung |
+----+---------+---------+------------+
|  1 |       1 |       2 |       5.00 |
|  2 |       1 |       3 |       4.00 |
|  3 |       2 |       3 |       2.00 |
+----+---------+---------+------------+
In den Feldern punkt_a und punkt_b sind nur ID's, die zu Orten in einer anderen Tabelle gehören.

Jetzt würde ich gerne mit einem einzigen Query alle möglichen Strecke zwischen zwei beliebigen Punkten ermitteln. Ist das möglich?

Für die Punkte 1 und 2 gibt es hier z.B. zwei Wege.

1<->2 Entfernung 5.00
1<->3<->2 Entfernung 6.00

Es wird auch starke Verzweigungen geben, so dass sich eine Strecke zwischen zwei Punkten aus z.B. 10 oder mehr Teilstrecken bilden kann.

Voraussichtlich wird es maximal 100 Punkte geben.

Hat jemand eine Idee?
 
D

dms

Eine kleine Änderung hat sich ergeben. Es wird nun rund 250 Orte geben. Sollte aber belanglos sein.
Wenn es geht sollte das ganze mit MySQL 4.1.1 möglich sein. Wenn es wirklich nicht anders geht ist aber auch 5.x willkommen.
 
Yankee

Yankee

Mitglied
Mitglied seit
27.02.2004
Beiträge
155
Ich behaupte, das ist nicht möglich, da nur rekursiv lösbar.
 
TheFallenAngel

TheFallenAngel

Mitglied
Mitglied seit
27.10.2003
Beiträge
509
Sind dir die IDs bekannt, oder willst du eine Art Routenplaner basteln?
 
moses_78

moses_78

Mitglied
Mitglied seit
08.04.2005
Beiträge
1.299
warum muss es genau ein query sein?
 
A

aeuglein

Mitglied
Mitglied seit
17.03.2004
Beiträge
566
Die SQL ANSI-92 OOP Sprache wird dir für dein Vorhaben keine geeigneten Werkzeuge liefern... Für einfache Additionen/Multiplikationen reicht sie, aber du möchtest ja eine Art "Rekursion" haben.

Da würde ich eher eine kleine Anwendung (Skript sogar) entwickeln, was das erledigt.
 
D

dms

Yankee schrieb:
Ich behaupte, das ist nicht möglich, da nur rekursiv lösbar.
Genau, Rekursion. Sowas muss doch mit SQL irgendwie möglich sein. Mit Nutzerfunktionen vielleicht irgendiwe?...

TheFallenAngel schrieb:
Sind dir die IDs bekannt, oder willst du eine Art Routenplaner basteln?
Die ID's sind nicht bekannt. Ich muss die Strecken zwischen beliebigen Punkten ermitteln können. Routenplaner wäre eine gute Beschreibung für das Vorhaben.

moses_78 schrieb:
warum muss es genau ein query sein?
Bei dem Projekt muss ich peinlichst genau auf Performance achten. Mir ist klar dass es mit mehreren Query's bzw. durch das Ermitteln aller Einträge und Berechnung per Script einfacher bzw. überhaupt möglich ist. Aber wo wäre dann die Herausforderung. :)

aeuglein schrieb:
Da würde ich eher eine kleine Anwendung (Skript sogar) entwickeln, was das erledigt.
So würde ich es natürlich machen wenn es anders nicht möglich ist. Ich wollte nur erst meine Möglichkeiten wissen.
 
Yankee

Yankee

Mitglied
Mitglied seit
27.02.2004
Beiträge
155
dms schrieb:
Genau, Rekursion. Sowas muss doch mit SQL irgendwie möglich sein. Mit Nutzerfunktionen vielleicht irgendiwe?...
Nicht mit MySQL
 
Yankee

Yankee

Mitglied
Mitglied seit
27.02.2004
Beiträge
155
Eine Möglichkeit, die vielen Queries zu beschleunigen, wären prepared statements. Denn wenn Du rekursiv suchst, wirst Du immer wieder den gleichen Query ausführen. Das kann mit oben genanntem Mechanismus optimiert werden. Allerdings wird auch das bei vielen Queries nicht ausreichend performant sein.
 
eSynth

eSynth

Mitglied
Mitglied seit
15.07.2005
Beiträge
498
Thommy schrieb:
Natürlich ist Rekursion mit mySQL lösbar... es ging mal nicht, aber das ist schon etwas her!
Kannst du uns auch was über die Performance erzählen? :rolleyes:
 
Yankee

Yankee

Mitglied
Mitglied seit
27.02.2004
Beiträge
155
Sorry, aber das hat nichts mit nativer Unterstützung von hierarchischen Strukturen zu tun. Das in dem Artikel beschriebene Verfahren ist lediglich ein Workaround. Fraglich ist, ob dieses auf das angegebene Problem anwendbar ist.
 
D

dms

@Thommy Den Artikel kenne ich, habe Ihn vor wenigen Minuten selbst in einem anderen Thread gepostet. :) Joins würde ich aber nicht als Rekursion bezeichnen. Die dort vorgestellte Lösung ist nur auf eine begrenzte Anzahl von Unterkategorien anwendbar.
 
Yankee

Yankee

Mitglied
Mitglied seit
27.02.2004
Beiträge
155
dms schrieb:
@Thommy Den Artikel kenne ich, habe Ihn vor wenigen Minuten selbst in einem anderen Thread gepostet. :) Joins würde ich aber nicht als Rekursion bezeichnen. Die dort vorgestellte Lösung ist nur auf eine begrenzte Anzahl von Unterkategorien anwendbar.
Also soweit ich das jetzt auf die Schnelle erkennen kann ist die Lösung für beliebig tiefe Bäume anwendbar. Hat halt hohe Kosten beim Einfügen und Ändern, aber nicht beim Auslesen.
 
D

dms

Kann sein dass ich was übersehen habe. Habs grad eilig, muss nem Freund heute beim Umzug helfen und habe nur Zeit am Rechner zu sitzen während dem Anziehen oder Frühstücken (wie jetzt *kau*).
Ich schau mir das heute Abend noch mal genauer an. Weiter unten scheint es interessant zu werden.
 
MacCaffeine

MacCaffeine

Mitglied
Mitglied seit
08.12.2003
Beiträge
225
Hi.
Also von der Theorie her läuft es so ganz grob in die Richtung von dem Problem des Handlungsreisenden und das zählt du den, aus der theoretischen Informatik, ziemlich schlecht lösbaren Problemen. Sie sind unter den überhaupt lösbaren Problemen die am schlechtesten lösbaren.
In dem link geht es hinten dran um das Problem der "nested sets", was m.E. hier nichts bringen dürfte.
Direkte Rekursion hab ich unter MySQL noch nicht gesehen. Unter DB2 von IBM kann man mit stored procedures rekursion betreiben, aber da MySQL glaube erst ab der Version 5 ganz rudimentär stored procedures unterstützt, wirst du damit wenig Chancen haben.
Auch sind Rekursionen aus Performance-Sicht das schlechteste, was man haben kann. Gerade, wenn man viele Aufrufe (=Datensätze) hat/haben wird.
Du musst ja zwangsläufig alle Datensätze durchlaufen, um zu überprüfen, ob du da irgendwie irgendwo von A nach B kommst.

Also mit ner MySQL wirst du da schlechte Karten haben. Kann dir jetzt aber leider auch keinen anderen Vorschlag machen.

Interessant ist diese Aufgabe aber auf jeden Fall. Wenn ich was finde, sag ich bescheid.

MfG MDLC =)
 
Zuletzt bearbeitet von einem Moderator:
Yankee

Yankee

Mitglied
Mitglied seit
27.02.2004
Beiträge
155
Also ich behaupte mal, das ist weniger TSP als Dijkstra, wobei Dijkstra in diesem Fall nicht nur den optimalen Weg betrachtet, sondern alle.

Oracle kann mit hierarchischen Strukturen nativ umgehen.
 
wegus

wegus

Mitglied
Mitglied seit
13.09.2004
Beiträge
16.756
postgres ist naturgemäß geeignet mit geometrie-behafteten Problemen umzugehen, wenn hier ein np-unvollständiges Problem vorliegt ( a la Handlungsreisender), dann ist ohnehin nur die Berechnung eines Optimums ( nicht des Absoluten) möglich! Ich hab da irgendwo in einer Subraumfalte des Hirns noch das Wort Greedy-Algorithmus im Kopfe - ist aber schon lange her!
 
MacCaffeine

MacCaffeine

Mitglied
Mitglied seit
08.12.2003
Beiträge
225
@Yankee: hast Recht, der Dijkstra Algorithmus trifft es besser.
Das macht sie Sache mit MySQL aber auch nicht einfacher. :)
 
Oben