Gibt es Abfragen die sowas können?

[shb]

hi leute ich habe einen tabelle die sagen wir mal so aussieht

spalte1  spalte2
    1          2
    1          4
    2          1
    2          3
    2          5
    3          6

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.
das ergebnis soll also so aussehen.

1 2
2 3
3 6

versteht ihr was ich meine?

thx cu SHB

[fs111]

Also ich verstehe rein gar nicht, was Du willst, geht das evtl. genauer?

fs111

[Pingu]

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.

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

Nur muß man hierzu natürlich schon im Voraus einen gewissen Lösungsweg kennen.

Pingu

[Christoph]

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.

[Hans-Georg Normann]

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.

Hans

[shb]

@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

[Joghurt]

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

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]

[shb]

Bei langen Strecken wird das natürlich extrem speicherintensiv

das nicht alles was gläzt gold ist weiß ich
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?

[Joghurt]

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 )

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...

[shb]

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

[Joghurt]

Schon, nur nicht, wenn 100 Anfragen pro Sekunde bearbeitet werden müssen.

[shb]

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

[Christoph]

ja aber gibt es eine andere / bessere lösung um routen zu berechnen?

Solltest Du in jedem Buch über Graphenalgorithmen finden. Was Du suchst ist die Berechnung des kürzesten Weges ("shortest Path").