Дизъюнктивный журнал данных

Дизъюнктивный журнал данных — это расширение языка логического программирования Datalog , которое допускает дизъюнкцию в заголовках правил. Это расширение позволяет дизъюнктивному журналу данных выражать несколько NP-сложных задач, которые, как известно, не могут быть выражены в простом журнале данных. Дизъюнктивная регистрация данных применялась в контексте рассуждений об онтологиях в семантической сети . ^[1] DLV — это реализация дизъюнктивного журнала данных.

Синтаксис

Дизъюнктивная программа Datalog представляет собой набор правил. Правило – это предложение вида: ^[2]

a_{1}\vee \dots \vee a_{n}\leftarrow b_{1}\wedge \dots \wedge b_{m}\quad 1\leq n,0\leq m

где $b_{1}$ , ..., $b_{m}$ может быть отрицательным и может включать ограничения (не)равенства.

Семантика

Существует как минимум три способа определения семантики дизъюнктивного журнала данных: ^[3]

Семантика минимальной модели
Идеальная семантика модели
Семантика дизъюнктивной стабильной модели, которая обобщает семантику стабильной модели.

Выразительность

Дизъюнктивный журнал данных может выражать несколько NP-полных и NP-сложных задач, включая задачу коммивояжера , раскраску графа , задачу максимальной клики и минимальное вершинное покрытие . ^[3] Эти проблемы выражаются в Datalog только в том случае, если полиномиальная иерархия рушится.

Реализации

Система DLV модели ( Журнал данных используется с дизъюнкцией, где устойчивой дизъюнктивной . символ логической дизъюнкции V) реализует семантику ^[4]

См. также

Синтаксис и семантика логического программирования

Источники

Примечания

^ Камински, Марк; Ненов, Явор; Грау, Бернардо Куэнка (21 июня 2014 г.). «Перезапись журналов данных в дизъюнктивных программах регистрации данных и ее приложения к рассуждениям онтологий» . Материалы конференции AAAI по искусственному интеллекту . 28 (1). arXiv : 1404.3141 . дои : 10.1609/aaai.v28i1.8854 . ISSN 2374-3468 . S2CID 17098158 .
^ Эйтер, Готтлоб и Маннила 1997 , стр. 370.
^ Перейти обратно: ^а ^б Эйтер, Готтлоб и Маннила, 1997 .
^ Альвиано, Марио; Фабер, Вольфганг; Леоне, Никола; Перри, Симона; Пфайфер, Джеральд; Террачина, Джорджио (2011), «Дизъюнктивная система регистрации данных DLV» , Datalog Reloaded , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 282–301, номер документа : 10.1007/978-3-642-24206-9_17 , ISBN 978-3-642-24205-2 , получено 4 августа 2023 г.

Ссылки

Эйтер, Томас; Готтлоб, Георг; Маннила, Хейкки (1 сентября 1997 г.). «Дизъюнктивный журнал данных» . Транзакции ACM в системах баз данных . 22 (3): 364–418. дои : 10.1145/261124.261126 . ISSN 0362-5915 . S2CID 8755376 .

[1] Камински, Марк; Ненов, Явор; Грау, Бернардо Куэнка (21 июня 2014 г.). «Перезапись журналов данных в дизъюнктивных программах регистрации данных и ее приложения к рассуждениям онтологий» . Материалы конференции AAAI по искусственному интеллекту . 28 (1). arXiv : 1404.3141 . дои : 10.1609/aaai.v28i1.8854 . ISSN 2374-3468 . S2CID 17098158 .

[FOOTNOTEEiterGottlobMannila1997370-2] Эйтер, Готтлоб и Маннила 1997 , стр. 370.

[FOOTNOTEEiterGottlobMannila1997-3] Перейти обратно: ^а ^б Эйтер, Готтлоб и Маннила, 1997 .

[4] Альвиано, Марио; Фабер, Вольфганг; Леоне, Никола; Перри, Симона; Пфайфер, Джеральд; Террачина, Джорджио (2011), «Дизъюнктивная система регистрации данных DLV» , Datalog Reloaded , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 282–301, номер документа : 10.1007/978-3-642-24206-9_17 , ISBN 978-3-642-24205-2 , получено 4 августа 2023 г.

[1]

[2]

[3]

[4]