Click here to view and discuss this page in DocCommentXchange. In the future, you will be sent there automatically.

SAP Sybase SQL Anywhere 16.0 (Deutsch) » SQL Anywhere Server - SQL-Benutzerhandbuch » Abfragen und Datenänderung » Allgemeine Tabellenausdrücke

 

Das Problem der kürzesten Entfernung

Sie können rekursive allgemeine Tabellenausdrücke verwenden, um ideale Strecken in einem direktiven Graphen zu finden. Jede Zeile in einer Datenbank stellt eine gerichtete Kante dar. Jede Zeile spezifiziert einen Ausgangspunkt, ein Ziel und die Kosten der Reise vom Ausgangspunkt zum Ziel. Abhängig von der Problemstellung können die Kosten die Entfernung, die Reisezeit oder einen anderen Faktor darstellen. Die Rekursion ermöglicht es Ihnen, mögliche Routen durch diesen Graphen zu untersuchen. Aus der Menge der möglichen Routen können Sie dann jene auswählen, die Sie interessieren.

Betrachten Sie zum Beispiel die Problemstellung, einen idealen Weg zwischen den Städten Kitchener und Pembroke zu finden. Es gibt einige mögliche Routen, die Sie alle durch eine Menge von dazwischen liegenden Städten führen. Das Ziel ist es, die kürzesten Routen zu finden und sie miteinander zu vergleichen.

Direktives Diagramm der Entfernungen zwischen Städten.

Als Erstes definieren Sie eine Tabelle, die die Kanten dieses Graphen darstellt, und fügen eine Zeile für jede Kante ein. Da alle Kanten dieses Graphen zwei Richtungen haben, müssen die Kanten, die die umgekehrte Richtung darstellen, ebenfalls eingefügt werden. Das wird erreicht, indem Sie die erste Menge von Zeilen auswählen, aber den Ausgangspunkt und das Ziel vertauschen. Eine Zeile muss beispielsweise die Reise von Kitchener nach Toronto darstellen und eine andere die Reise von Toronto zurück nach Kitchener.



CREATE TABLE travel (
    origin      VARCHAR(10),
    destination VARCHAR(10),
    distance    INT,
  PRIMARY KEY ( origin, destination )
); 
INSERT INTO travel
  SELECT 'Kitchener',  'Toronto',    105 UNION
  SELECT 'Kitchener',  'Barrie',     155 UNION
  SELECT 'North Bay',  'Pembroke',   220 UNION
  SELECT 'Pembroke',   'Ottawa',     150 UNION
  SELECT 'Barrie',     'Toronto',     90 UNION
  SELECT 'Toronto',    'Belleville', 190 UNION
  SELECT 'Belleville', 'Ottawa',     230 UNION
  SELECT 'Belleville', 'Pembroke',   230 UNION
  SELECT 'Barrie',     'Huntsville', 125 UNION
  SELECT 'Huntsville', 'North Bay',  130 UNION
  SELECT 'Huntsville', 'Pembroke',   245; 
INSERT INTO travel   -- Insert the return trips
  SELECT destination, origin, distance
  FROM travel;

Die nächste Aufgabe ist es, die rekursiven allgemeinen Tabellenausdrücke zu schreiben. Da die Reise in Kitchener losgeht, beginnt die Anfangs-Unterabfrage, indem alle möglichen Strecken aus Kitchener heraus ausgewählt werden, zusammen mit den jeweiligen Entfernungen.

Die rekursive Unterabfrage erweitert diese Strecken. Bei jeder Strecke werden Abschnitte hinzugefügt, die von den Zielen der vorherigen Abschnitte ausgehen, wobei die Länge der neuen Abschnitte hinzuaddiert wird, um die aktuellen Gesamtkosten für die einzelnen Strecken zu ermitteln. Aus Gründen der Effizienz werden Strecken beendet, wenn sie eine der folgenden Bedingungen erfüllen:

  • Die Strecke führt zum Ausgangspunkt zurück.

  • Die Strecke führt zum vorherigen Standort zurück.

  • Die Strecke erreicht das endgültige Ziel.

Im aktuellen Beispiel sollte keine Strecke nach Kitchener zurückführen, und alle Strecken sollten beendet werden, wenn sie Pembroke erreichen.

Wenn rekursive Abfragen verwendet werden, um zyklische Diagramme zu untersuchen, ist es wichtig zu überprüfen, dass sie korrekt beendet werden. In diesem Fall sind die oben stehenden Bedingungen unzureichend, da eine Route eine beliebig hohe Anzahl von Reisen hin und zurück zwischen zwei dazwischen liegenden Städten enthalten kann. Die untenstehende rekursive Abfrage garantiert ein Ende, indem die maximale Anzahl von Abschnitten bei jeder gegebenen Route auf sieben beschränkt wird.

Da der Zweck der Beispielsabfrage darin liegt, eine sinnvolle Route zu finden, wählt die Haupt-Abfrage nur jene Routen aus, die weniger als 50 % länger als die kürzeste Route sind.



WITH RECURSIVE
    trip ( route, destination, previous, distance, segments ) AS
( SELECT CAST( origin || ', ' || destination AS VARCHAR(256) ),
         destination, origin, distance, 1
  FROM travel
  WHERE origin = 'Kitchener'
    UNION ALL
  SELECT route || ', ' || v.destination,
         v.destination,            -- current endpoint
         v.origin,                 -- previous endpoint
         t.distance + v.distance,  -- total distance
         segments + 1              -- total number of segments
  FROM trip t JOIN travel v ON t.destination = v.origin
  WHERE v.destination <> 'Kitchener'  -- Don't return to start
    AND v.destination <> t.previous   -- Prevent backtracking
    AND v.origin      <> 'Pembroke'   -- Stop at the end
    AND segments                      -- TERMINATE RECURSION!
          < ( SELECT count(*)/2 FROM travel ) )
SELECT route, distance, segments FROM trip
WHERE destination = 'Pembroke' AND
      distance < 1.5 * ( SELECT MIN( distance )
                         FROM trip
                         WHERE destination = 'Pembroke' )
ORDER BY distance, segments, route;

Wenn diese Anweisung in Bezug auf die oben stehende Datenmenge ausgeführt wird, führt sie zu folgenden Ergebnissen:

route distance segments
Kitchener, Barrie, Huntsville, Pembroke 525 3
Kitchener, Toronto, Belleville, Pembroke 525 3
Kitchener, Toronto, Barrie, Huntsville, Pembroke 565 4
Kitchener, Barrie, Huntsville, North Bay, Pembroke 630 4
Kitchener, Barrie, Toronto, Belleville, Pembroke 665 4
Kitchener, Toronto, Barrie, Huntsville, North Bay, Pembroke 670 5
Kitchener, Toronto, Belleville, Ottawa, Pembroke 675 4