Druckbare Version
hi leute ich habe einen tabelle die sagen wir mal so aussieht
ja ich weiß sieht nicht besonders toll aus und die abfrage soll eine verbindung von 1 nach 6 raus suchen, ich sitzte hier schon ne weile mit schleifen und so. nun ist mir die idee gekommen das es vieleicht schon sowas gibt.Code:spalte1 spalte2
1 2
1 4
2 1
2 3
2 5
3 6
das ergebnis soll also so aussehen.
versteht ihr was ich meine?Code:1 2
2 3
3 6
thx cu SHB
Also ich verstehe rein gar nicht, was Du willst, geht das evtl. genauer?
fs111
Hi,
ich verstehe zwar auch nicht ganz was Du willst, aber echte mathematische Probleme kann man mit einer Datenbank eigentlich nicht lösen. Dafür ist sie schließlich auch nicht gemacht.
Allerdings kann man natürlich mehrere Joins machen, z. B.Nur muß man hierzu natürlich schon im Voraus einen gewissen Lösungsweg kennen.Code:SELECT a.spalte1, c.spalte3 FROM tabelle AS a, tabelle AS b, tabelle AS c WHERE a.spalte2 = b.spalte1 AND b.spalte2 = c.spalte1
Pingu
Hallo,
sehr interessante Frage. Wenn ich Dich richtig verstehe ist das irgendwie sowas wie die Berechnung der "transitiven Hülle" (Pfad von 1 nach 2, von 2 nach x usw.). Das ist eine Abfrage, von der man beweisen kann, dass sie mit SQL nicht möglich ist.
Es geht aber mit PL/SQL (ist bei Oracle und PostgreSQL dabei). Du brauchst dabei while-Schleifen, die reines SQL nicht hat.
Ich verstehe zwar das Problem nicht, aber dann sollte es mit FireBird auch gehen. Dafür muss man allerdings dann eine Stored Procedure schreiben. Vielleicht kann man ja mal in diese Richtung überlegen.Zitat:
Zitat von Christoph
Hans
@Pingu deine Query muss ich mir noch in ruhe zu gemüte ziehen, vertehen werde ich die query schon, nur mit dem erstellen ist es immer so ne sache, ich brauch eigentlich nur einfache abfragen.
@Christoph du hast erkannt, was ich vorhabe ;)
aber es sollte ein mysql server bleiben. sobald owas wie schleifen benötigt werden, kann ich ja auch programmieren, da hat man mehrdimmensionale arrays und sowas nehmen.
@Hans-Georg Normann wie gesagt sollte bei mysql bleiben und statt einer Stored Procedure kann ich auch mit einer programmiersprache arbeiten, kommt doch dann auf selbe raus
tausend dank
cu SHB
Du wirst wohl eine kleine Schleife in der Sprache deiner Wahl schreiben müssen.
Ich habe mal ein Beispiel in Python gegeben (und nur sqlite anstatt mysql benutzt)
Zyklische Routen führen zu einer endlosschleife, wenn es keinen Weg zum Ziel gibt. Die müsstest du natürlich getrennt abfragen.
Der Grundgedanke ist der, dass du, bildlich gesprochen, an jeder Station einen virtuellen Fahrgast in jeden möglichen Zug einsteigen lässt, und dann für jeden einzelen am Zielbahnhof genauso verfährst, bis einer angekommen ist.
Bei langen Strecken wird das natürlich extrem speicherintensiv
Code:import sqlite
DB = sqlite.connect("test")
Cur = DB.cursor()
def FindShortestRoute(start,end,cursor):
routes = [[start]]
while 1:
try:
route = routes.pop()
except IndexError:
# list empty
return None
# route[-1] is the last element
cursor.execute("select * from foo where s1=%i" % route[-1])
for s1,s2 in cursor.fetchall():
if s2 == end:
return route+[s2]
newroute = route + [s2]
routes.append(newroute)
print FindShortestRoute(1,6,Cur) #Result [1, 2, 3, 6]
das nicht alles was gläzt gold ist weiß ich ;)Zitat:
Bei langen Strecken wird das natürlich extrem speicherintensiv
ja aber gibt es eine andere / bessere lösung um routen zu berechnen?
was heißt speicherintensiv, ich meine jede "normale" routen berechnung braucht ihre zeit, um die route zu berechnen, oder denkst du dass das ganze zu lange dauert?
Sagen wir mal so: mit diesem Algorithmus würde ich nicht versuchen, eine DB-Nahverkehrsverbindung von Flensburg nach Freiburg zu berechnen... (Lustigerweise konnten das die alten Fahrplanauskunftsautomaten auch nicht :D)Zitat:
Zitat von shb
Wenn die kürzeste Strecke über 10 Stationen geht, und jede Station nur 4 umsteigemöglichkeiten hat, hast du in etwa 4^10 = 1048576 SQL-Abfragen...
gut 1048576 ist nicht grad wening, geb ich ja zu und an hand der rechnung sehe ich auch wo die abfragen hingehen, aber wenn 12924 in 0.31 sekunden abfragen kann, kommt man dan nicht trotzdem noch auf eine gute zeit, oder meinst nicht?
cu SHB
Schon, nur nicht, wenn 100 Anfragen pro Sekunde bearbeitet werden müssen.
nein sollen auch nicht, das ganze soll ein offline routenplaner werden.
ich hab hier einen thread zu diesem thema eröffnet. Also es woll wirklich nur einen nutzen brauchen.
aber fals ihr noch andere ideen hab zum thema routing, dann immer her damit.
thx cu SHB
Solltest Du in jedem Buch über Graphenalgorithmen finden. Was Du suchst ist die Berechnung des kürzesten Weges ("shortest Path").Zitat:
Zitat von shb