Das kniffelige Teilsummenproblem mit T-SQL gelöst
Im Rahmen der Ausbildung unserer Werkstudenten bekam ich den Auftrag, diesen die Grundzüge der Data Definition Language (DDL) und der Data Manipulation Language (DML) näher zu bringen. Doch schnell zeigte sich, dass die beiden Masterstudenten der Mathematik nicht nur sehr lernbereit und wissbegierig, sondern auch extrem gut im Verständnis der grundlegenden Gedanken der Abfragesprache T-SQL waren. Selbst fortgeschrittene Techniken wie die Idee der Rekursion beherrschten sie in Rekordzeit. Es war also an mir, neue Aufgabenfelder zu präsentieren und so das Potential der beiden Mitarbeiter zu fördern.
Es galt also, Problemfälle für den SQL-Server zu finden, die sie mit den bisher gelernten Standard-T-SQL-Mitteln nicht gelöst bekommen hätten. Das faszinierende Element an dieser Aufgabe war es, die eine Fragestellung zu kreieren, die bei übersichtlicher Datenmenge sowie dem einfachen Aufbau der Testdaten eine Situation beschreibt, deren Einfachheit mit wenigen Worten erfassbar ist. Dabei sollte sie dennoch so komplex daherkommen, dass selbst erfahrene Datenbankentwickler nicht sofort auf einen Lösungsansatz kommen. Konnte es mir wirklich gelingen, meine Kollegen mit einer simplen Tabelle mit nur zwei Spalten und nur 12 Datensätzen derart ins Schwitzen zu bringen? Schnell konstruierte ich eine theoretische Fragestellung, die ich nicht auf Anhieb lösen konnte. Nun galt es einen passenden Anwendungsfall aus dem echten Leben zu finden…
Die ausführliche Internetrecherche brachte schnell zu Tage, dass es sich bei meinem Problem um einen Spezialfall des sogenannten "Rucksack"-Problems handelte. Es ist in der wissenschaftlichen Ausbildung der Mathematik und Informatik verallgemeinert als "Teilsummenproblem" bekannt [1]. Abseits des Lehrbuchbeispiels eines Bankräubers, der nur auf eine begrenzte Rucksack-Kapazität zum Abtransport der Beute zugreifen kann und nun entscheiden muss, welche Säcke er einpackt und welche er aus Platz- und Gewichtsgründen zurücklassen muss, fiel mir eine Anfrage meines kleinen Sohnes als geeignetes Beispiel ein.
Mit ihm hatten wir in jungen Jahren folgende Vereinbarung bei dem Besuch eines Kirmesplatzes getroffen:
- Mein Sohn muss kein eigenes Taschengeld investieren, er bekommt genauso wie seine größere Schwester eine individuelle Summe von Oma, Opa und den Eltern zur Verfügung gestellt.
- Vorab darf er sich im Internet informieren, welche Fahrgeschäfte der Rummel bietet und welche Möglichkeiten der Verköstigung er gerne aufsuchen möchte.
- Nach Freigabe der jeweiligen Attraktion darf er eine Liste anfertigen, wie er die zur Verfügung stehende Summe ausgeben möchte. Dabei gibt es keine Einschränkungen, theoretisch könnte er alles in Eis oder Geisterbahnfahrten investieren, er kann aber die Attraktionen auch beliebig anders kombinieren.
- Mein Sohn ist von dem Typ Kinder, die gerne am nächsten Schultag bei allen Themen mitreden. Daher versucht er, so viele verschiedene Attraktionen wie möglich zu nutzen.
- Seine Sparsamkeit führt dazu, dass er
… keinesfalls das gesetzte Limit überschreiten wird, damit er kein eigenes Taschengeld opfern muss und
… den zur Verfügung gestellten Betrag so weit wie nur eben möglich ausreizt, damit kein Geld verschwendet wird, denn: ungenutzte Beträge verfallen und gehen zurück an Oma, Opa und die Eltern!
Besonders der letzte Punkt war pure Motivation für den Nachwuchs, konnte er doch so eigenes Taschengeld sparen. Mein Sohn war mit dieser kleinen und vermutlich so simplen Matheaufgabe tagelang in seinem Zimmer verschwunden und optimierte mit Papier und Bleistift vor sich hin. Für einen Grundschüler war seine Rechenleistung enorm. Schon für diese extra Lerneinheit ist das Verfahren zu empfehlen. Irgendwann kam er in Begleitung seiner großen Schwester in mein Zimmer und forderte mich auf, das Problem für die Zukunft mit Rechnerunterstützung zu lösen – schließlich sei ich ja Informatiker. Also warf ich den SQL-Server an und schaffte erst mal die Grundvoraussetzungen: Eine entsprechende Tabelle mit Testdaten.
-- Schema OKTOBERFEST anlegen, um Objekte sauber der Aufgabe zuordnen zu können
CREATE SCHEMA [Oktoberfest]
GO
-- Tabelle ATTRAKTION im Schema OKTOBERFEST anlegen
CREATE TABLE [Oktoberfest].[Attraktion](
[ID] [INT] PRIMARY KEY IDENTITY(1,1)
, [Attraktion] [NVARCHAR](20) NULL
, [Preis] [MONEY] NULL
) ON [PRIMARY]
GO
-- Tabelle ATTRAKTION im Schema OKTOBERFEST mit den Inhalten (beispielhafte Testdaten) aus der Fragestellung füllen
INSERT INTO [Oktoberfest].[Attraktion] VALUES
('Kettenkarussell', 2.15)
, ('Geisterbahn', 4.50)
, ('Raupe', 2.80)
, ('Würstchenstand', 4.20)
, ('Softgetränk', 1.75)
, ('Riesenrad', 5.30)
, ('Autoscooter', 3.10)
, ('Entenangeln', 2.40)
, ('Dosenwerfen', 2.05)
, ('Losbude', 1.55)
, ('Wilde Maus', 4.30)
, ('Kamelrennen', 1.60)
GODoch wie sollte man nun die gewünschten Informationen extrahieren? Trotz des simplen Aufbaus und der geringen Zahl der Testdaten schlug die gewaltige Komplexitätskeule der Kombinatorik gnadenlos zu. Betrachtet man die Fragestellung mit etwas Mathematik, entspricht die Herausforderung nach etwas Vereinfachung (bspw. der Anpassung des Einzelpreises je Attraktion auf einen Durchschnitt) dem berühmten "Urnenmodell mit Zurücklegen" [2].
Der erste Ansatz war traditionell der eines Entwicklers: Man nehme ein paar Schleifen, addiere die jeweilige Ausgabe für jede noch mögliche Attraktion einfach auf und bilde so ein paar Fallunterscheidungen, zwischen denen man sich dann nur noch für die gewollte Variante entscheiden muss.
Doch wie groß muss ein Schleifenzähler denn maximal werden können? Da mein Sohn theoretisch auch die billigste Attraktion solange wiederholt nutzen durfte, bis der zur Verfügung stehende Gesamtbetrag aufgebraucht war, half für die erste Einschätzung eine einfache Division:
MaxAnzahlNutzungen = zur Verfügung stehender Gesamtbetrag / Minimaleinzelpreis über alle Attraktionen
Auch die Abbruchbedingung für die Hauptschleife ist schnell gefunden: Der vorgegebene Gesamtbetrag darf keinesfalls überschritten werden. Hier hört die Auflistung der einfachen Grundideen aber schon auf, denn schnell stellte sich der Ansatz, dem Problem mit Schleifen, Cursor und ähnlichem beizukommen, als untauglich heraus. Was bei einer geringen Zahl von Attraktionen und einem sehr kleinen verfügbaren Gesamtbetrag noch halbwegs akzeptable Laufzeiten erzeugte, wurde extrem unhandlich, sobald man auch nur einen dieser Parameter erhöhte.
Wir nennen die Zahl der Kugeln (=Attraktionen) n und die Anzahl der Ziehungen (=Fahrten/Einkäufe) k. Die Reihenfolge, in der die Kugeln gezogen werden, ist irrelevant.
Es gilt die mathematische Formel aus der Kombinatorik:
Stark vereinfacht heißt das: Bei einem Durchschnittspreis von bspw. 3 Euro pro Attraktion und einem Budget von 21 Euro kann man 7 Aktionen tätigen. Werden 12 Attraktionen angeboten ergibt dies:
= 31.824 Möglichkeiten
Bei einem Durchschnittspreis von 2,50 Euro, einer Auswahl aus 20 Attraktionen und einem Budget von 30 Euro erreicht die Anzahl der Kombinationen schon Höhen, die die TempDB vor ernsthafte Probleme stellen kann:
= 141.120.525 Möglichkeiten!
Damit war relativ schnell klar, dass manuell erstellte Schleifen und Cursor hier nicht zielführend zu nutzen sein würden. Derartige Ideen lassen sich einfach nicht effizient umsetzen und bedeuten dann in der Laufzeitbetrachtung die rote Karte. Aber der SQL-Server kennt ja noch ein paar mehr Wege. Ich kam mit einer rekursiven CTE und tatkräftiger Hilfe der beiden Mathestudenten relativ schnell zum Ziel. Diese ist simpel zu verstehen und zu warten, schon durch Microsoft laufzeitoptimiert und einfach aufzurufen. Um das Ganze praktisch zu gestalten habe ich die CTE in eine Stored Procedure ausgelagert.
Während der Tests fiel auf, dass es durchaus Kombinationen von Attraktionseinzelpreisen und dem verfügbaren Gesamtpreis gibt, die mathematisch nicht genau aufgingen. Also bauten wir noch einen weiteren Parameter ein, der angab, wie hoch die prozentuale Abweichung nach unten vom vorgegebenen Gesamtbetrag sein durfte. Dieser Prozentwert erlaubte dann auch die Ausgabe von Lösungsdatensätzen, die nicht genau auf die geforderte Summe kamen, aber diese nur geringfügig unterschritten:
-- Prozedur SPASSGELDAUSGEBEN im Schema OKTOBERFEST anlegen
CREATE OR ALTER PROCEDURE [Oktoberfest].[SpassgeldAusgeben]
@ZielPreis MONEY
, @ProzentualeAbweichung INTEGER
AS
BEGIN
SET NOCOUNT ON;
;WITH loopquery
(
[Letzte_id]
, [Kosten]
, [AnzahlAttraktionen]
, [Attraktionen]
)
AS (
-- Initialisierung der Rekursion
SELECT
[att].[ID] AS [ID]
, [att].[Preis] AS [Preis]
, 1 AS [AnzahlAttraktionen]
, CAST([att].[Attraktion] AS VARCHAR(MAX)) AS [Attraktionen]
FROM [Oktoberfest].[Attraktion] AS [att]
UNION ALL
-- Rekursion mit der Summierung der Attraktionsanzahl und des Preises
SELECT
[p].ID
, [lq].[Kosten] + [p].[Preis]
, [AnzahlAttraktionen] + 1
, CAST([lq].[Attraktionen] + ‘, ‘ + [p].[Attraktion] AS VARCHAR(MAX))
FROM loopquery AS [lq]
INNER JOIN [Oktoberfest].[Attraktion] AS [p] ON [p].[ID] >= [lq].[Letzte_id]
WHERE 1 = 1
-- Abbruchbedingung der Rekursion
AND [lq].[Kosten] + [p].[Preis] <= @ZielPreis
)
-- Ausgabe des Ergebnisses
SELECT –TOP x WITH TIES
@ZielPreis AS [Zielpreis]
, [Kosten] AS [Kosten]
, [AnzahlAttraktionen] AS AnzahlAttraktionen]
, [Attraktionen] AS [Attraktionen]
FROM loopquery
WHERE 1=1
AND [Kosten] >= ((@ZielPreis / 100) * (100 – @ProzentualeAbweichung))
ORDER BY [Kosten] DESC, [AnzahlAttraktionen] DESC
END
GO
Die auskommentierte Stelle im Quelltext, in der die Formulierung "TOP x WITH TIES" vorkommt, steuert dabei, ob nur eine bestimmte Anzahl von Ergebnissen (TOP x) ausgegeben werden sollen, und ob "identisch gute" Ergebnisse einzeln oder jeweils zählen (WITH TIES). Der Aufruf der Prozedur bei einem einkommentierten "TOP 3 WITH TIES" bringt also maximal drei unterschiedliche aber evtl. sogar mehr (dann gleichwertige) Ergebnisse.
Der Aufruf der CTE-Prozedur geht dann schnell von der Hand. Man bestückt die notwendigen Parameter und übergibt der Prozedur damit die Information, wie hoch die zur Verfügung stehende Summe ist und ob diese genau zu treffen ist oder eine Abweichung nach unten toleriert wird. Dieser Schwellwert ist in Prozent anzugeben.
Übergibt man der Prozedur mit 21,80 Euro und einer erlaubten Abweichung von 2% entsprechende Parameter, ermittelt der SQL-Server schon 16.030 mögliche Kombinationen, die die gestellten Bedingungen erfüllen. Dabei wird das Ergebnis nach Grad der Erreichung der Vorgabesumme sowie nach Anzahl der damit nutzbaren Attraktionen sortiert:
DECLARE @RC INTEGER
DECLARE @ZielPreis MONEY
DECLARE @ProzentualeAbweichung INTEGER
SET @ZielPreis = 21.80
SET @ProzentualeAbweichung = 2
EXECUTE @RC = [Oktoberfest].[SpassgeldAusgeben]
@ZielPreis, @ProzentualeAbweichung
GOMit diesem Stand nun eine Lösung zu entwickeln, die die Anzahl der unterschiedlichen Attraktionen zählt und diese danach zu sortieren, ist dann nur noch eine Fingerübung…
CREATE OR ALTER PROCEDURE [Oktoberfest].[SpassgeldAusgeben]
@ZielPreis MONEY
, @ProzentualeAbweichung INTEGER
AS
BEGIN
SET NOCOUNT ON;
;WITH loopquery
(
[Letzte_id]
, [Kosten]
, [AnzahlAktionen]
, [AnzahlUnique]
, [Attraktionen]
)
AS (
-- Initialisierung der Rekursion
SELECT
[att].[ID] AS [ID]
, [att].[Preis] AS [Preis]
, 1 AS [AnzahlAktionen]
, 1 AS [AnzahlUnique]
, CAST([att].[Attraktion] AS VARCHAR(MAX)) AS [Attraktionen]
FROM [Oktoberfest].[Attraktion] AS [att]
UNION ALL
-- Rekursion mit der Summierung der Attraktionsanzahl und des Preises
SELECT
[p].ID
, [lq].[Kosten] + [p].[Preis]
, [AnzahlAktionen] + 1
, CASE
WHEN CHARINDEX([p].[Attraktion], [lq].[Attraktionen]) = 0
THEN [AnzahlUnique] + 1
ELSE [AnzahlUnique]
END
, CAST([lq].[Attraktionen] + ', ' + [p].[Attraktion] AS VARCHAR(MAX))
FROM loopquery AS [lq]
INNER JOIN [Oktoberfest].[Attraktion] AS [p] ON [p].[ID] >= [lq].[Letzte_id]
WHERE 1 = 1
-- Abbruchbedingung der Rekursion
AND [lq].[Kosten] + [p].[Preis] <= @ZielPreis
)
-- Ausgabe des Ergebnisses
SELECT --TOP 1 WITH TIES
@ZielPreis AS [Zielpreis]
, [Kosten] AS [Kosten]
, [AnzahlAktionen] AS [AnzahlAktionen]
, AnzahlUnique AS [AnzahlUnique]
, [Attraktionen] AS [Attraktionen]
FROM loopquery
WHERE 1=1
AND [Kosten] >= ((@ZielPreis / 100) * (100 - @ProzentualeAbweichung))
ORDER BY [AnzahlUnique] DESC, [Kosten] DESC, [AnzahlAktionen] DESC
END
GO
