Datalog: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Awserer (обсуждение | вклад) |
Awserer (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
* требует, чтобы каждая переменная, появляющаяся в отрицательном литерале в теле предложения, также появлялась в некотором положительном литерале в теле предложения<ref>{{Cite web|url=https://web.archive.org/web/20170325035511/http://www.cs.sjsu.edu/faculty/lee/cs157/24SpDatalog.ppt|title=Datalog (презентация)|website=web.archive.org|date=2017-03-25|access-date=2022-08-20}}</ref> |
* требует, чтобы каждая переменная, появляющаяся в отрицательном литерале в теле предложения, также появлялась в некотором положительном литерале в теле предложения<ref>{{Cite web|url=https://web.archive.org/web/20170325035511/http://www.cs.sjsu.edu/faculty/lee/cs157/24SpDatalog.ppt|title=Datalog (презентация)|website=web.archive.org|date=2017-03-25|access-date=2022-08-20}}</ref> |
||
Процедура разрешения запроса с помощью Datalog основана на [[Логика первого порядка|логике первого порядка]], и, по этой причине, является правильной и полной. Однако Datalog не является полным по Тьюрингу и, таким образом, используется в качестве предметно-ориентированного языка, который может использовать преимущества эффективных алгоритмов, разработанных для разрешения запросов. Действительно, для эффективного выполнения запросов были предложены различные методы, например, алгоритм Magic Sets<ref>{{cite journal|last=Bancilhon |url=http://ssdi.di.fct.unl.pt/krr/docs/magicsets.pdf |publisher=UNL |place=[[Portugal|PT]] |title=Magic sets and other strange ways to implement logic programs |url-status=dead |archive-url=https://web.archive.org/web/20120308104055/http://ssdi.di.fct.unl.pt/krr/docs/magicsets.pdf |archive-date=2012-03-08 }}</ref>, табличное логическое программирование<ref>{{cite journal|first1=Frank|last1=Pfenning|first2=Carsten|last2=Schuermann|publisher=CMU|url=https://www.cs.cmu.edu/~twelf/guide-1-4/twelf_5.html#SEC31|title=Twelf User's Guide}}</ref> или разрешение SLG<ref>{{cite journal|title=Efficient top-down computation of queries under the well-founded semantics|url=http://www.cs.sunysb.edu/~tswift/webpapers/jlp-95.pdf}}</ref>. |
Процедура разрешения запроса с помощью Datalog основана на [[Логика первого порядка|логике первого порядка]], и, по этой причине, является правильной и полной. Однако Datalog не является полным по Тьюрингу и, таким образом, используется в качестве предметно-ориентированного языка, который может использовать преимущества эффективных алгоритмов, разработанных для разрешения запросов. Действительно, для эффективного выполнения запросов были предложены различные методы, например, алгоритм Magic Sets<ref>{{cite journal|last=Bancilhon |url=http://ssdi.di.fct.unl.pt/krr/docs/magicsets.pdf |publisher=UNL |place=[[Portugal|PT]] |title=Magic sets and other strange ways to implement logic programs |url-status=dead |archive-url=https://web.archive.org/web/20120308104055/http://ssdi.di.fct.unl.pt/krr/docs/magicsets.pdf |archive-date=2012-03-08 }}</ref>, табличное логическое программирование<ref>{{cite journal|first1=Frank|last1=Pfenning|first2=Carsten|last2=Schuermann|publisher=CMU|url=https://www.cs.cmu.edu/~twelf/guide-1-4/twelf_5.html#SEC31|title=Twelf User's Guide}}</ref> или разрешение SLG<ref>{{cite journal|title=Efficient top-down computation of queries under the well-founded semantics|url=http://www.cs.sunysb.edu/~tswift/webpapers/jlp-95.pdf}}</ref>. |
||
Некоторые широко используемые системы баз данных включают идеи и алгоритмы, разработанные для Datalog. Например, стандарт SQL:1999 включает рекурсивные запросы, а алгоритм Magic Sets (первоначально разработанный для более быстрой оценки запросов Datalog) реализован в IBM [[DB2]]. Кроме того, механизмы Datalog стоят за специализированными системами баз данных, такими как база данных Intellidimension для семантической сети<ref>{{Книга|ссылка=https://www.worldcat.org/oclc/612954168|заглавие=Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data : 2004, Paris, France, June 13-18, 2004.|год=2004|место=[New York]|издательство=Association for Computing Machinery|страниц=xvii, 988 pages|isbn=1-58113-859-8, 978-1-58113-859-7}}</ref>. В Datalog было внесено несколько расширений, например, для поддержки агрегатных функций, для обеспечения объектно-ориентированного программирования или для разрешения дизъюнкций в качестве заголовков предложений. Эти расширения оказывают существенное влияние на определение семантики Datalog и на реализации конкретных версия интерпретатора Datalog. |
|||
== Примечания == |
== Примечания == |
||
Версия от 09:09, 23 августа 2022
| Datalog | |
|---|---|
| Класс языка | Логический, Декларативное |
| Появился в | 1986 |
| Система типов | Слабая |
| Диалекты | Datomic, pyDatalog, Dyna и т.д. |
Datalog — это язык декларативного логического программирования. Хотя синтаксически он выглядит как подмножество Prolog, Datalog обычно использует восходящую, а не нисходящую модель разрешения выражений. Это отличие приводит к значительному отличию поведения и свойств от Пролога. Он часто используется в качестве языка запросов для дедуктивных баз данных. В последние годы Datalog нашел новое применение в интеграции данных, извлечении информации, создании сетей, анализе программ, безопасности, облачных вычислениях и машинном обучении[1][2].
Его истоки восходят к началу логического программирования, но он стал выделяться как отдельная тематика примерно в 1977 году, когда Эрве Галлер и Джек Минкер организовали семинар по логике и базам данных[3]. Дэвиду Майеру приписывают введение термина Datalog[4].
Возможности, ограничения и расширения
В отличие от Пролога, операторы программы Datalog могут быть указаны в любом порядке. Более того, запросы Datalog к конечным множествам гарантированно завершатся, поэтому в Datalog нет оператора cut в Прологе. Это делает Datalog полностью декларативным языком.
В отличие от Пролога, Datalog:
- запрещает сложные термы в качестве аргументов предикатов, например, p (1, 2) допустимо, но не p (f (1), 2),
- накладывает определенные стратификационные ограничения на использование отрицания и рекурсии,
- требует, чтобы каждая переменная, которая появляется в заголовке предложения, также появлялась в неарифметическом положительном (то есть не инвертированном) литерале в теле предложения,
- требует, чтобы каждая переменная, появляющаяся в отрицательном литерале в теле предложения, также появлялась в некотором положительном литерале в теле предложения[5]
Процедура разрешения запроса с помощью Datalog основана на логике первого порядка, и, по этой причине, является правильной и полной. Однако Datalog не является полным по Тьюрингу и, таким образом, используется в качестве предметно-ориентированного языка, который может использовать преимущества эффективных алгоритмов, разработанных для разрешения запросов. Действительно, для эффективного выполнения запросов были предложены различные методы, например, алгоритм Magic Sets[6], табличное логическое программирование[7] или разрешение SLG[8].
Некоторые широко используемые системы баз данных включают идеи и алгоритмы, разработанные для Datalog. Например, стандарт SQL:1999 включает рекурсивные запросы, а алгоритм Magic Sets (первоначально разработанный для более быстрой оценки запросов Datalog) реализован в IBM DB2. Кроме того, механизмы Datalog стоят за специализированными системами баз данных, такими как база данных Intellidimension для семантической сети[9]. В Datalog было внесено несколько расширений, например, для поддержки агрегатных функций, для обеспечения объектно-ориентированного программирования или для разрешения дизъюнкций в качестве заголовков предложений. Эти расширения оказывают существенное влияние на определение семантики Datalog и на реализации конкретных версия интерпретатора Datalog.
Примечания
- ↑ Huang, Green, and Loo, "Datalog and Emerging applications", SIGMOD 2011 (PDF), UC Davis
{{citation}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка). - ↑ 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.
- ↑ Logic and data bases. — New York, 1978. — viii, 458 pages с. — ISBN 0-306-40060-X, 978-0-306-40060-5.
- ↑ S. Abiteboul. Foundations of databases. — Reading, Mass.: Addison-Wesley, 1995. — xviii, 685 pages с. — ISBN 0-201-53771-0, 978-0-201-53771-0.
- ↑ Datalog (презентация). web.archive.org (25 марта 2017). Дата обращения: 20 августа 2022.
- ↑ Bancilhon. "Magic sets and other strange ways to implement logic programs" (PDF). PT: UNL. Архивировано из оригинала (PDF) 8 марта 2012.
{{cite journal}}: Cite journal требует|journal=(справка) - ↑ Pfenning, Frank; Schuermann, Carsten. "Twelf User's Guide". CMU.
{{cite journal}}: Cite journal требует|journal=(справка) - ↑ "Efficient top-down computation of queries under the well-founded semantics" (PDF).
{{cite journal}}: Cite journal требует|journal=(справка) - ↑ Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data : 2004, Paris, France, June 13-18, 2004.. — [New York]: Association for Computing Machinery, 2004. — xvii, 988 pages с. — ISBN 1-58113-859-8, 978-1-58113-859-7.