Veri kaydı - Datalog

Datalog , sözdizimsel olarak Prolog'un bir alt kümesi olan bildirimsel bir mantık programlama dilidir . Genellikle tümdengelim veritabanları için bir sorgu dili olarak kullanılır . Son yıllarda Datalog, veri entegrasyonu , bilgi çıkarma , ağ oluşturma , program analizi , güvenlik , bulut bilişim ve makine öğreniminde yeni uygulamalar buldu .

Kökenleri mantık programlamanın başlangıcına kadar uzanır , ancak 1977'de Hervé Gallaire ve Jack Minker'in mantık ve veritabanları üzerine bir atölye çalışması düzenlemesiyle ayrı bir alan olarak öne çıktı . David Maier , Datalog terimini icat etmekle tanınır.

Özellikler, sınırlamalar ve uzantılar

Prolog'dan farklı olarak, bir Datalog programının ifadeleri herhangi bir sırada belirtilebilir. Ayrıca, sonlu kümelerdeki Datalog sorgularının sonlanması garantilidir , bu nedenle Datalog, Prolog'un kesme operatörüne sahip değildir . Bu, Datalog'u tamamen bildirimsel bir dil yapar .

Prolog'un aksine, Datalog

1. yüklemlerin argümanları olarak karmaşık terimlere izin vermez , örneğin, p (1, 2) kabul edilebilir ancak p (f (1), 2) değil,
2. olumsuzlama ve özyineleme kullanımına belirli tabakalaşma kısıtlamaları getirir ,
3. bir yan tümcenin başında görünen her değişkenin aynı zamanda yan tümcenin gövdesinde aritmetik olmayan bir pozitif (yani olumsuzlanmamış) değişmezde de görünmesini gerektirir ,
4. Bir yan tümcenin gövdesinde olumsuz bir değişmezde görünen her değişkenin, aynı zamanda yan tümcenin gövdesinde bazı olumlu değişmezlerde de görünmesini gerektirir.

Datalog ile sorgu değerlendirmesi birinci dereceden mantığa dayalıdır ve bu nedenle sağlam ve eksiksizdir . Ancak, Datalog tam Turing değildir ve bu nedenle , sorgu çözümü için geliştirilmiş verimli algoritmalardan yararlanabilen etki alanına özgü bir dil olarak kullanılır . Aslında, sorguları verimli bir şekilde gerçekleştirmek için örneğin Magic Sets algoritması, tablolu mantıksal programlama veya SLG çözünürlüğü gibi çeşitli yöntemler önerilmiştir.

Yaygın olarak kullanılan bazı veritabanı sistemleri, Datalog için geliştirilmiş fikirleri ve algoritmaları içerir. Örneğin, SQL: 1999 standardı içeren özyinelemeli sorguları IBM'in uygulanan ve (başlangıçta Datalog sorguları daha hızlı değerlendirilmesi için geliştirilen) Sihirli Setleri algoritması DB2 . Ayrıca, Datalog motorları, Intellidimension'ın semantik web veritabanı gibi özel veritabanı sistemlerinin arkasındadır .

Datalog'a, örneğin toplu işlevleri desteklemek , nesne yönelimli programlamaya izin vermek veya cümle başı olarak ayrımlara izin vermek için çeşitli uzantılar yapılmıştır . Bu uzantıların Datalog'un semantiğinin tanımı ve ilgili Datalog yorumlayıcısının uygulanması üzerinde önemli etkileri vardır.

Parça

Veri günlüğü programları kural gövdelerinde olumsuzlamayı kullanabilir veya kullanmayabilir: Olumsuzlamalı veri günlüğü programlarının, anlambilimin iyi tanımlandığından emin olmak için genellikle bunu tabakalı olumsuzlama olarak kullanmaları gerekir. Datalog programları, kural gövdelerindeki değişkenler arasındaki eşitsizlikleri kullanabilir veya kullanmayabilir .

Aşağıdaki gibi bazı sözdizimsel Datalog parçaları tanımlanmıştır (en kısıtlıdan en az kısıtlıya):

• kural gövdelerinin tek bir atomdan oluşması gereken doğrusal Datalog
• korumalı Datalog , burada her kural için, kural gövdelerinde meydana gelen tüm değişkenler, koruyucu atom adı verilen en az bir atomda birlikte yer almalıdır.
• sınır korumalı Datalog , burada her kural için, kural gövdesi ve kural başlığı ( sınır değişkenleri olarak adlandırılır ) arasında paylaşılan tüm değişkenlerin tümü bir koruyucu atomda birlikte yer almalıdır.

Diğer bir kısıtlama özyineleme kullanımı ile ilgilidir: özyinelemeli olmayan Datalog , Datalog programlarının tanımında özyinelemeye izin verilmeyerek tanımlanır. Datalog'un bu parçası, birleşik sorguların birleşimleri kadar anlamlıdır, ancak sorguları özyinelemeli olmayan Datalog olarak yazmak daha kısa olabilir.

dışavurumculuk

Sınırlılık sorun Datalog için, bu olup olmadığını, bir Datalog programı verilen sorar sınırlanan bir sabit ile sınırlı olabilir, bir giriş veri tabanında programı değerlendirirken, yani, maksimum yineleme derinliği ulaşmıştır. Başka bir deyişle, bu soru Datalog programının özyinelemeli olmayan bir Datalog programı olarak yeniden yazılabileceğini sorar. Rastgele Datalog programlarında sınırlılık probleminin çözümü kararlaştırılamaz , ancak Datalog'un bazı parçalarıyla sınırlandırılarak karar verilebilir hale getirilebilir.

Örnek

Bu iki satır, iki gerçeği , yani her zaman geçerli olan şeyleri tanımlar :

parent(xerces, brooke).
parent(brooke, damocles).

Demek istedikleri şudur : xerces, brooke'un ebeveynidir ve brooke, democles'in ebeveynidir . İsimler küçük harfle yazılır çünkü büyük harfle başlayan diziler değişkenleri temsil eder.

Bu iki satır , yeni gerçeklerin bilinen gerçeklerden nasıl çıkarılabileceğini tanımlayan kuralları tanımlar.

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

anlam:

• X, Y'nin ebeveyniyse, X Y'nin atasıdır.
• X, bazı Z'nin ebeveyniyse ve Z, Y'nin atasıysa, X Y'nin atasıdır.

Bu satır bir sorgudur:

?- ancestor(xerces, X).

Şunu sorar: xerces'in atası olduğu tüm X'ler kimlerdir? Yukarıda açıklanan gerçekleri ve kuralları içeren bir Datalog sistemine karşı oluşturulduğunda brooke ve democles döndürür .

Kurallar hakkında daha fazla bilgi: bir kuralın ortasında bir :- sembolü vardır: Bu sembolün solundaki kısım kuralın başıdır , sağdaki kısım ise gövdedir . Bir kural şöyle okunur: <body> öğesinin doğru olduğu biliniyorsa, <head> öğesinin doğru olduğu bilinir . Örnekte, biz kim bilmiyorum: kurallarda Büyük harfler değişkenler için durmak X veya Y , ancak bazıları X'in bazı atası Y eğer X'in o üstüdür Y . Sorgu çağrısının sonucunu hesaplamak için tümcelerin sırasına bağlı olan Prolog'un aksine, tümcelerin sıralaması Datalog'da önemsizdir.

Datalog, uzantısal yüklem sembolleri (olgularla tanımlanır) ve kasıtlı yüklem sembolleri (kurallarla tanımlanır ) arasında ayrım yapar . Yukarıdaki örnekte ancestorbir yönelim yüklem sembolüdür ve parentgenişlemelidir. Tahminler aynı zamanda gerçekler ve kurallar tarafından da tanımlanabilir ve bu nedenle ne tamamen uzamsal ne de yönelimsel olabilir, ancak herhangi bir Datalog programı, yinelenen rollere sahip bu tür yüklem sembolleri olmadan eşdeğer bir programa yeniden yazılabilir.

Sözdizimi

Bir Datalog programı, bir gerçekler ve kurallar listesinden oluşur ( Horn cümleleri ). Eğer sabit ve değişken ikisidir sayılabilen sırasıyla sabitler ve değişkenlerin setleri ve ilişki bir sayılabilir kümesidir yüklem sembolleri , ardından aşağıdaki dilbilgisi bir Datalog programının yapısını ifade eder:

<program> ::= <fact> <program> | <rule> <program> | ɛ
<fact> ::=  <relation> "(" <constant-list> ")." 
<rule> ::= <atom> ":-" <atom-list> "."
<atom> ::= <relation> "(" <term-list> ")"
<atom-list> ::= <atom> | <atom> "," <atom-list>
<term> ::= <constant> | <variable>
<term-list> ::= <term> | <term> "," <term-list>
<constant-list> ::= <constant> | <constant> "," <constant-list>

Atomlar ayrıca literatürde değişmez olarak adlandırılır .

anlambilim

Datalog programlarının semantiğine ilişkin yaygın olarak kullanılan üç yaklaşım vardır: model-teorik , sabit-nokta ve ispat-teorik .

Model Teorisi

Bir gerçek veya kuralı denir zemin onun alt terimleri tüm sabitleri ise. Temel kural R ₁ , eğer R ₁ , R _{2 '} deki tüm değişkenler için sabitlerin ikamesinin sonucuysa , başka bir R ₂ kuralının temel örneğidir .

Herbrand baz (bkz Herbrand evreni bir Datalog programı) programında görünen sabitleri ile yapılabilir tüm zemin atomlu kümesidir. Bir yorumlama ( veritabanı örneği olarak da bilinir ), Herbrand tabanının bir alt kümesidir. Zemin atomu, I'in bir elementiyse, I yorumunda doğrudur . Yorum I'de bir kural doğrudur , eğer o kuralın her bir temel örneği için, gövdedeki tüm maddeler I'de doğruysa , o zaman kuralın başı I'de de doğrudur .

Bir model, bir Datalog programı P bir yorumudur ben bir P tüm zemin gerçekleri içeren P ve kurallarının tüm kılan P gerçek I . Model-teorik anlambilim, bir Datalog programının anlamının onun minimal modeli (eşdeğeri, tüm modellerinin kesişimi) olduğunu belirtir.

Sabit Nokta Semantiği

Let I bir Datalog programı yorumların kümesi P (yani I = P ( lH ), burada H Herbrand nokta P ve P olan Powerset operatörün bir ilk tanımlamak için kullanılır. I için I , aşağıdaki gibi: her bir zemin Örneğin her kural P vücuttaki her fıkra giriş yorumlanmasında ise, çıkış yorumlama zemin örneğinin başını ekleyin. Sonra bu haritanın sabit nokta programının asgari modelidir. fixpoint semantik bir önermek minimal modeli hesaplamak için algoritma: Programdaki temel gerçekler kümesiyle başlayın, ardından bir sabitleme noktasına ulaşılana kadar kuralların sonuçlarını tekrar tekrar ekleyin.

Değerlendirme

Farklı performans özelliklerine sahip bir Datalog programını değerlendirmenin birçok farklı yolu vardır.

Aşağıdan Yukarıya Değerlendirme Stratejileri

Aşağıdan yukarıya değerlendirme stratejileri, programdaki gerçeklerle başlar ve belirli bir amaç veya sorgu oluşturulana veya programın eksiksiz minimal modeli üretilene kadar kuralları tekrar tekrar uygular.

Naif Değerlendirme

Naif değerlendirme , Datalog programları için sabit nokta semantiğini yansıtır . Naif değerlendirme, programdaki gerçeklere göre başlatılan bir dizi "bilinen gerçekler" kullanır. Programdaki her kuralın tüm temel örneklerini tekrar tekrar numaralandırarak ilerler. Temel örneğin gövdesindeki her atom bilinen gerçekler kümesindeyse, o zaman baş atom bilinen gerçekler kümesine eklenir. Bu süreç, sabit bir noktaya ulaşılana kadar tekrarlanır ve daha fazla gerçek çıkarılamaz. Naif değerlendirme, programın tüm minimal modelini üretir.

Datalog uygulayan sistemler

Datalog'u temel alan veya bir Datalog yorumlayıcısı sağlayan sistemlerin kısa bir listesi:

Özgür yazılım/açık kaynak

Özgür olmayan yazılım

• Datomic , yeni bulut mimarileri üzerinde çalışan, ölçeklenebilir, esnek ve akıllı uygulamaları etkinleştirmek için tasarlanmış dağıtılmış bir veritabanıdır. Sorgu dili olarak Datalog'u kullanır.
• FoundationDB , kullanımıyla ilgili bir öğretici ile pyDatalog için ücretsiz bir veritabanı bağlaması sağlar.
• Leapsight Semantic Dataspace (LSD), yüksek kullanılabilirlik, hata toleransı, operasyonel basitlik ve ölçeklenebilirlik sunan dağıtılmış tümdengelimli bir veritabanıdır. LSD, sorgulama ve akıl yürütme için Leaplog'u (bir Datalog uygulaması) kullanır ve Leapsight tarafından oluşturulmuştur.
• LogicBlox , web tabanlı perakende planlama ve sigorta uygulamaları için kullanılan Datalog'un ticari bir uygulamasıdır.
• Profium Sense, Java ile yazılmış yerel bir RDF uyumlu grafik veritabanıdır . Kullanıcı tanımlı kuralların Datalog değerlendirme desteğini sağlar.
• .QL , güvenlik açıklarını tespit etmek için kaynak kodunu analiz etmek için Semmle tarafından oluşturulan Datalog'un ticari nesne yönelimli bir çeşididir.
• SecPAL , Microsoft Research tarafından geliştirilen bir güvenlik ilkesi dilidir .
• Stardog, Java'da uygulanan bir grafik veritabanıdır . Veri günlüğü değerlendirmesi de dahil olmak üzere kapsamlı akıl yürütme yetenekleri sağlayan RDF ve tüm OWL 2 profilleri için destek sağlar .
• StrixDB: ticari bir RDF grafik deposu, Lua API ve Datalog çıkarım yetenekleriyle uyumlu SPARQL . httpd ( Apache HTTP Sunucusu ) modülü olarak veya bağımsız olarak kullanılabilir (beta sürümleri Perl Sanatsal Lisans 2.0 kapsamında olmasına rağmen).

Ayrıca bakınız

• Cevap seti programlama
• birleşik sorgu
• DLV
• flix
• SWRL
• Demet üreten bağımlılık (TGD), bir dil bütünlüğü kısıtlamaları ile ilişkisel veri tabanları Datalog benzer sözdizimi

Referanslar

bibliyografya

daha fazla okuma

• Gradel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maarten, Marx; Spencer, Joel ; Vardi, Moşe Y .; Venema, Yde; Weinstein, Scott (2007), Sonlu model teorisi ve uygulamaları , Teorik Bilgisayar Biliminde Metinler. Bir EATCS Serisi, Berlin: Springer-Verlag , ISBN 978-3-540-00428-8, Zbl  1133.03001