| Adat napló | |
|---|---|
| Nyelvóra | Logikai , deklaratív |
| Megjelent | 1986 |
| Típusrendszer | Gyenge |
| Dialektusok | Datomic , pyDatalog, Dyna stb. |
A Datalog egy deklaratív logikai programozási nyelv. Bár szintaktikailag úgy néz ki, mint a Prolog részhalmaza , a Datalog általában alulról felfelé építkező, nem felülről lefelé irányuló kifejezési felbontási modellt használ. Ez a különbség jelentős különbséghez vezet a Prolog viselkedésében és tulajdonságaiban. Gyakran használják deduktív adatbázisok lekérdezési nyelveként. Az elmúlt években a Datalog új felhasználási területeket talált az adatintegráció, az információ-kinyerés, a hálózatépítés, a programelemzés, a biztonság, a számítási felhő és a gépi tanulás területén [1] [2] .
Eredete a logikai programozás kezdetéig nyúlik vissza, de külön témaként 1977 körül kezdett kiemelkedni, amikor Herve Galler és Jack Minker szemináriumot szervezett a logikáról és az adatbázisokról [3] . David Mayer nevéhez fűződik a Datalog [4] kifejezés megalkotója .
A Prologtól eltérően a Datalog program utasításai tetszőleges sorrendben megadhatók. Sőt, a véges halmazokra vonatkozó Datalog lekérdezések garantáltan befejeződnek, ezért a Datalog nem rendelkezik cut utasítással a Prologban. Ez a Datalogot teljesen deklaratív nyelvvé teszi.
A Prologtól eltérően a Datalog:
A lekérdezések Datalog segítségével történő megoldásának eljárása elsőrendű logikán alapul , ezért helyes és teljes. A Datalog azonban nem Turing-teljes, ezért tartományspecifikus nyelvként használják, amely kihasználhatja a lekérdezések feloldására tervezett hatékony algoritmusokat. Valójában különféle módszereket javasoltak a lekérdezések hatékony végrehajtására, mint például a Magic Sets algoritmus [6] , a táblázatos logikai programozás [7] vagy az SLG felbontás [8] .
Néhány széles körben használt adatbázis-rendszer a Datalog számára kifejlesztett ötleteket és algoritmusokat tartalmaz. Például az SQL:1999 szabvány rekurzív lekérdezéseket tartalmaz, és a Magic Sets algoritmust (eredetileg a Datalog-lekérdezések gyorsabb kiértékelésére tervezték) az IBM DB2 implementálja . Ezenkívül a Datalog motorok olyan speciális adatbázisrendszerek mögött állnak, mint például az Intellidimension adatbázis a szemantikus webhez [9] . A Datalog számos kiterjesztésre került, például az összesítő függvények támogatására, az objektum-orientált programozás lehetővé tételére vagy a diszjunkciók mondatfejlécként történő engedélyezésére. Ezek a kiterjesztések jelentős hatással vannak a Datalog szemantika meghatározására és a Datalog értelmező egyes verzióinak megvalósítására.
Az adatnapló-programok használhatnak vagy nem tagadást a szabálytörzsekben: A tagadással rendelkező Datalog-programoknak gyakran rétegzett tagadásként kell használniuk, hogy biztosítsák a szemantika jól meghatározottságát. Az adatnapló programok használhatnak vagy nem egyenlőtlenségeket a változók között a szabálytörzsekben.
Egyes Datalog szintaxis töredékek vannak definiálva, például a következők (leginkább a legkevésbé korlátozott):
Egy másik korlátozás a rekurzió használatára vonatkozik: a nem rekurzív Datalog úgy van definiálva, hogy a Datalog programok definíciójában nem engedélyezi a rekurziót. Ez a Datalog-részlet ugyanolyan kifejező, mint az összefűzött lekérdezések, de a lekérdezések nem rekurzív adatnaplóként történő írása tömörebb lehet.
A Datalog kényszerproblémája abban rejlik, hogy a Datalog program korlátos-e, vagyis hogy a program kiértékelésekor elért maximális rekurziós mélység a bemeneti adatbázisban behatárolható-e valamilyen állandóval. Más szavakkal, a probléma abban rejlik, hogy a Datalog program átírható-e nem rekurzív Datalog programként. A tetszőleges Datalog programok korlátozásának megoldása eldönthetetlen, de eldönthetővé tehető, ha a Datalog egyes töredékeire korlátozzuk magunkat [10] .
Ez a két sor két tényt határoz meg, vagyis olyan dolgokat, amelyek mindig érvényesek:
szülő ( xerces , patak ). szülő ( brooke , damocles ).Íme, mit jelentenek: xerces a patak szülője, és patak a damoklész szülője. A neveket kisbetűvel írjuk, mert a nagybetűvel kezdődő karakterláncok változókat jelentenek.