Registro de datos disyuntivo

Disyunctive Datalog es una extensión del lenguaje de programación lógica Datalog que permite disyunciones en los encabezamientos de las reglas. Esta extensión permite que el lenguaje disyuntivo Datalog exprese varios problemas NP-hard que no se sabe que puedan expresarse en un lenguaje Datalog simple. Disyunctive Datalog se ha aplicado en el contexto del razonamiento sobre ontologías en la web semántica . ^[1] DLV es una implementación del lenguaje disyuntivo Datalog.

Sintaxis

Un programa Datalog disyuntivo es una colección de reglas. Una regla es una cláusula de la forma: ^[2]

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

donde , ..., pueden negarse y pueden incluir restricciones de (des)igualdad. ${\displaystyle b_{1}}$ ${\displaystyle b_{m}}$

Semántica

Hay al menos tres formas de definir la semántica de Datalog disyuntivo: ^[3]

• Semántica del modelo mínimo
• Semántica del modelo perfecto
• Semántica del modelo estable disyuntivo, que generaliza la semántica del modelo estable

Expresividad

El registro de datos disyuntivo puede expresar varios problemas NP-completos y NP-difíciles , incluidos el problema del viajante , la coloración de gráficos , el problema de camarilla máxima y la cobertura mínima de vértices . ^[3] Estos problemas solo se pueden expresar en Datalog si la jerarquía polinomial colapsa.

Implementaciones

El sistema DLV ( Data Log with Disjunction, donde se utiliza el símbolo de disyunción lógica V ) implementa la semántica del modelo estable disyuntivo. ^[4]

Véase también

• Sintaxis y semántica de la programación lógica

Fuentes

Notas

1. Kaminski, Mark; Nenov, Yavor; Grau, Bernardo Cuenca (21 de junio de 2014). "Reescritura de registros de datos de programas de registros de datos disyuntivos y sus aplicaciones al razonamiento ontológico". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 28 (1). arXiv : 1404.3141 . doi :10.1609/aaai.v28i1.8854. ISSN  2374-3468. S2CID  17098158.
2. Eiter, Gottlob y Mannila 1997, pág. 370.
3. Eiter, Gottlob y Mannila 1997.
4. Alviano, Mario; Faber, Wolfgang; Leona, Nicola; Perri, Simona; Pfeifer, Gerald; Terracina, Giorgio (2011), "The Disjunctive Datalog System DLV", Datalog Reloaded , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 282–301, doi :10.1007/978-3-642-24206-9_17, ISBN 978-3-642-24205-2, consultado el 4 de agosto de 2023

Referencias

• Eiter, Thomas; Gottlob, Georg; Mannila, Heikki (1997-09-01). "Registro de datos disyuntivo". ACM Transactions on Database Systems . 22 (3): 364–418. doi : 10.1145/261124.261126 . ISSN  0362-5915. S2CID  8755376.