डेटालॉग

From Vigyanwiki
Revision as of 10:50, 15 May 2023 by alpha>Indicwiki (Created page with "{{Short description|Declarative logic programming language}} {{Infobox programming language | paradigm = Logic, Declarative |...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
डेटालॉग
ParadigmLogic, Declarative
परिवारProlog
पहली प्रस्तुति1986; 39 years ago (1986)
टाइपिंग अनुशासनWeak
Dialects
Datomic, .QL, Soufflé, etc.
Influenced by
Prolog

Datalog एक घोषणात्मक प्रोग्रामिंग तर्क प्रोग्रामिंग लैंग्वेज है। हालांकि यह सिंटैक्टिक रूप से प्रोलॉग का सबसेट है, लेकिन सूचीपत्र आम तौर पर टॉप-डाउन मूल्यांकन मॉडल के बजाय नीचे-ऊपर का उपयोग करता है। यह अंतर प्रोलॉग से काफी भिन्न व्यवहार और गुण उत्पन्न करता है। यह अक्सर कटौतीत्मक डेटाबेस के लिए पूछताछ भाषा के रूप में उपयोग किया जाता है। Datalog को डेटा एकीकरण, संगणक संजाल , कार्यक्रम विश्लेषण , और बहुत कुछ में समस्याओं के लिए लागू किया गया है।

उदाहरण

एक सूची कार्यक्रम में तथ्य शामिल होते हैं, जो ऐसे कथन होते हैं जिन्हें सत्य माना जाता है, और नियम, जो कहते हैं कि ज्ञात तथ्यों से नए तथ्यों को कैसे निकाला जाए। उदाहरण के लिए, यहां दो तथ्य दिए गए हैं, जिसका अर्थ है कि जेर्सेस ब्रुक का जनक है और ब्रुक डैमोकल्स का जनक है: 

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

नाम लोअरकेस में लिखे गए हैं क्योंकि अपरकेस अक्षर से शुरू होने वाले तार वेरिएबल्स के लिए खड़े होते हैं। यहाँ दो नियम हैं: 

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

:- e> प्रतीक को इस प्रकार पढ़ा जाता है मानो , और अल्पविराम को पढ़ा जाता है और , इसलिए इन नियमों का अर्थ है:
  • X, Y का पूर्वज है यदि X, Y का माता-पिता है।
  • X, Y का पूर्वज है यदि X किसी Z का माता-पिता है, और Z, Y का पूर्वज है।

एक कार्यक्रम का अर्थ उन सभी तथ्यों के समूह के रूप में परिभाषित किया जाता है, जिन्हें प्रारंभिक तथ्यों और नियमों का उपयोग करके निकाला जा सकता है। इस कार्यक्रम का अर्थ निम्नलिखित तथ्यों द्वारा दिया गया है: 

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

कुछ Datalog कार्यान्वयन सभी संभावित तथ्यों को नहीं निकालते हैं, बल्कि प्रश्नों का उत्तर देते हैं: 

?- ancestor(xerces, X).

यह क्वेरी पूछती है: वे सभी X कौन हैं जो xerces के पूर्वज हैं? इस उदाहरण के लिए, यह ब्रुक और डैमोकल्स लौटाएगा।

संबंध का डेटाबेस से तुलना

Datalog का गैर-पुनरावर्ती सबसेट संबंधपरक डेटाबेस, जैसे SQL के लिए क्वेरी भाषाओं से निकटता से संबंधित है। Datalog, संबंधपरक बीजगणित और SQL अवधारणाओं के बीच निम्न तालिका मानचित्र:

Datalog Relational algebra SQL
Relation Relation Table
Fact Tuple Row
Rule n/a Materialized view
Query Select Query

अधिक औपचारिक रूप से, गैर-पुनरावर्ती Datalog संयोजक प्रश्नों के संघों, या समकक्ष, निषेध-मुक्त संबंधपरक बीजगणित के सटीक रूप से मेल खाता है।

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |
Schematic translation from non-recursive Datalog into SQL
s(x, y).
t(y).
r(A, B) :- s(A, B), t(B).

CREATE TABLE s (
  z0 TEXT NONNULL,
  z1 TEXT NONNULL,
  PRIMARY KEY (z0, z1)
);
CREATE TABLE t (
  z0 TEXT NONNULL PRIMARY KEY
);
INSERT INTO s VALUES ('x', 'y');
INSERT INTO t VALUES ('y');
CREATE VIEW r AS
SELECT s.z0, s.z1
FROM s, t
WHERE s.z1 = t.z0;

सिंटेक्स

एक सूची कार्यक्रम में नियमों की एक सूची होती है (हॉर्न खंड)।[1] यदि निरंतर और चर क्रमशः स्थिरांक और चर के दो गणनीय सेट सेट हैं और संबंध विधेय चर का एक गणनीय सेट है, तो निम्नलिखित बीएनएफ व्याकरण एक डेटालॉग प्रोग्राम की संरचना को व्यक्त करता है: 

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

परमाणु भी कहा जाता है literals. के बाईं ओर परमाणु :- प्रतीक कहा जाता है head नियम; दाईं ओर परमाणु हैं body. प्रत्येक डेटालॉग प्रोग्राम को इस शर्त को पूरा करना चाहिए कि नियम के शीर्ष में दिखाई देने वाला प्रत्येक चर शरीर में भी प्रकट होता है (इस स्थिति को कभी-कभी कहा जाता है range restriction).[1][2] वेरिएबल नामों के लिए दो सामान्य परंपराएं हैं: वेरिएबल्स को बड़ा करना, या उन्हें एक प्रश्न चिह्न के साथ उपसर्ग करना ?.[3] ध्यान दें कि इस परिभाषा के तहत, Datalog करता है not निषेध और न ही समुच्चय शामिल करें; देखना § Extensions उन निर्माणों के बारे में अधिक जानकारी के लिए।

खाली शरीर वाले नियम कहलाते हैं facts. उदाहरण के लिए, निम्नलिखित नियम एक तथ्य है: 

r(x) :- .

तथ्यों के समुच्चय को कहा जाता है extensional database या EDB Datalog कार्यक्रम के। डाटालॉग प्रोग्राम का मूल्यांकन करके गणना किए गए टुपल्स के सेट को कहा जाता है intensional database या IDB.

सिंथेटिक चीनी

लॉजिक प्रोग्रामिंग के कई कार्यान्वयन उपरोक्त व्याकरण का विस्तार करते हैं ताकि बिना तथ्यों को लिखने की अनुमति मिल सके :-, जैसे इतना: 

r(x).

कुछ 0-एरी संबंधों को कोष्ठक के बिना लिखने की अनुमति भी देते हैं, जैसे: 

p :- q.

ये केवल संक्षिप्त रूप हैं (सिंटैक्टिक चीनी); कार्यक्रम के शब्दार्थ पर उनका कोई प्रभाव नहीं है।

शब्दार्थ

Main article: Syntax and semantics of logic programming
Herbrand universe, base, and model of a Datalog program

Program: 

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).
Herbrand universe: x, y, z
Herbrand base: edge(x, x), edge(x, y), ..., edge(z, z), path(x, x), ..., path(z, z)
Herbrand model: edge(x, y), edge(y, z), path(x, y), path(y, z), path(x, z)

Datalog प्रोग्राम के शब्दार्थ के लिए तीन व्यापक रूप से उपयोग किए जाने वाले दृष्टिकोण हैं: मॉडल सिद्धांत | मॉडल-सैद्धांतिक, निश्चित बिंदु (गणित) | निश्चित-बिंदु, और प्रूफ-सैद्धांतिक शब्दार्थ | प्रूफ-सैद्धांतिक। इन तीन दृष्टिकोणों को समकक्ष सिद्ध किया जा सकता है।[4] परमाणु कहा जाता है ground यदि इसका कोई उपपद चर नहीं है। सहज रूप से, प्रत्येक शब्दार्थ एक कार्यक्रम के अर्थ को परिभाषित करता है, जो कि सभी जमीनी परमाणुओं का समूह होता है, जिसे तथ्यों से शुरू करके, कार्यक्रम के नियमों से घटाया जा सकता है।

मॉडल सैद्धांतिक

एक नियम को ग्राउंड कहा जाता है यदि इसके सभी परमाणु (सिर और शरीर) ग्राउंड होते हैं। एक बुनियादी नियम आर1 दूसरे नियम R का एक जमीनी उदाहरण है2 अगर आर1 आर में सभी चर के लिए स्थिरांक के प्रतिस्थापन (तर्क) का परिणाम है2. डाटालॉग प्रोग्राम का हरब्रांड बेस सभी जमीनी परमाणुओं का सेट है जो प्रोग्राम में दिखाई देने वाले स्थिरांक के साथ बनाया जा सकता है। Herbrand model}el एक डेटालॉग प्रोग्राम का सबसे छोटा उपसमुच्चय है, जैसे कि कार्यक्रम में प्रत्येक नियम के प्रत्येक आधार उदाहरण के लिए, यदि नियम के शरीर में परमाणु सेट में हैं, तो सिर भी है।[5] मॉडल-सैद्धांतिक शब्दार्थ कार्यक्रम के अर्थ के रूप में न्यूनतम हेरब्रांड मॉडल को परिभाषित करता है।

फिक्स्ड-पॉइंट

होने देना I कार्यक्रम पी के हरब्रांड आधार का सत्ता स्थापित हो। पी के लिए तत्काल परिणाम ऑपरेटर एक मानचित्र है T से I को I जो एक ही चरण में कार्यक्रम के नियमों से प्राप्त किए जा सकने वाले सभी नए जमीनी परमाणुओं को जोड़ता है। कम से कम निश्चित बिंदु शब्दार्थ कम से कम निश्चित बिंदु को परिभाषित करता है T कार्यक्रम का अर्थ होना; यह न्यूनतम हरब्रांड मॉडल के साथ मेल खाता है।[6]

fixpoint सिमेंटिक्स न्यूनतम मॉडल की गणना के लिए एक एल्गोरिथ्म का सुझाव देता है: कार्यक्रम में जमीनी तथ्यों के सेट के साथ शुरू करें, फिर एक निश्चित बिंदु तक पहुंचने तक नियमों के परिणामों को बार-बार जोड़ें। इस एल्गोरिद्म को #भोला मूल्यांकन|भोला मूल्यांकन कहा जाता है।

प्रमाण-सैद्धांतिक

ग्राउंड एटम की व्युत्पत्ति दर्शाने वाला प्रूफ ट्री path(x, z) कार्यक्रम से 
edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

प्रूफ-सैद्धांतिक शब्दार्थ एक डेटालॉग प्रोग्राम के अर्थ को संबंधित प्रूफ ट्री के साथ तथ्यों के सेट के रूप में परिभाषित करता है। सहज रूप से, एक प्रूफ ट्री दिखाता है कि किसी प्रोग्राम के तथ्यों और नियमों से तथ्य कैसे प्राप्त किया जाए।

किसी को यह जानने में दिलचस्पी हो सकती है कि क्या एक विशेष जमीनी परमाणु एक सूची कार्यक्रम के न्यूनतम हरब्रांड मॉडल में दिखाई देता है या नहीं, शायद बाकी मॉडल के बारे में ज्यादा परवाह किए बिना। ऊपर वर्णित प्रूफ ट्री का टॉप-डाउन रीडिंग ऐसे प्रश्नों के परिणामों की गणना के लिए एक एल्गोरिथ्म का सुझाव देता है। यह पठन एसएलडी संकल्प एल्गोरिदम को सूचित करता है, जो प्रोलॉग के मूल्यांकन के लिए आधार बनाता है।

मूल्यांकन

अलग-अलग प्रदर्शन विशेषताओं के साथ, एक सूची कार्यक्रम का मूल्यांकन करने के कई अलग-अलग तरीके हैं।

बॉटम-अप मूल्यांकन रणनीतियाँ

बॉटम-अप मूल्यांकन रणनीतियाँ कार्यक्रम में तथ्यों के साथ शुरू होती हैं और नियमों को बार-बार लागू करती हैं जब तक कि कोई लक्ष्य या प्रश्न स्थापित नहीं हो जाता है, या जब तक कार्यक्रम का पूर्ण न्यूनतम मॉडल तैयार नहीं हो जाता।

भोला मूल्यांकन

भोले-भाले मूल्यांकन में #Fixpoint Semantics को Datalog प्रोग्राम के लिए प्रतिबिम्बित करता है। भोली मूल्यांकन ज्ञात तथ्यों के एक सेट का उपयोग करता है, जिसे कार्यक्रम में तथ्यों के लिए आरंभ किया जाता है। यह कार्यक्रम में प्रत्येक नियम के सभी जमीनी उदाहरणों की बार-बार गणना करके आगे बढ़ता है। यदि जमीनी उदाहरण के शरीर में प्रत्येक परमाणु ज्ञात तथ्यों के समूह में है, तो शीर्ष परमाणु को ज्ञात तथ्यों के समूह में जोड़ा जाता है। यह प्रक्रिया एक निश्चित बिंदु तक पहुंचने तक दोहराई जाती है, और कोई और तथ्य नहीं निकाला जा सकता है। सहज मूल्यांकन कार्यक्रम के संपूर्ण न्यूनतम मॉडल का निर्माण करता है।[7]

अर्ध-भोला मूल्यांकन

अर्ध-भोले मूल्यांकन एक नीचे से ऊपर की मूल्यांकन रणनीति है जो सहज मूल्यांकन की तुलना में विषम रूप से तेज हो सकती है।[8]


प्रदर्शन विचार

Argonne National Laboratory में थीटा सुपरकंप्यूटर पर एक समानांतर Datalog इंजन का मूल्यांकन किया गया था।[9]

भोली और अर्ध-भोली मूल्यांकन दोनों एक निश्चित बिंदु तक पहुंचने तक ज्ञात तथ्यों के एक सेट पर बार-बार लागू करके पुनरावर्ती डेटालॉग नियमों का मूल्यांकन करते हैं। प्रत्येक पुनरावृत्ति में, नियम केवल एक चरण के लिए चलाए जाते हैं, अर्थात गैर-पुनरावर्ती रूप से। जैसा कि उल्लेख किया गया है # तुलना संबंधपरक डेटाबेस के लिए, प्रत्येक गैर-पुनरावर्ती डेटालॉग नियम एक संयुग्मन क्वेरी के लिए सटीक रूप से मेल खाता है। इसलिए, संयुग्मी प्रश्नों को गति देने के लिए उपयोग की जाने वाली डेटाबेस सिद्धांत की कई तकनीकें डेटालॉग के बॉटम-अप मूल्यांकन पर लागू होती हैं, जैसे कि

इस तरह की कई तकनीकों को आधुनिक बॉटम-अप डेटालॉग इंजनों में कार्यान्वित किया जाता है जैसे सूफले (प्रोग्रामिंग लैंग्वेज) | सूफले। कुछ Datalog इंजन सीधे SQL डेटाबेस को एकीकृत करते हैं।[13] Datalog का बॉटम-अप मूल्यांकन भी समानांतर कंप्यूटिंग के लिए उत्तरदायी है। समानांतर डेटालॉग इंजन आम तौर पर दो प्रतिमानों में विभाजित होते हैं:

  • साझा-मेमोरी, मल्टी-कोर सेटिंग में, Datalog इंजन एक नोड पर निष्पादित होते हैं। लॉक (कंप्यूटर विज्ञान) या लॉक-मुक्त डेटा संरचनाओं का उपयोग करके थ्रेड्स के बीच समन्वय प्राप्त किया जा सकता है। उदाहरणों में OpenMP का उपयोग करने वाले Datalog इंजन शामिल हैं।[14]
  • साझा-कुछ नहीं वास्तुकला |शेयर्ड-नथिंग सेटिंग में, डाटालॉग इंजन नोड्स के कंप्यूटर क्लस्टर पर निष्पादित होते हैं। ऐसे इंजन आम तौर पर हैश फंकशन के आधार पर अलग-अलग उपसमुच्चय में संबंधों को विभाजित करके संचालित करते हैं, प्रत्येक नोड पर संगणना (जुड़ना) करते हैं, और फिर नेटवर्क पर नव-निर्मित ट्यूपल्स का आदान-प्रदान करते हैं।[15] उदाहरणों में संदेश पासिंग इंटरफ़ेस पर आधारित डेटालॉग इंजन शामिल हैं,[16] अपाचे हडूप,[17] और अपाचे स्पार्क।[18]


टॉप-डाउन मूल्यांकन रणनीतियाँ

एसएलडी रिजॉल्यूशन डाटालॉग प्रोग्राम के लिए मजबूत और पूर्ण है।

जादू सेट

टॉप-डाउन मूल्यांकन रणनीतियाँ एक प्रश्न या लक्ष्य से शुरू होती हैं। बॉटम-अप मूल्यांकन रणनीतियाँ पूरे न्यूनतम मॉडल की गणना करके और उसके विरुद्ध क्वेरी का मिलान करके प्रश्नों का उत्तर दे सकती हैं, लेकिन यह अक्षम हो सकता है यदि उत्तर केवल पूरे मॉडल के एक छोटे उपसमुच्चय पर निर्भर करता है। जादू सेट एल्गोरिदम एक डेटालॉग प्रोग्राम और एक क्वेरी लेता है, और एक अधिक कुशल प्रोग्राम तैयार करता है जो नीचे-ऊपर मूल्यांकन का उपयोग करते हुए क्वेरी के समान उत्तर की गणना करता है।[19] मैजिक सेट एल्गोरिथम के एक प्रकार को ऐसे प्रोग्राम बनाने के लिए दिखाया गया है, जो #अर्ध-भोले मूल्यांकन|अर्द्ध-भोले मूल्यांकन का उपयोग करके मूल्यांकन किए जाने पर, टॉप-डाउन मूल्यांकन के रूप में कुशल हैं।[20]


जटिलता

डेटालॉग मूल्यांकन का निर्णय समस्या सूत्रीकरण इस प्रकार है: एक डेटालॉग प्रोग्राम दिया गया P तथ्यों के एक सेट में विभाजित (ईडीबी) E और नियमों का एक सेट R, और एक व्याख्या A, है A के न्यूनतम मॉडल में P? इस सूत्रीकरण में, सूची कार्यक्रमों के मूल्यांकन की कम्प्यूटेशनल जटिलता के तीन रूप हैं:[21]

  • data complexity}ty निर्णय समस्या की जटिलता है जब A और E इनपुट हैं और R निश्चित है।
  • वह program complexity निर्णय समस्या की जटिलता है जब A और R इनपुट हैं और E निश्चित है।
  • वह combined complexity निर्णय समस्या की जटिलता है जब A, E, और R इनपुट हैं।

डेटा जटिलता के संबंध में, Datalog के लिए निर्णय समस्या P-पूर्ण है। कार्यक्रम की जटिलता के संबंध में, निर्णय समस्या EXPTIME-पूर्ण है। विशेष रूप से, सूची कार्यक्रमों का मूल्यांकन हमेशा समाप्त हो जाता है; डेटालॉग ट्यूरिंग पूर्णता नहीं है | ट्यूरिंग-पूर्ण।

Datalog के कुछ एक्सटेंशन इन जटिलता सीमाओं को संरक्षित नहीं करते हैं। कुछ Datalog इंजनों में लागू किए गए एक्सटेंशन #Datalog इंजन, जैसे कि बीजगणितीय डेटा प्रकार, परिणामी भाषा को ट्यूरिंग-पूर्ण भी बना सकते हैं।

एक्सटेंशन

Datalog में कई एक्सटेंशन किए गए हैं, उदाहरण के लिए, ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग की अनुमति देने के लिए, नकारात्मकता, कुल कार्यों, असमानताओं का समर्थन करने के लिए, या खंड (तर्क) के प्रमुखों के रूप में संयोजनों को अनुमति देने के लिए। इन विस्तारों का भाषा के शब्दार्थ और संबंधित दुभाषिया के कार्यान्वयन पर महत्वपूर्ण प्रभाव पड़ता है।

Datalog Prolog, disjunctive Datalog, उत्तर सेट प्रोग्रामिंग, DatalogZ|Datalog का एक सिंटैक्टिक उपसमुच्चय हैℤ, और बाधा तर्क प्रोग्रामिंग। जब एक उत्तर सेट प्रोग्राम के रूप में मूल्यांकन किया जाता है, तो एक डेटालॉग प्रोग्राम एक एकल उत्तर सेट उत्पन्न करता है, जो वास्तव में इसका न्यूनतम मॉडल है।[22] Datalog के कई कार्यान्वयन अतिरिक्त सुविधाओं के साथ Datalog का विस्तार करते हैं; देखना § Datalog engines अधिक जानकारी के लिए।

एकत्रीकरण

एग्रीगेट फ़ंक्शन का समर्थन करने के लिए डेटालॉग को बढ़ाया जा सकता है।[23] एकत्रीकरण को लागू करने वाले उल्लेखनीय डेलालॉग इंजनों में शामिल हैं:

निषेध

Further information: Syntax and semantics of logic programming § Extending Datalog with negation

Datalog में निषेध जोड़ने से इसके शब्दार्थ जटिल हो जाते हैं, जिससे मूल्यांकन के लिए पूरी नई भाषाएँ और रणनीतियाँ बन जाती हैं। उदाहरण के लिए, वह भाषा जो स्थिर मॉडल शब्दार्थ के साथ निषेध को जोड़ने का परिणाम है, बिल्कुल उत्तर सेट प्रोग्रामिंग है।

स्तरीकरण (गणित)#गणितीय तर्क में नकार को इसके मॉडल-सैद्धांतिक और निश्चित बिंदु शब्दार्थ को बनाए रखते हुए Datalog में जोड़ा जा सकता है। स्तरीकृत निषेध को लागू करने वाले उल्लेखनीय डेलालॉग इंजनों में शामिल हैं:

  • लॉजिकब्लॉक्स[25]
  • सूफले (प्रोग्रामिंग भाषा) | सूफले

प्रोलॉग से तुलना

प्रोलॉग के विपरीत, एक सूची कार्यक्रम के बयान किसी भी क्रम में बताए जा सकते हैं। Datalog में Prolog's Cut (तर्क प्रोग्रामिंग) ऑपरेटर नहीं है। यह Datalog को पूरी तरह से घोषणात्मक भाषा बनाता है।

प्रोलॉग के विपरीत, Datalog

  • जटिल शब्दों को विधेय (तर्क) के तर्कों के रूप में अस्वीकार करता है, उदाहरण के लिए, p(x, y) स्वीकार्य है लेकिन नहीं p(f(x), y),
  • निषेध अस्वीकार करता है,
  • के लिए आवश्यक है कि खंड (तर्क) के शीर्ष में दिखाई देने वाला प्रत्येक चर खंड के शरीर में एक शाब्दिक (गणितीय तर्क) में भी दिखाई दे।

यह लेख मुख्य रूप से बिना निषेध के Datalog से संबंधित है (यह भी देखें Syntax and semantics of logic programming § Extending Datalog with negation). हालाँकि, स्तरीकृत निषेध, Datalog के लिए एक सामान्य जोड़ है; निम्न सूची स्तरीकृत निषेध के साथ प्रोलॉग के साथ डेटालॉग के विपरीत है। स्तरीकृत निषेध के साथ डेटालॉग

  • विधेय (तर्क) के तर्कों के रूप में जटिल शब्दों को भी अस्वीकार करता है,
  • के लिए आवश्यक है कि खंड (तर्क) के शीर्ष में दिखाई देने वाला प्रत्येक चर भी खंड के शरीर में एक सकारात्मक (अर्थात, अस्वीकृत नहीं) परमाणु में दिखाई दे,
  • की आवश्यकता है कि खंड के शरीर में नकारात्मक शाब्दिक में दिखाई देने वाला प्रत्येक चर खंड के शरीर में कुछ सकारात्मक अक्षर में भी दिखाई दे।[26][unreliable source?]

== अभिव्यक्ति == boundedness problem}em के लिए Datalog पूछता है, एक Datalog प्रोग्राम दिया गया है, चाहे वह हो bounded, यानी, एक इनपुट डेटाबेस पर प्रोग्राम का मूल्यांकन करते समय अधिकतम रिकर्सन गहराई तक पहुंचा जा सकता है, जिसे कुछ स्थिरता से बांधा जा सकता है। दूसरे शब्दों में, यह प्रश्न पूछता है कि क्या Datalog प्रोग्राम को एक गैर-आवर्ती Datalog प्रोग्राम के रूप में फिर से लिखा जा सकता है। मनमाना Datalog प्रोग्राम पर बाउंडनेस की समस्या का समाधान करना अनिर्णीत समस्या है,[27] लेकिन इसे Datalog के कुछ अंशों तक सीमित करके निर्णायक बनाया जा सकता है।

डेटा लॉग इंजन

Further information: Draft:List of Datalog engines

सिस्टम जो Datalog से प्रेरित भाषाओं को लागू करता है, चाहे वह संकलक , दुभाषिया (कंप्यूटिंग) , पुस्तकालय (कम्प्यूटिंग) , या एंबेडेड DSL, के रूप में जाना जाता है Datalog engines. Datalog इंजन अक्सर Datalog के एक्सटेंशन को लागू करते हैं, इसे अतिरिक्त डेटा प्रकार, विदेशी फ़ंक्शन इंटरफ़ेस या उपयोगकर्ता-परिभाषित जाली (ऑर्डर) के लिए समर्थन के साथ विस्तारित करते हैं। इस तरह के एक्सटेंशन डायवर्जेंस (कंप्यूटर साइंस) | नॉन-टर्मिनेटिंग या अन्यथा खराब परिभाषित प्रोग्राम लिखने की अनुमति दे सकते हैं।

उपयोग और प्रभाव

Datalog अपनी अभिव्यक्ति में काफी सीमित है। यह ट्यूरिंग पूर्णता नहीं है | ट्यूरिंग-पूर्ण, और इसमें बुनियादी डेटा प्रकार जैसे इंटेगर (कंप्यूटर विज्ञान) या स्ट्रिंग (कंप्यूटर विज्ञान) शामिल नहीं है। यह पारसीमोनी एक सैद्धांतिक दृष्टिकोण से अपील कर रहा है, लेकिन इसका मतलब है कि Datalog per se शायद ही कभी एक प्रोग्रामिंग भाषा के रूप में उपयोग किया जाता है।[28] अधिकांश #Datalog इंजन, Datalog के पर्याप्त विस्तार को लागू करते हैं। हालाँकि, इस तरह के कार्यान्वयन पर Datalog का एक मजबूत प्रभाव है, और कई लेखक उन्हें इस लेख में प्रस्तुत किए गए Datalog से अलग करने की जहमत नहीं उठाते हैं। तदनुसार, इस खंड में चर्चा किए गए अनुप्रयोगों में सूची-आधारित भाषाओं के यथार्थवादी कार्यान्वयन के अनुप्रयोग शामिल हैं।

Datalog को डेटा एकीकरण, सूचना निष्कर्षण, कंप्यूटर नेटवर्क, सुरक्षा, क्लाउड कम्प्यूटिंग और यंत्र अधिगम में समस्याओं के लिए लागू किया गया है।[29][30] Google ने बड़े डेटा संसाधन के लिए Datalog का एक एक्सटेंशन विकसित किया है।[31] Datalog ने स्थैतिक प्रोग्राम विश्लेषण में अनुप्रयोग देखा है।[32] Soufflé (प्रोग्रामिंग भाषा) | Soufflé बोली का उपयोग जावा (प्रोग्रामिंग भाषा) के लिए पॉइंटर विश्लेषण और नियंत्रण प्रवाह विश्लेषण | योजना (प्रोग्रामिंग भाषा) के लिए नियंत्रण-प्रवाह विश्लेषण लिखने के लिए किया गया है।[33][34] कुछ स्थिर विश्लेषणों को लिखना आसान बनाने के लिए डेटालॉग को संतुष्टि मॉडुलो सिद्धांतों के साथ एकीकृत किया गया है।[35] फ़्लिक्स (प्रोग्रामिंग भाषा) बोली स्थिर प्रोग्राम विश्लेषण लिखने के लिए भी अनुकूल है।[36] कुछ व्यापक रूप से उपयोग किए जाने वाले डेटाबेस सिस्टम में Datalog के लिए विकसित विचार और एल्गोरिदम शामिल हैं। उदाहरण के लिए, SQL:1999 मानक में SQL में श्रेणीबद्ध और पुनरावर्ती प्रश्न शामिल हैं, और IBM के IBM DB2 में मैजिक सेट्स एल्गोरिथम (शुरुआत में Datalog प्रश्नों के तेजी से मूल्यांकन के लिए विकसित) लागू किया गया है।[37]


इतिहास

Datalog की उत्पत्ति तर्क प्रोग्रामिंग की शुरुआत में हुई थी, लेकिन यह 1977 के आसपास एक अलग क्षेत्र के रूप में प्रमुख हो गया जब हर्वे गैलेयर और जैक मिंकर ने तर्क और डेटाबेस पर एक कार्यशाला का आयोजन किया।[38] डेविड मैयर को 'डेटालॉग' शब्द गढ़ने का श्रेय दिया जाता है।[39]


यह भी देखें

  • उत्तर सेट प्रोग्रामिंग
  • संयोजक प्रश्न
  • डेटालॉगज़ | डेटालॉगℤ* वियोगी सूची
  • फ्लिक्स (प्रोग्रामिंग भाषा)
  • शब्दार्थ वेब नियम भाषा
  • टपल-जनरेटिंग डिपेंडेंसी (TGD), डेटालॉग के समान सिंटैक्स के साथ संबंधपरक डेटाबेस पर अखंडता की कमी के लिए एक भाषा

टिप्पणियाँ

  1. ↑ 1.0 1.1 Ceri, Gottlob & Tanca 1989, p. 146.
  2. ↑ Eisner, Jason; Filardo, Nathaniel W. (2011). de Moor, Oege; Gottlob, Georg; Furche, Tim; Sellers, Andrew (eds.). "Dyna: Extending Datalog for Modern AI". Datalog Reloaded. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 6702: 181–220. doi:10.1007/978-3-642-24206-9_11. ISBN 978-3-642-24206-9.
  3. ↑ Maier, David; Tekle, K. Tuncay; Kifer, Michael; Warren, David S. (2018-09-01), "Datalog: concepts, history, and outlook", Declarative Logic Programming: Theory, Systems, and Applications, Association for Computing Machinery and Morgan & Claypool, vol. 20, pp. 3–100, doi:10.1145/3191315.3191317, ISBN 978-1-970001-99-0, S2CID 69379310, retrieved 2023-03-02
  4. ↑ Van Emden, M. H.; Kowalski, R. A. (1976-10-01). "एक प्रोग्रामिंग भाषा के रूप में विधेय तर्क का शब्दार्थ". Journal of the ACM. 23 (4): 733–742. doi:10.1145/321978.321991. ISSN 0004-5411. S2CID 11048276.
  5. ↑ Ceri, Gottlob & Tanca 1989, p. 149.
  6. ↑ Ceri, Gottlob & Tanca 1989, p. 150.
  7. ↑ Ceri, Gottlob & Tanca 1989, p. 154.
  8. ↑ Alvarez-Picallo, Mario; Eyers-Taylor, Alex; Peyton Jones, Michael; Ong, C.-H. Luke (2019). Caires, Luís (ed.). "वृद्धिशील संगणना को ठीक करना". Programming Languages and Systems. Lecture Notes in Computer Science (in English). Cham: Springer International Publishing. 11423: 525–552. doi:10.1007/978-3-030-17184-1_19. ISBN 978-3-030-17184-1. S2CID 53430789.
  9. ↑ Gilray, Thomas; Sahebolamri, Arash; Kumar, Sidharth; Micinski, Kristopher (2022-11-21). "उच्च-क्रम, डेटा-समानांतर संरचित कटौती". arXiv:2211.11573 [cs.PL].
  10. ↑ Subotić, Pavle; Jordan, Herbert; Chang, Lijun; Fekete, Alan; Scholz, Bernhard (2018-10-01). "बड़े पैमाने पर डेटालॉग संगणना के लिए स्वचालित सूचकांक चयन". Proceedings of the VLDB Endowment. 12 (2): 141–153. doi:10.14778/3282495.3282500. ISSN 2150-8097. S2CID 53569679.
  11. ↑ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). "Porting doop to Soufflé: a tale of inter-engine portability for Datalog-based analyses". Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis. SOAP 2017. New York, NY, USA: Association for Computing Machinery: 25–30. doi:10.1145/3088515.3088522. ISBN 978-1-4503-5072-3. S2CID 3074689. "The LogicBlox engine performs full query optimization."
  12. ↑ Arch, Samuel; Hu, Xiaowen; Zhao, David; Subotić, Pavle; Scholz, Bernhard (2022). Villanueva, Alicia (ed.). "Building a Join Optimizer for Soufflé". Logic-Based Program Synthesis and Transformation. Lecture Notes in Computer Science (in English). Cham: Springer International Publishing. 13474: 83–102. doi:10.1007/978-3-031-16767-6_5. ISBN 978-3-031-16767-6.
  13. ↑ Fan, Zhiwei; Zhu, Jianqiao; Zhang, Zuyu; Albarghouthi, Aws; Koutris, Paraschos; Patel, Jignesh (2018-12-10). "Scaling-Up In-Memory Datalog Processing: Observations and Techniques". arXiv:1812.03975 [cs.DB].
  14. ↑ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (2019-02-16). "समवर्ती डेटालॉग मूल्यांकन के लिए एक विशेष बी-ट्री". Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. PPoPP '19. New York, NY, USA: Association for Computing Machinery: 327–339. doi:10.1145/3293883.3295719. ISBN 978-1-4503-6225-2. S2CID 59617209.
  15. ↑ Wu, Jiacheng; Wang, Jin; Zaniolo, Carlo (2022-06-11). "मल्टीकोर मशीनों पर समांतर रिकर्सिव डेटालॉग मूल्यांकन का अनुकूलन". Proceedings of the 2022 International Conference on Management of Data. SIGMOD '22. New York, NY, USA: Association for Computing Machinery: 1433–1446. doi:10.1145/3514221.3517853. ISBN 978-1-4503-9249-5. S2CID 249578825. "These approaches implement the idea of parallel bottom-up evaluation by splitting the tables into disjoint partitions via discriminating functions, such as hashing, where each partition is then mapped to one of the parallel workers. After each iteration, workers coordinate with each other to exchange newly generated tuples where necessary.
  16. ↑ Gilray, Thomas; Sahebolamri, Arash; Kumar, Sidharth; Micinski, Kristopher (2022-11-21). "उच्च-क्रम, डेटा-समानांतर संरचित कटौती". arXiv:2211.11573 [cs.PL].
  17. ↑ Shaw, Marianne; Koutris, Paraschos; Howe, Bill; Suciu, Dan (2012). Barceló, Pablo; Pichler, Reinhard (eds.). "Optimizing Large-Scale Semi-Naïve Datalog Evaluation in Hadoop". Datalog in Academia and Industry. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 7494: 165–176. doi:10.1007/978-3-642-32925-8_17. ISBN 978-3-642-32925-8.
  18. ↑ Shkapsky, Alexander; Yang, Mohan; Interlandi, Matteo; Chiu, Hsuan; Condie, Tyson; Zaniolo, Carlo (2016-06-14). "स्पार्क पर डेटालॉग क्वेरीज़ के साथ बिग डेटा एनालिटिक्स". Proceedings of the 2016 International Conference on Management of Data. SIGMOD '16. New York, NY, USA: Association for Computing Machinery. 2016: 1135–1149. doi:10.1145/2882903.2915229. ISBN 978-1-4503-3531-7. PMC 5470845. PMID 28626296.
  19. ↑ Balbin, I.; Port, G. S.; Ramamohanarao, K.; Meenakshi, K. (1991-10-01). "स्तरीकृत डेटाबेस पर प्रश्नों की कुशल बॉटम-अप संगणना". The Journal of Logic Programming (in English). 11 (3): 295–344. doi:10.1016/0743-1066(91)90030-S. ISSN 0743-1066.
  20. ↑ Ullman, J. D. (1989-03-29). "डेटालॉग के लिए बॉटम-अप टॉप-डाउन को मात देता है". Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. PODS '89. New York, NY, USA: Association for Computing Machinery: 140–149. doi:10.1145/73721.73736. ISBN 978-0-89791-308-9. S2CID 13269547.
  21. ↑ Dantsin, Evgeny; Eiter, Thomas; Gottlob, Georg; Voronkov, Andrei (2001-09-01). "तर्क प्रोग्रामिंग की जटिलता और अभिव्यंजक शक्ति". ACM Computing Surveys. 33 (3): 374–425. doi:10.1145/502807.502810. ISSN 0360-0300.
  22. ↑ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (2023-01-11). "From SMT to ASP: Solver-Based Approaches to Solving Datalog Synthesis-as-Rule-Selection Problems". Proceedings of the ACM on Programming Languages. 7 (POPL): 7:185–7:217. doi:10.1145/3571200. S2CID 253525805.
  23. ↑ Zaniolo, Carlo; Yang, Mohan; Das, Ariyam; Shkapsky, Alexander; Condie, Tyson; Interlandi, Matteo (September 2017). "समुच्चय के साथ पुनरावर्ती Datalog कार्यक्रमों का फिक्सपॉइंट शब्दार्थ और अनुकूलन*". Theory and Practice of Logic Programming (in English). 17 (5–6): 1048–1065. arXiv:1707.05681. doi:10.1017/S1471068417000436. ISSN 1471-0684. S2CID 6272867.
  24. ↑ "Chapter 7. Rules - LogicBlox 3.10 Reference Manual". developer.logicblox.com. Retrieved 2023-03-04.
  25. ↑ "6.4. Negation - LogicBlox 3.10 Reference Manual". developer.logicblox.com. Retrieved 2023-03-04. "Additionally, negation is only allowed when the platform can determine a way to stratify all rules and constraints that use negation."
  26. ↑ Michael Lam; Dr. Sin Min Lee. "संगणक वैज्ञानिक". Course CS 157A. SAN JOSÉ STATE UNIVERSITY, department of Computer Science. Archived from the original on 2017-03-25.
  27. ↑ Hillebrand, Gerd G; Kanellakis, Paris C; Mairson, Harry G; Vardi, Moshe Y (1995-11-01). "डेटालॉग प्रोग्राम के लिए अनिर्णायक बाउंडनेस समस्याएँ". The Journal of Logic Programming (in English). 25 (2): 163–190. doi:10.1016/0743-1066(95)00051-K. ISSN 0743-1066.
  28. ↑ Lifschitz, Vladimir. "Foundations of logic programming." Principles of knowledge representation 3 (1996): 69-127. "The expressive possibilities of [Datalog] are much too limited for meaningful applications to knowledge representation."
  29. ↑ Huang, Green, and Loo, "Datalog and Emerging applications", SIGMOD 2011 (PDF), UC Davis{{citation}}: CS1 maint: multiple names: authors list (link).
  30. ↑ Mei, Hongyuan; Qin, Guanghui; Xu, Minjie; Eisner, Jason (2020). "Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification". Proceedings of ICML 2020. arXiv:2006.16723.
  31. ↑ Chin, Brian; Dincklage, Daniel von; Ercegovac, Vuk; Hawkins, Peter; Miller, Mark S.; Och, Franz; Olston, Christopher; Pereira, Fernando (2015). Ball, Thomas; Bodik, Rastislav; Krishnamurthi, Shriram; Lerner, Benjamin S.; Morrisett, Greg (eds.). "Yedalog: Exploring Knowledge at Scale". 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 32: 63–78. doi:10.4230/LIPIcs.SNAPL.2015.63. ISBN 978-3-939897-80-4.
  32. ↑ Whaley, John; Avots, Dzintars; Carbin, Michael; Lam, Monica S. (2005). Yi, Kwangkeun (ed.). "प्रोग्राम विश्लेषण के लिए बाइनरी डिसीजन डायग्राम के साथ डेटालॉग का उपयोग करना". Programming Languages and Systems. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 3780: 97–118. doi:10.1007/11575467_8. ISBN 978-3-540-32247-4.
  33. ↑ Scholz, Bernhard; Jordan, Herbert; Subotić, Pavle; Westmann, Till (2016-03-17). "Datalog में तेजी से बड़े पैमाने पर प्रोग्राम विश्लेषण पर". Proceedings of the 25th International Conference on Compiler Construction. CC 2016. New York, NY, USA: Association for Computing Machinery: 196–206. doi:10.1145/2892208.2892226. ISBN 978-1-4503-4241-4. S2CID 7531543.
  34. ↑ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). "Porting doop to Soufflé: a tale of inter-engine portability for Datalog-based analyses". Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis. SOAP 2017. New York, NY, USA: Association for Computing Machinery: 25–30. doi:10.1145/3088515.3088522. ISBN 978-1-4503-5072-3. S2CID 3074689.
  35. ↑ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (2020-11-13). "Formulog: Datalog for SMT-based static analysis". Proceedings of the ACM on Programming Languages. 4 (OOPSLA): 141:1–141:31. doi:10.1145/3428209. S2CID 226961727.
  36. ↑ Madsen, Magnus; Yee, Ming-Ho; Lhoták, Ondřej (2016-06-02). "From Datalog to flix: a declarative language for fixed points on lattices". ACM SIGPLAN Notices. 51 (6): 194–208. doi:10.1145/2980983.2908096. ISSN 0362-1340.
  37. ↑ Gryz; Guo; Liu; Zuzarte (2004). "Query sampling in DB2 Universal Database" (PDF). Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04. p. 839. doi:10.1145/1007568.1007664. ISBN 978-1581138597. S2CID 7775190.
  38. ↑ Gallaire, Hervé; Minker, John 'Jack', eds. (1978), "Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977", Advances in Data Base Theory, New York: Plenum Press, ISBN 978-0-306-40060-5.
  39. ↑ Abiteboul, Serge; Hull, Richard; Vianu, Victor (1995), Foundations of databases, p. 305, ISBN 9780201537710.


संदर्भ


Retrieved from ‘https://www.vigyanwiki.in/index.php?title=डेटालॉग&oldid=183265’