Datalog | |
---|---|
Språkklass | Boolean , deklarativ |
Framträdde i | 1986 |
Typ system | Svag |
Dialekter | Datomic , pyDatalog , Dyna etc. |
Datalog är ett deklarativt logiskt programmeringsspråk. Även om det syntaktiskt ser ut som en delmängd av Prolog , använder Datalog i allmänhet en nedifrån och upp snarare än en upplösningsmodell för uttrycksupplösning. Denna skillnad leder till en signifikant skillnad i beteende och egenskaper från Prolog. Det används ofta som frågespråk för deduktiva databaser. Under de senaste åren har Datalog hittat nya användningsområden inom dataintegration, informationsextraktion, nätverk, programanalys, säkerhet, molnberäkning och maskininlärning [1] [2] .
Dess ursprung går tillbaka till början av logikprogrammering, men det började sticka ut som ett separat ämne runt 1977, när Herve Galler och Jack Minker organiserade ett seminarium om logik och databaser [3] . David Mayer är krediterad för att ha myntat termen Datalog [4] .
Till skillnad från Prolog kan Datalog-programsatser anges i valfri ordning. Dessutom är Datalog-frågor mot ändliga uppsättningar garanterade att slutföra, vilket är anledningen till att Datalog inte har en cut-sats i Prolog. Detta gör Datalog till ett helt deklarativt språk.
Till skillnad från Prolog, Datalog:
Proceduren för att lösa en fråga med Datalog är baserad på första ordningens logik och är därför korrekt och komplett. Datalog är dock inte Turing komplett och används därför som ett domänspecifikt språk som kan dra fördel av effektiva algoritmer utformade för att lösa frågor. Faktum är att olika metoder har föreslagits för att effektivt exekvera frågor, såsom Magic Sets-algoritmen [6] , tabelllogikprogrammering [7] eller SLG-upplösning [8] .
Några mycket använda databassystem inkluderar idéer och algoritmer utvecklade för Datalog. Till exempel inkluderar SQL:1999-standarden rekursiva frågor, och Magic Sets-algoritmen (ursprungligen utformad för att utvärdera datalogfrågor snabbare) är implementerad i IBM DB2 . Dessutom ligger Datalog-motorer bakom specialiserade databassystem som Intellidimension-databasen för den semantiska webben [9] . Flera tillägg har gjorts till Datalog, till exempel för att stödja aggregerade funktioner, för att möjliggöra objektorienterad programmering eller för att tillåta disjunktioner som meningsrubriker. Dessa tillägg har en betydande inverkan på definitionen av Datalog-semantik och på implementeringar av specifika versioner av Datalog-tolken.
Datalogprogram kan eller får inte använda negation i regelkroppar: Datalogprogram med negation behöver ofta använda det som en stratifierad negation för att säkerställa att semantiken är väldefinierad. Datalogprogram kan använda olikheter mellan variabler i regelkroppar eller inte.
Vissa datalogsyntaxfragment är definierade, till exempel följande (mest begränsade till minst begränsade):
En annan begränsning gäller användningen av rekursion: en icke-rekursiv Datalog definieras genom att inte tillåta rekursion i definitionen av Datalog-program. Det här datalogkodavsnittet är lika uttrycksfullt som sammanlänkande frågor, men att skriva frågor som en icke-rekursiv datalogg kan vara mer koncis.
Begränsningsproblemet för Datalog handlar om huruvida Datalog-programmet är begränsat, det vill säga om det maximala rekursionsdjupet som uppnås vid utvärdering av programmet i indatadatabasen kan begränsas av någon konstant. Problemet handlar med andra ord om huruvida Datalog-programmet kan skrivas om till ett icke-rekursivt Datalog-program. Lösningen på begränsningen av godtyckliga Datalog-program går inte att avgöra, men den kan göras beslutbar genom att begränsa oss till några fragment av Datalog [10] .
Dessa två rader definierar två fakta, det vill säga saker som alltid gäller:
förälder ( xerces , brooke ). förälder ( brooke , damokles ).Så här menar de: xerces är brookes förälder och brooke är damokles förälder. Namn skrivs med gemener eftersom strängar som börjar med en stor bokstav representerar variabler.