Datalog

Datalog
Språkklass Boolean , deklarativ
Framträdde i 1986  ( 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] .

Funktioner, begränsningar och tillägg

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.

Fragment

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.

Uttrycksförmåga

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] .

Exempel

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.

Anteckningar

  1. Huang, Green, and Loo, Datalog and Emerging applications , SIGMOD 2011 , UC Davis , < http://www.cs.ucdavis.edu/~green/papers/sigmod906t-huang.pdf > Arkiverad 22 oktober 2020 på Wayback Maskin . 
  2. Mei, Hongyuan; Qin, Guanghui; Xu, Minjie; Eisner, Jason (2020). "Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification". Procedurer för ICML 2020 . arXiv : 2006.16723 .
  3. Logik och databaser . - New York, 1978. - viii, 458 sidor sid. - ISBN 0-306-40060-X , 978-0-306-40060-5.
  4. S. Abiteboul. Grunderna för databaser . - Reading, Mass.: Addison-Wesley, 1995. - xviii, 685 sidor sid. - ISBN 0-201-53771-0 , 978-0-201-53771-0.
  5. Datalog (presentation) (nedlänk) . web.archive.org (25 mars 2017). Hämtad 20 augusti 2022. Arkiverad från originalet 25 mars 2017. 
  6. Bancilhon. "Magiska uppsättningar och andra konstiga sätt att implementera logikprogram" (PDF) . PT : UNL. Arkiverad från originalet (PDF) 2012-03-08. Utfasad parameter används |url-status=( hjälp )
  7. Pfenning, Frank; Schuermann, Carsten. "Tolv användarhandbok" . CMU. Arkiverad från originalet 2022-08-22 . Hämtad 2022-08-22 . Utfasad parameter används |deadlink=( hjälp )
  8. "Effektiv top-down beräkning av frågor under den välgrundade semantiken" (PDF) . Arkiverad (PDF) från originalet 2013-10-04 . Hämtad 2022-08-22 . Utfasad parameter används |deadlink=( hjälp )
  9. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data: 2004, Paris, Frankrike, 13-18 juni 2004. . - [New York]: Association for Computing Machinery, 2004. - xvii, 988 sidor sid. - ISBN 1-58113-859-8 , 978-1-58113-859-7.
  10. Gerd G Hillebrand, Paris C Kanellakis, Harry G Mairson, Moshe Y Vardi. Obeslutbara begränsningsproblem för dataloggprogram  //  The Journal of Logic Programming. — 1995-11. — Vol. 25 , iss. 2 . — S. 163–190 . - doi : 10.1016/0743-1066(95)00051-K . Arkiverad 7 maj 2021.