Der SQL Server liefert eine Vielzahl von Funktionen. Trotzdem steht man zuweilen vor Problemen, die sich nicht oder nur umständlich mit SQL Server Funktionen lösen lassen. Ein Beispiel hierfür ist die Durchführung einer „unscharfen“ Stringsuche. Mit „unscharfer“ Suche bezeichne ich hier die Suche nach ähnlichen Zeichenfolgen. So soll z.B. bei einer Suche nach dem String „Müller“ auch der String „Müler“ getroffen werden.

Zu diesem Zweck bietet der SQL Server die Möglichkeit eigene Funktionen in Form von .NET Programmbibliotheken einzubinden. In diesem Blogbeitrag werde ich diese Möglichkeit am Beispiel der Levenshtein-Distanz demonstrieren. Die Levenshtein-Distanz ist eine bekannte Methode zur Berechnung der Ähnlichkeit zweier Zeichenketten. Sie basiert auf dem Prinzip, zu bestimmen wie viele Zeichenänderungen notwendig sind, um eine Zeichenkette in eine andere umzuwandeln. Je weniger Zeichenänderungen notwendig sind, desto ähnlicher sind sich zwei Zeichenketten.

 

Ein Beispiel (passend zur Weihnachtszeit):

 

s1: Weihnachtsbaum

 

s2: Weihnachtbaum

 

s3: Weihnachtsmarkt

 

 

Um beispielsweise s1 in die Zeichenkette s2 umzuwandeln ist genau eine Operation notwendig (entferne Zeichen ‚s‘). Für die Umwandlung von s1 nach s3 sind vier Umwandlungen notwendig (Tauschen von ‚b‘, ‚u‘ und ‚m‘ sowie das Hinzufügen von ‚t‘ ans Ende der Zeichenkette). Somit sind sich s1 und s2 ähnlicher als s1 und s3.

 

 

In diesem Blogbeitrag will ich anhand der Programmiersprache F# demonstrieren, wie sich dieser Algorithmus in SQL Server einbinden lässt. F# ist eine funktionale Programmiersprache, die sich besonders für die Umsetzung von mathematischen Problemen eignet.

 

 

Eine einfache Implementierung der Levenshtein-Distanz sieht in F# folgendermaßen aus:

(*Funktion min gibt von drei Werten den geringsten Wert zurück*)
let inline min val1 val2 val3 =
    if val1 < val2 && val1 < val3 then val1
    elif val2 < val3 then val2
    else val3

(*Funktion levenshtein gibt die Levenshtein-Distanz von zwei Worten zurück*)
let levenshtein (u:string) (v:string) =
    let m = u.Length //Länge wort1
    let n = v.Length //Länge wort2
    let d = Array2D.create (m+1) (n+1) -1 //Matrix für die Verarbeitung erstellen und mit -1 initialisieren
    //Die rekursive Funktion dist geht durch das zweidimensionale Array und sucht den Weg mit den wenigsten Tauschoperationen
    let rec dist =
        function
        | i, 0 -> i
        | 0, j -> j
        | i,j when d.[i,j] <> -1 -> d.[i,j]
        | i,j ->
            let dval =
                if u.[i-1] = v.[j-1] then dist (i-1, j-1)
                else
                    min 
                        (dist(i-1,j)+1) //deletion
                        (dist(i,j-1)+1) //insertion
                        (dist(i-1,j-1)+1) //substitution
            d.[i,j] <- dval; dval //Aktualisiert den Zellenwert im Array
    dist (m,n) //Der letzte Wert der Matrix wird zurückgegeben

Zur Veranschaulichung hier nochmal die Arbeitsweise des Algorithmus in grafischer Form:

 

 

 

 

 

 

Somit haben wir jetzt einen einfachen

Algorithmus zumvergleichen zweier Zeichenketten. Der nächste Schritt ist es diese Funktionauch für den SQL Server zur Verfügung zu stellen. Hierzu erstellen wir mitHilfe von Visual Studio ein „F# Library“-Projekt und fügen dort unseren Algorithmusein. Damit unsere Funktion auch von außen sichtbar ist, müssen wir Sie in einerKlasse kapseln. Hierfür werden die Schlüsselwörter „type“ bzw. „module“verwendet.

namespace FSharpTestLib
open System

module MyModule =
	… //Hier folgen die Funktionen…

 

Kompilieren wir unsere Anwendung erhalten wir zwei Dateien. Neben einer DLL-Datei mit dem Namen unseres F#-Projekts wurde zudem eine Datei mit dem Namen „FSharp.Core.dll“ erstellt. Die „FSharp.Core.dll“ enthält F# spezifische .NET-Klassen die zusätzlich eingebunden werden müssen, um die Funktionsweise unserer DLL sicherzustellen.

 

Der letzte Schritt besteht darin unsere erstellte Funktion im SQL Server einzubinden. Hierfür kopieren wir die beiden DLL-Dateien in ein für den SQL Server zugreifbares Verzeichnis. Anschließend führen wir folgende SQL-Statements aus.

/*** Nutzung externer Programmbibliotheken erlauben ***/
sp_configure 'clr enabled', 1
GO
reconfigure
GO

/*** Zur Vereinfachung schalten wir Verschlüsselung der externen Programmbibliotheken aus ***/
alter database DLLTest set trustworthy on

/*** Einbinden der zusätzlich benötigten .NET-Klassen ***/
CREATE ASSEMBLY FSharpCore
FROM 'D:\Temp\FSharp.Core.dll'
WITH PERMISSION_SET = UNSAFE;

/*** Einbinden der von uns erstellten DLL ***/
CREATE ASSEMBLY FSharpTestLib 
FROM 'D:\Temp\FSharpTestLib.dll'
WITH PERMISSION_SET = UNSAFE;

GO

/*** Erstellen einer SQL-Funktion ***/
CREATE FUNCTION dbo.levenshtein 
(
	@s1 nvarchar(max),
	@s2 nvarchar(max)
)
RETURNS int
AS EXTERNAL NAME FsharpTestLib.[FSharpTestLib.MyModule].levenshtein

GO

/*** Mit der Funktion kann nun der Levenshtein-Algorithmus im SQL verwendet werden ***/
SELECT [dbo].[levenshtein]('Weihnachtsmarkt','Weihnachtsbaum')
--> Ergebnis: 4

 

Mit „sp_configure“ erlauben wir die Nutzung externer Programmbibliotheken. Anschließend können wir unsere DLL als Assembly einbinden und in Form einer Funktion schließlich im SQL verwenden. Der Einfachheit halber wurde in diesem Beispiel auf eine Verschlüsselung der Assemblies verzichtet.

 

Zum Abschluss nun noch ein kleines SQL-Beispiel zur Demonstration der Funktionsweise. Abgefragt wird hier eine einspaltige Tabelle mit Suchwörtern. Das CASE-Konstrukt dient dazu, die längere der zu vergleichenden Zeichenketten als Grundlage der prozentualen Berechnung zu verwenden.

SELECT 
suchstring, 
[dbo].[levenshtein]('Weihnachtsbaum', suchstring) AS LevenshteinDistanz, 
CONVERT(float,1-([dbo].[levenshtein]('Weihnachtsbaum', suchstring)/CONVERT(float,CASE WHEN
												  LEN(suchstring) > LEN('Weihnachtsbaum') 
											      THEN
												  LEN(suchstring)
											      ELSE
												  LEN('Weihnachtsbaum')
											      END))) * 100 AS [Übereinstimmung in %]
FROM [dbo].[DLLTest]
ORDER by LevenshteinDistanz

 

 

Fazit: Wie in diesem Blogbeitrag gezeigt, lässt sich der Funktionsumfang der .NET Sprachen relativ einfach im SQL Server verwenden. Dadurch lassen sich Probleme lösen, die ansonsten aufwendige SQL Lösungen erfordern würden. Dabei können neben F# auch andere .NET Sprachen verwendet werden.