Datalog: logica als querytaal
Stel je een rechercheur voor die geen enkel feit zelf hoeft te verzinnen, maar alleen conclusies trekt uit een stapel kaartjes. Op de kaartjes staan simpele feiten, zoals "Jan is de vader van Piet" en "Piet is de vader van Anna". Daarnaast heeft de rechercheur een klein setje regels, bijvoorbeeld: "als X de vader is van Y, en Y de vader is van Z, dan is X de grootvader van Z". Door die regel mechanisch op alle kaartjes toe te passen, rolt er vanzelf een nieuw feit uit: "Jan is de grootvader van Anna". De rechercheur hoeft niet te bedenken hóe hij moet zoeken, hij hoeft alleen te zeggen wát waar is en welke regels gelden.
Zo werkt Datalog. Het is een programmeertaal, of eigenlijk een querytaal, waarmee je feiten en logische regels opschrijft, waarna een computer daar automatisch alle mogelijke conclusies uit afleidt. Datalog is een vereenvoudigde variant van Prolog, een oudere logische programmeertaal, en wordt vooral gebruikt om vragen te stellen aan databases en kennisgrafen waarin relaties tussen dingen belangrijk zijn: familiebanden, netwerkverbindingen, organisatiestructuren of afhankelijkheden tussen stukjes computercode. Het duikt terug op in nieuwsberichten over kennisgrafen, kunstmatige intelligentie die moet kunnen redeneren, en tools die automatisch beveiligingslekken in software opsporen.
Wat is het precies?
Een Datalog-programma bestaat uit twee soorten regels. Ten eerste zijn er feiten: simpele beweringen zoals "ouder(jan, piet)" of "verbonden(server1, server2)". Ten tweede zijn er regels die zeggen hoe je uit bestaande feiten nieuwe feiten mag afleiden, in de vorm "als dit en dat waar is, dan is ook dat waar". Een regel als "voorouder(X, Y) :- ouder(X, Y)" en "voorouder(X, Z) :- ouder(X, Y), voorouder(Y, Z)" zegt: iedere ouder is een voorouder, en de ouder van een voorouder is zelf ook weer een voorouder. Met die twee regeltjes vind je automatisch alle voorouders in een stamboom, hoe diep die ook is.
Dat lijkt op wat je met SQL kunt in een gewone database, maar er is een belangrijk verschil. SQL is van oorsprong niet goed in dit soort recursieve vragen, waarbij je een regel steeds opnieuw op zijn eigen uitkomst moet toepassen. Moderne SQL-databases hebben daar met "recursieve CTE's" (common table expressions) een lapmiddel voor, maar in Datalog zit recursie in het hart van de taal. Je beschrijft simpelweg wát waar moet zijn, niet hóe de computer dat stap voor stap moet uitrekenen. Dat noemen we declaratief programmeren, in tegenstelling tot de imperatieve stijl van de meeste programmeertalen, waarin je precies voorschrijft welke stappen in welke volgorde moeten gebeuren.
Onder de motorkap werkt een Datalog-systeem meestal "van onderaf naar boven" (bottom-up). Het begint met de bekende feiten en past de regels net zolang herhaald toe tot er geen nieuwe feiten meer bijkomen. Dat eindpunt heet een fixpoint: een toestand waarin verdere toepassing van de regels niets nieuws meer oplevert. Omdat Datalog, anders dan Prolog, geen complexe geneste termen en functies toestaat, is wiskundig te bewijzen dat dit proces altijd stopt. Dat is precies waarom bedrijven Datalog vertrouwen voor taken waar voorspelbaarheid telt: er is geen risico op een oneindige lus.
Eén complicatie is negatie: een regel die zegt "X geldt als Y níet waar is". Dat klinkt onschuldig, maar kan tot tegenstrijdigheden leiden als je niet oplet, bijvoorbeeld wanneer twee regels elkaar via ontkenningen tegenspreken. Onderzoekers lossen dit meestal op met "gestratificeerde negatie": de regels worden in lagen ingedeeld, zodat ontkenningen alleen mogen verwijzen naar feiten uit een eerdere, al afgeronde laag. Dat houdt de taal beheersbaar, maar maakt de theorie ook minder eenvoudig dan de basisversie doet vermoeden.
Wat wil men ermee bereiken?
De kernbelofte van Datalog is een querytaal die krachtig genoeg is voor ingewikkelde, recursieve vragen over relaties, maar tegelijk voorspelbaar en veilig genoeg blijft om op grote schaal te vertrouwen. Waar een algemene programmeertaal in principe alles kan, inclusief eindeloos vastlopen, garandeert Datalog dat een query altijd een antwoord oplevert binnen een begrensde tijd. Dat maakt het aantrekkelijk voor situaties waarin je geen zin hebt in verrassingen: bedrijfsregels, toegangsbeleid, netwerkconfiguraties of kennisgrafen waar duizenden gebruikers tegelijk vragen op afvuren.
Een tweede drijfveer is programma-analyse: het doorzoeken van broncode op patronen, zonder de code daadwerkelijk uit te voeren. Beveiligingsonderzoekers willen bijvoorbeeld weten of gebruikersinvoer ergens ongefilterd in een databasequery terechtkomt, wat kan wijzen op een kwetsbaarheid. Zulke vragen zijn in essentie ook weer recursieve zoektochten door een netwerk van functie-aanroepen en datastromen, en dat is precies waar Datalog in uitblinkt.
Onderliggend is er ook een filosofisch motief: het idee dat bedrijfslogica en beleidsregels expliciet en controleerbaar horen te zijn, in plaats van verstopt in duizenden regels programmeercode die niemand meer helemaal doorgrondt. Door regels in Datalog te schrijven, kun je ze in principe apart lezen, testen en aanpassen, los van de rest van het systeem.
Voorbeelden uit de praktijk
LogicBlox, een bedrijf uit Atlanta dat rond het midden van de jaren 2000 werd opgericht, bouwde een commercieel platform rond een eigen Datalog-dialect genaamd LogiQL. Het werd gebruikt voor bedrijfsanalyse en planning, onder meer in de detailhandel, waar retailers ermee voorraad- en supply chain-vraagstukken doorrekenden.
Datomic, een database ontwikkeld door Rich Hickey (bekend van de programmeertaal Clojure) en zijn bedrijf Cognitect, kwam rond 2012 uit en gebruikt Datalog als querytaal in plaats van SQL. Cognitect, en daarmee Datomic, werd in 2020 overgenomen door de Braziliaanse fintech Nubank.
Semmle, een spin-off van de University of Oxford, ontwikkelde de taal QL, die sterk door Datalog is beïnvloed en bedoeld is om broncode te doorzoeken op kwetsbaarheden en bugs. GitHub nam Semmle in 2019 over; de technologie leeft voort als CodeQL en vormt de basis van GitHub Code Scanning. GitHub Security Lab gebruikte CodeQL onder meer om, rond de ontdekking van de Log4Shell-kwetsbaarheid eind 2021, snel te doorzoeken welke codebases vergelijkbare risico's bevatten.
Soufflé is een opensource-Datalog-engine waar onder meer Oracle Labs en onderzoekers als Bernhard Scholz (University of Sydney) aan bijdroegen. Het wordt veel gebruikt in academisch en industrieel onderzoek naar statische programma-analyse, bijvoorbeeld in het Doop-framework voor het analyseren van Java-code, en in onderzoek naar de beveiliging van Android-apps.
RDFox is een Datalog-gebaseerde kennisgraaf- en redeneer-engine van Oxford Semantic Technologies, een spin-off van de University of Oxford die rond 2017 mede door onderzoeker Boris Motik werd opgericht. Het wordt door verschillende organisaties ingezet om kennisgrafen op te bouwen en er automatisch conclusies uit af te leiden, bijvoorbeeld voor productinformatie of technische documentatie.
Hoe ver is de techniek?
De theorie achter Datalog is allesbehalve nieuw. Het veld ontstond eind jaren zeventig, met een veelgeciteerde workshop en het daaruit voortgekomen boek "Logic and Data Bases" uit 1978, onder redactie van Hervé Gallaire en Jack Minker. In de jaren tachtig en negentig werd de wiskundige basis verder uitgewerkt binnen het onderzoek naar "deductieve databases", databases die niet alleen feiten opslaan maar er ook logisch mee kunnen redeneren. In die zin is Datalog een volwassen, goed begrepen technologie.
Wat wél volop in ontwikkeling is, is de praktische toepassing. Lange tijd bleef Datalog vooral een onderwerp voor academische papers, omdat vroege implementaties traag waren op grote datasets. De afgelopen quzn twee decennia zijn er snellere "engines" gebouwd, zoals Soufflé en RDFox, die met slimme optimalisaties en parallellisatie ook op grotere schaal bruikbaar zijn. Onderzoek naar incrementele evaluatie (waarbij een systeem na een kleine wijziging niet alles opnieuw hoeft te herberekenen) en naar het combineren van Datalog met machine learning en kennisgrafen loopt nog volop.
Er zijn ook duidelijke obstakels. Datalog blijft buiten academische kringen en een paar gespecialiseerde toepassingen relatief onbekend, zeker vergeleken met SQL. De regels rond negatie en aggregatie (zoals tellen of optellen binnen een Datalog-query) maken de taal in de praktijk minder eenvoudig dan de kernidee doet vermoeden. Bovendien staat Datalog niet alleen: SQL-databases hebben met recursieve CTE's een deel van hetzelfde terrein veroverd, en grafendatabases met eigen querytalen zoals Cypher en SPARQL, plus de nieuwere GQL-standaard voor graafqueries, bieden alternatieve manieren om vergelijkbare vragen te stellen. Welke aanpak wint terrein, verschilt sterk per toepassingsgebied en is niet uitgemaakt.
Wie werken eraan?
Onderzoek en ontwikkeling rond Datalog is verspreid over een handvol academische centra en bedrijven. Oracle Labs en de University of Sydney, met onderzoeker Bernhard Scholz, spelen een rol bij de Soufflé-engine. De University of Oxford en het daaruit voortgekomen bedrijf Oxford Semantic Technologies, met Boris Motik, ontwikkelen RDFox voor kennisgraaftoepassingen. GitHub Security Lab bouwt voort op de Oxford-wortels van Semmle om CodeQL te onderhouden en in te zetten voor beveiligingsonderzoek. Aan de Aarhus University in Denemarken werkt onderzoeker Magnus Madsen aan Flix, een programmeertaal die Datalog-achtige regels combineert met gewone functionele en imperatieve code, vooral gericht op programma-analyse.
Breder gezien leeft het onderwerp vooral binnen de academische databasegemeenschap, met publicaties op conferenties als VLDB, SIGMOD en PODS. Geografisch ligt het zwaartepunt in de Verenigde Staten, het Verenigd Koninkrijk, Australië en Denemarken, met verspreide bijdragen uit de rest van Europa.