• Entwicklung/Architektur
  • Methoden
  • Programmiersprachen
• Betrieb
  • Datenbanken
  • Server
  • IT-Security
  • Speicher
  • Netzwerke
  • Virtualisierung
  • Verfügbarkeit
  • Künstliche Intelligenz
• Management und Recht
  • Projektmanagement
  • Digitalisierung
  • IT-Recht
  • IT-Selbständige
• Aktuelles
• Termine
• IT-Jobs

☰

• Entwicklung
• Betrieb
• Management und Recht
• News
• IT-Jobs
• Newsletter

Torsten Ahlemeyer 10. Mai 2022

Wie löst man mit SQL einen Zauberwürfel?

Wie die Idee der Graph-DB hier für Geschwindigkeit sorgt

Nach dieser Aktion stehen in der Datenbank genau 3.674.160 unterschiedliche Datensätze, die jeweils eine Würfelposition darstellen.

Umbau vom rationalen Ansatz auf die Graph-DB

Um die unbestreitbaren Vorteile der Graph-Datenbank nutzen zu können, sind nun ein paar Umbaumaßnahmen an diesen Daten notwendig. Wir überführen unser Modell dazu in Graph-Objekte, also eine Knoten- und eine Kantentabelle. Das Beispiel des Zauberwürfels eignet sich sehr gut, um das Vorgehen und die Effektivität des Graph-Ansatzes zu demonstrieren.

Eine Position, also der verdrehte Zustand eines Rubik Cubes, entspricht einem Knoten. Die Bewegung zwischen zwei Knoten bildet dann die Kantentabelle ab. Sie repräsentiert also den Zug, der einen Ausgangswürfel in einen Endwürfel überführt, indem beispielsweise die obere Ebene 90° gegen den Uhrzeigersinn gedreht wird. All diese Informationen finden wir in der vorhin erschaffenen Tabelle [RubiksCube].[Zugkombinationen]. Um diese in Knoten- und Kantentabelle zu überführen, reichen ein paar Zellen Quellcode:

-- Diese Tabelle stellt die Knoten des Graphen dar
CREATE TABLE [RubiksCube].[Position] (
	  [ID]			 BIGINT		    PRIMARY KEY
	, [PositionID]	 VARCHAR(24)
	) AS NODE;
GO

-- Diese Tabelle stellt die Kanten, also die Verbindungen zwischen den Knoten, dar
CREATE TABLE [RubiksCube].[dreht_nach] (
	  [ID]			  BIGINT		PRIMARY KEY 
    , [Drehung]		  VARCHAR(25)
	, [Kosten]		  INTEGER
	, [Startposition] CHAR(24)
	, [Endposition]	  CHAR(24)
  ) AS EDGE;
GO

Diese Codezeilen zur Tabellenerstellung unterscheiden sich vom bekannten relationalen Standard nur durch jeweils zwei Wörter: AS NOTE bzw. AS EDGE. Aufgrund dieser Schlüsselwörter weiß der SQL Server, dass es sich um Graph-Tabellen handelt. Diese müssen nun mit Inhalt gefüllt werden:

-- Inhalte für die Knotentabelle [RubiksCube].[Position] erzeugen
INSERT INTO [RubiksCube].[Position]
SELECT * FROM (
	SELECT 
		  ROW_NUMBER() OVER(ORDER BY [Ausgangsposition] ASC) - 1	AS [ID]		-- (Informatiker zählen ab "0", daher "-1", da ROW_NUMBER bei "1" beginnt
		, [Ausgangsposition]		                                AS [PositionID]
	FROM
	(
		SELECT DISTINCT 
			[Ausgangsposition]	AS [Ausgangsposition]
		FROM [RubiksCube].[ZugKombinationen]
	) AS [DummyInnen]
) AS [DummyAussen]
GO


-- Inhalte für die Kantentabelle [RubiksCube].[dreht_nach] erzeugen
INSERT INTO	[RubiksCube].[dreht_nach]
SELECT 
	  (SELECT $node_id FROM [RubiksCube].[Position] WHERE ID = [PO1].[ID])			-- KEIN Alias !!!
	, (SELECT $node_id FROM [RubiksCube].[Position] WHERE ID = [PO2].[ID])			-- KEIN Alias !!!
	, ROW_NUMBER() OVER(ORDER BY [Ausgangsposition] ASC) - 1					AS [ID]
	, [Bewegung]	         AS [Drehung]	    -- Identifiziert die Drehung, z.B. "RechtsHoch"
	, 1		                 AS [Kosten]	    -- Anzahl minimaler Züge bis zur Lösung
	, [Ausgangsposition]	 AS [Startposition]	-- Position VOR dem Drehen
	, [Zielposition]	     AS [Endposition]	-- Position NACH dem Drehen
FROM [RubiksCube].[ZugKombinationen] AS [ZK]
INNER JOIN [RubiksCube].[Position] AS [PO1]
	ON [ZK].[Ausgangsposition] = [PO1].[PositionID]
INNER JOIN [RubiksCube].[Position] AS [PO2]
	ON AND [ZK].[Zielposition] = [PO2].[PositionID]
GO

Während die Füllung der Kantentabelle [RubikCube].[Position] genau nach dem aus der relationalen Welt bekannten Muster abläuft, fallen bei der Füllung der Kantentabelle die beiden Subselects auf. Sie ermitteln zur Laufzeit die IDs aus der Knotentabelle, welche beim Insert angegeben werden müssen. Daher ist die Laufzeit dieses Skripts einmalig auch recht hoch – aber der Aufwand lohnt sich 1000fach bei späteren Abfragen.

Wir lösen blitzschnell jeden noch so verdrehten Zauberwürfel

Die eigentliche Lösung ist nun schnell runterprogrammiert und noch schneller ausgeführt. Dank der Abfragesprache "Cypher" kann man sie fast genau niederschreiben, wie man sie gedanklich formuliert:

CREATE OR ALTER PROCEDURE [RubiksCube].[prcGraphLoesung]
	  @Start   CHAR(24)
	, @Ziel	   CHAR(24)
AS
BEGIN
	SET NOCOUNT ON;

	SELECT 
		  [innen].[Startposition]		AS [Startposition]
		, [innen].[Drehungen]		    AS [Drehung]
		, [innen].[Zielposition]		AS [Zielposition]
	FROM
		(SELECT 
			  [Start].[PositionID]	AS [Startposition]
			, STRING_AGG([dn].[Drehung], '->')
WITHIN GROUP (GRAPH PATH)	AS [Drehungen]
			, LAST_VALUE([Ziel].[PositionID])	
WITHIN GROUP (GRAPH PATH)	AS [Zielposition]
			FROM 
				  [RubiksCube].[Position]		            AS [Start]
				, [RubiksCube].[dreht_nach]		FOR PATH	AS [dn]
				, [RubiksCube].[Position]		FOR PATH	AS [Ziel]
			WHERE MATCH(SHORTEST_PATH([Start](-([dn])->[Ziel])+))
			AND [Start].[PositionID] = @Start
		) AS [innen]
	WHERE [innen].[Zielposition] = @Ziel
END
GO

Übergeben werden der Lösungsprozedur nur die Strings, die den verdrehten und den gewünschten Würfel symbolisieren. Innerhalb der Prozedur sind folgende Punkte bemerkenswert:

1. Die STRING_AGG-Funktion dient der Verkettung der einzelnen Lösungsschritte. Diese werden mit Pfeilen separiert hintereinander gehängt.
2. Im FROM-Teil gibt es zwei unterschiedliche Aliase auf dieselbe Knotentabelle.
3. Es gibt keine JOINs mehr (die Logik einer Graph-DB extrahiert die Verbindungen aus der Kantentabelle, hier haben wir die IDs ja extra hinterlegt).
4. In der WHERE-Klausel gibt es ein neues Schlüsselwort: MATCH.
5. Wer genau hinsieht, erkennt einen angedeuteten Pfeil, der die Beziehungsrichtung vorgibt. Er läuft in der MATCH-Klausel von [Start] über [dn] nach [Ziel].
6. Der Befehl SHORTEST_PATH sucht nun die schnellste Zugkombination vom Ausgangs- zum Zielwürfel. Dabei ist zu beachten, dass der Algorithmus gewollt mit der Erfolgsmeldung abbricht, sobald er sicher ist, dass es keine kürzere Möglichkeit mehr gibt. Sollte es also zwei identisch lange Lösungen geben, wird nur die erste gefunden.

Die Vor- und Nachteile dieser Lösung

Dank der adjazenten Datenspeicherung (fachlich benachbarte Informationen werden auch nah beieinander gespeichert, so dass nicht immer der gesamte Datenbestand durchsucht werden muss) und der automatischen Indizierung von Graph-Tabellen dauert die Suche nach der optimalen Lösung mit diesem Ansatz nur noch Bruchteile von Sekunden. Dies bezahlt man mit der einmaligen Initialisierung, also dem Aufbau und dem Füllen der Graph-Tabellen. Es gilt also abzuwägen, wie oft man ultraschnelle Abfragen benötigt, um einschätzen zu können, ob der Aufwand des Aufbaues einer Graph-DB Sinn macht. Denkt man aber bspw. an eine Online-Preisauskunft für Flugverbindungen, liegt das Ergebnis einer derartigen Überlegung sicher schnell auf der Hand.

Natürlich kann man den Algorithmus noch weiter "pimpen". So ist es beispielsweise ein Leichtes, auch eine 180°-Drehung einer Ebene als einen einzigen Zug einzubauen. Dieser würde dann die benötigte Maximalzahl notwendiger Züge bis zur Lösung auf 20 drücken. Auch ist die unterschiedliche Gewichtung von Zügen denkbar. Implementiert man bspw., dass Drehungen gegen den Uhrzeigersinn teurer sind als Drehungen mit dem Uhrzeigersinn, könnte der Algorithmus zur Lösungsfindung nicht einfach stumpf die Zahl der notwendigen Schritte zählen, sondern die Kosten optimieren. Derartige Nebenbedingungen kennt man bspw. von Navigationssystemen, die intern identisch funktionieren. Hier gibt es unterschiedlich gewichtete Straßen (Autobahnen werden Dorfstraßen vorgezogen) oder bspw. mautpflichtige Streckenabschnitte, die mit kostenfreien Wegen konkurrieren.

Der komplette Quellcode für das Projekt "Rubiks Cube" ist abrufbar [2]. Er enthält zur Gegenüberstellung auch meinen Code einer klassischen, rein relationalen Lösung mit Hilfe einer Rekursion. Auch sie führt zu einem korrekten Ergebnis, ist der Graph-Variante aber sowohl bzgl. der Komplexität der Implementierung als auch vor allem im Laufzeitverhalten gnadenlos unterlegen.

Autor

Das könnte Sie auch interessieren