Modellierung: Fahrplan in DB ablegen zur Verbindungssuche

Hallo,

ich möchte ein DB-basiertes Fahrplanauskunftsystem erstellen. Das heißt, ich habe Bus-Fahrpläne mehrere Linien in einer Stadt: Es gibt unterschiedliche Linien, an deren Haltestellen fahren (mit mehr oder minder regelmäßigen Ankunfts- und Abfahrtszeiten) Busse, die für jeden Abschnitt zwischen zwei Stationen eine gewisse Fahrtzeit benötigen.

Mein Ziel ist es, dass Benutzer auf einer Webseite typische Anfragen einer Fahrplanauskunft ausführen können. D.h., es gibt eine Maske mit den Feldern

Startort: _______________ Zielort:_____________________ Abfahrtsdatum & Zeit: ___________________ [Finde Verbindung!]

und ein Klick auf den Button listet mögliche Verbindungen nach Fahrtdauer sortiert auf.

Ich habe schonmal hier im Forum gesucht und diesen Thread zum Abbilden einer einzelnen Buslinie gefunden. Aber mein Problem ist komplexer, und die passende Datenstruktur ist meiner Meinung nach wohl eher ein kanten-gewichteter Graph als eine verkettete Liste. Darauf könnte man das das Single-Source-Shortest-Path Problem (z.B. mit Dijkstras Algorithmus) lösen, um den kürzesten Weg zu finden. Soweit mein Plan in der Theorie.

Aber die Frage ist: Was speichere ich in der DB, was löse ich in SQL, und was in der Sprache der Anwendung (wird wohl PHP werden)? Dijkstras Algorithmus will ich glaube ich nicht in SQL machen, aber ich will ja auch nicht den ganzen Graphen (also alle Knoten und Kanten, d.h., Stationen und Streckenfahrtzeiten) bei jeder Anfrage aus der DB holen, aufbauen, und dann alles in PHP machen.

Das Problem der Abbildung von Graphen in Datenbanken müsste recht verbreitet sein, aber ich habe verblüffend wenig Praktisches dazu gefunden (das Beste war diese DA). Oder gibt es vielleicht sogar irgendein OSS-Projekt, dass einem das Eingeben und Durchsuchen solcher Daten erlaubt?

Vielen Dank für jede Hilfe, Links sind sehr willkommen.

Tim

Eventuell hilft dir pgRouting weiter. Da sollten einige deiner Probleme bereits gelöst sein.
ZUm Design: Du kannst auch in SQL Funktionen schreiben. Oder externe einbinden. Geht alles.
Wann man was in der Datenbank tut entscheidet sich wie man darauf zugreifen möchte und was sie tun. Dinge die viel mit Suchen und Sortieren beschäftigt sind gehören IMHO auf jedenfall in die DB. Dinge die innerhalb der DB benutzt werden sollen, z.B. um die Zahl der Transaktionen und Verbindungen des Clients klein zu halten auch. Wenn ich was mit verschiedenen Clients benutzen möchte ist das auch ein Kandidat für eine DB-Funktion. Aber pauschalisieren kann man das wohl nicht.

Gruß Uwe

Vielen Dank erstmal für die Antwort. Auf pgRouting habe ich schonmal einen kurzen Blick geworfen.

Ich lese mal die Sachen komplett, die ich bis jetzt so gefunden habe und denke noch etwas darüber nach, sobald ich wieder Zeit dafür habe.