Vadalog

Es posible que este artículo contenga investigaciones originales . Por favor, mejórelo verificando las afirmaciones realizadas y agregando citas en línea . Las afirmaciones que consten únicamente de investigaciones originales deben eliminarse. ( Noviembre de 2024 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Vadalog es un sistema para realizar tareas complejas de razonamiento lógico sobre grafos de conocimiento . Su lenguaje se basa en una extensión del lenguaje basado en reglas Datalog , Warded Datalog ^± . ^[1]

Vadalog fue desarrollado por investigadores de la Universidad de Oxford y la Universidad Técnica de Viena, así como por empleados del Banco de Italia .

Un sistema de gestión de grafos de conocimiento (KGMS) tiene que gestionar grafos de conocimiento , que incorporan grandes cantidades de datos en forma de hechos y relaciones. En general, se puede considerar como la unión de tres componentes: ^[2]

1. KBMS, es decir, un sistema de gestión de base de conocimientos ,
2. Big Data, que es la necesidad de manejar grandes cantidades de datos, especialmente si tenemos en cuenta que los grafos de conocimiento han sido pensados ​​como una solución para integrar múltiples fuentes de datos, tanto corporativos como públicos, que pueden ser integrados en grandes grafos de conocimiento,
3. El análisis (de datos) es la necesidad de proporcionar acceso a paquetes de software existentes para aprendizaje automático, minería de texto, análisis de datos y visualización de datos y combinarlos en la misma plataforma.

Desde un punto de vista más técnico, se pueden identificar algunos requisitos adicionales para definir un KGMS adecuado:

• Definición de un lenguaje y de un formalismo con alto poder expresivo , ^{[3] [4]}
• Manejo rentable de datos , en todos sus pasos, desde la limpieza de datos hasta la extracción de datos web y el acceso a grandes volúmenes de datos de muchas fuentes diferentes, ^[5]
• razonamiento lógico , probabilístico y ontológico eficiente , ^{[6] [2]}
• baja complejidad, tanto en términos de complejidad espacial (para manejar grandes datos) como de sintaxis,
• interfaces ( API ) para acceder a muchas fuentes de datos heterogéneas, como RDBMS corporativos , almacenes NoSQL o RDF , la web, paquetes de aprendizaje automático y análisis. ^[7]

Otros requisitos pueden incluir funciones y servicios DBMS más típicos , como los propuestos por Codd. ^[8]

Vadalog ofrece una plataforma que cumple con todos los requisitos de un KGMS enumerados anteriormente. Es capaz de realizar tareas de razonamiento basadas en reglas sobre gráficos de conocimiento y también admite el flujo de trabajo de ciencia de datos, como la visualización de datos y el aprendizaje automático. ^[2]

Una regla es una expresión de la forma n  :− a ₁ , ..., a _n donde:

• a ₁ , ..., a _n son los átomos del cuerpo,
• n es el átomo de la cabeza .

Una regla permite inferir nuevo conocimiento a partir de las variables que están en el cuerpo: cuando todas las variables en el cuerpo de una regla son asignadas exitosamente, la regla se activa y resulta en la derivación del predicado principal: dada una base de datos D y un conjunto de reglas Σ , una tarea de razonamiento apunta a inferir nuevo conocimiento, aplicando las reglas del conjunto Σ a la base de datos D (el conocimiento extensional).

La forma más extendida de conocimiento que se ha adoptado en las últimas décadas ha sido en forma de reglas, ya sea en sistemas basados ​​en reglas , sistemas basados ​​en ontologías u otras formas y puede ser capturada típicamente en grafos de conocimiento. ^[7] La ​​naturaleza de los grafos de conocimiento también hace que la presencia de recursión en estas reglas sea un aspecto particularmente importante. La recursión significa que las mismas reglas pueden ser llamadas varias veces antes de obtener la respuesta final de la tarea de razonamiento y es particularmente poderosa ya que permite una inferencia basada en resultados previamente inferidos. Esto implica que el sistema debe proporcionar una estrategia que garantice la terminación. Más técnicamente, un programa es recursivo si el grafo de dependencia construido con la aplicación de las reglas es cíclico. La forma más simple de recursión es aquella en la que la cabeza de una regla también aparece en el cuerpo ( reglas autorrecursivas ).

El lenguaje Vadalog permite responder a consultas de razonamiento que también incluyen recursión. Está basado en Warded Datalog ^± , que pertenece a la familia de lenguajes Datalog ^± que extiende Datalog con cuantificadores existenciales en cabezas de reglas ^[9] y al mismo tiempo restringe su sintaxis para lograr decidibilidad y manejabilidad . ^{[10] [11]} Las reglas existenciales también se conocen como dependencias generadoras de tuplas ( tgds ). ^[12]

Una regla existencial tiene la siguiente forma:

${\displaystyle \varphi (x)\Rightarrow \existe z\Psi (x,z)}$

o, alternativamente, en sintaxis Datalog, se puede escribir de la siguiente manera:

p ( X , Z )  :-  r ( X ).

Las variables en Vadalog son como las variables en la lógica de primer orden y una variable es local a la regla en la que aparece. Esto significa que las apariciones del mismo nombre de variable en diferentes reglas hacen referencia a diferentes variables.

En el caso de un conjunto de reglas , consistente en lo siguiente:${\estilo de visualización \Sigma}$

r ( X , Y )  :-  p ( X ). p ( Z )  :-  r ( X , Z ).

La variable Z en la segunda regla se dice que es peligrosa, ya que la primera regla generará un nulo en el segundo término del átomo r y este se inyectará a la segunda regla para obtener el átomo p, lo que lleva a una propagación de nulos al intentar encontrar una respuesta al programa. Si se permite la propagación arbitraria, el razonamiento es indecidible y el programa será infinito. ^[7] Warded Datalog ^± supera este problema pidiendo que para cada regla definida en un conjunto , todas las variables en los cuerpos de reglas deben coexistir en al menos un átomo en la cabeza, llamado ward. El concepto de wardness restringe la forma en que se puede usar una variable peligrosa dentro de un programa. Aunque esto es un límite en términos de poder expresivo, con este requisito y gracias a su arquitectura y algoritmos de terminación , Warded Datalog ^± es capaz de encontrar respuestas a un programa en un número finito de pasos. También muestra un buen equilibrio entre complejidad computacional y poder expresivo, capturando la complejidad de los datos PTIME mientras permite el razonamiento ontológico y la posibilidad de ejecutar programas con recursión. ^[13]${\estilo de visualización \Sigma}$

Vadalog replica en su totalidad Warded Datalog ^± y lo amplía con la inclusión en el lenguaje de:

• agregaciones monótonas ( operadores min, max, sum, prod, count ), ^[14]
• negación estratificada ,
• soporte para diferentes tipos de datos ( cadenas, enteros, dobles, fecha, booleanos, conjuntos, listas, nulos marcados),
• mecanismo de anotación enriquecido para definir cómo interactuar con fuentes de datos y bibliotecas externas.

Además, el sistema ofrece una arquitectura de alta ingeniería que permite un cálculo eficiente. Esto se hace de las dos maneras siguientes.

1. Adoptar una arquitectura de procesamiento en memoria y un enfoque basado en flujo de extracción , que limita el consumo de memoria o lo hace predecible.
2. Utilizando una estrategia de control de terminación agresiva , que detecta patrones y redundancia mientras se construye el gráfico de persecución (usado para generar las respuestas) lo antes posible y corta el cálculo cuando ocurren. ^[7] Esto está conectado con el concepto de isomorfismo de hechos, que reduce el número de pasos necesarios para obtener una respuesta: si un hecho h es isomorfo a h' , el sistema solo explorará el gráfico de persecución del hecho h . ^[15]

Por lo tanto, el sistema Vadalog es capaz de realizar tareas de razonamiento ontológico, ya que pertenece a la familia Datalog . El razonamiento con el núcleo lógico de Vadalog captura OWL 2 QL y SPARQL ^[16] (a través del uso de cuantificadores existenciales) y análisis de grafos (a través del soporte para recursión y agregación).

Considere el siguiente conjunto de reglas de Vadalog:

antepasado ( Y , X )  :-  persona ( X ). antepasado ( Y , Z )  :-  antepasado ( Y , X ),  padre ( X , Z ).

La primera regla establece que para cada persona existe un ancestro . La segunda regla establece que, si es un padre de , entonces es un ancestro de también. Nótese la cuantificación existencial en la primera posición del predicado del ancestro en la primera regla, que generará un valor nulo ν _i en el procedimiento de búsqueda. Dicho valor nulo se propaga luego al encabezado de la segunda regla. Considere una base de datos con los hechos extensionales y la consulta para encontrar todos los hechos de ancestros implicados como tarea de razonamiento.${\estilo de visualización X}$${\estilo de visualización Y}$${\estilo de visualización X}$${\estilo de visualización Z}$${\estilo de visualización Y}$${\estilo de visualización Z}$D = {person(Alice), person(Bob), parent(Alice,Bob)}

Al realizar el procedimiento de persecución, el hecho se genera activando la primera regla en . Luego, se crea activando la segunda regla en y . Finalmente, la primera regla podría activarse en , pero el hecho resultante es isomorfo con , por lo que este hecho no se genera y la parte correspondiente del gráfico de persecución no se explora.ancestor(ν1,Alice)person(Alice)ancestor(ν1,Bob)ancestor(ν1,Alice)parent(Alice,Bob)person(Bob)ancestor(ν2,Bob)ancestor(ν1,Bob)

En conclusión, la respuesta a la pregunta es el conjunto de hechos .{ancestor(ν1,Alice), ancestor(ν1,Bob)}

La integración de Vadalog con herramientas de ciencia de datos se logra mediante primitivas y funciones de enlace de datos . ^[7]

1. Primitivas de enlace de datos : los enlaces permiten conectarse a fuentes de datos externas o sistemas como una base de datos, un marco o una biblioteca y decirle al sistema cómo tratarlos. Esto incluye conexiones con sistemas de bases de datos relacionales como PostgreSQL o MySQL , y bases de datos gráficas, como Neo4j . También es posible integrar bibliotecas de aprendizaje automático ( Weka , scikit-learn , Tensorflow ) y una herramienta de extracción de datos web, OXPath, que permite recuperar datos directamente de la web. Esto es posible a través de las llamadas anotaciones: son hechos especiales que aumentan los conjuntos de reglas existenciales con comportamientos específicos. La @inputanotación le dice al sistema que los hechos para un átomo del programa se importan de una fuente de datos externa, por ejemplo, una base de datos relacional. La @outputanotación especifica que los hechos para un átomo del programa se exportarán a un destino externo, por ejemplo, la salida estándar o una base de datos relacional. Otras anotaciones como @bind, @mapping, @qbindpermiten personalizar las fuentes de datos para la @inputanotación o los destinos para la @outputanotación.
2. Funciones : también se pueden admitir expresiones personalizadas que utilicen operadores aritméticos, manipulación de cadenas o comparación. También se habilitan bibliotecas escritas en Python y se pueden integrar con la anotación dedicada @library.

El sistema también proporciona una integración con la plataforma JupyterLab , donde se pueden escribir y ejecutar programas Vadalog y leer la salida, explotando las funcionalidades de la plataforma. También da la posibilidad de evaluar la corrección del programa, ejecutarlo y analizar el proceso de derivación de los datos de salida mediante herramientas como el resaltado de sintaxis , el análisis de código (verificando si el código es correcto o hay errores) y las explicaciones de resultados (cómo se ha obtenido el resultado): todas estas funcionalidades están integradas en el cuaderno y ayudan en la escritura y análisis del código Vadalog.

El sistema Vadalog puede emplearse para abordar muchos casos de uso del mundo real de distintos campos de investigación e industria. ^[3] Entre estos últimos, esta sección presenta dos casos relevantes y accesibles que pertenecen al dominio financiero. ^{[17] [18] [19]}

Un gráfico de propiedad de una empresa muestra las entidades como nodos y las participaciones como aristas. Cuando una entidad tiene una determinada cantidad de participaciones en otra (comúnmente identificadas como mayoría absoluta), puede ejercer un poder de decisión sobre esa entidad y esto configura un control de la empresa y, de manera más general, una estructura de grupo. La búsqueda de todas las relaciones de control requiere investigar diferentes escenarios y estructuras de grupo muy complejas, a saber, control directo e indirecto. Esta consulta se puede traducir en las siguientes reglas:

• una empresa X controla directamente una empresa Y si X posee directamente más del 50% del capital total de Y ,
• una empresa X controla indirectamente una empresa Y si X controla un conjunto de empresas intermediarias que en conjunto (es decir, sumando sus acciones) poseen más del 50% de Y.

Estas reglas se pueden escribir en un programa Vadalog que derivará todos los bordes de control como se muestra a continuación:

control ( X , X )  :-  empresa ( X ).control ( X , Y )  :-  control ( X , Y ),  propio ( Y , Z , W ),  V  =  suma ( W , < Y > ),  V  >  0.5 .

La primera regla establece que cada empresa se controla a sí misma. La segunda regla define el control de X sobre Z sumando las acciones de Z que poseen las empresas Y sobre todas las empresas Y controladas por X.

Este escenario consiste en determinar si existe un vínculo entre dos entidades en un gráfico de propiedad de empresas. Determinar la existencia de tales vínculos es relevante, por ejemplo, en la supervisión bancaria y la evaluación de la solvencia crediticia, ya que una empresa no puede actuar como garante de préstamos a otra empresa si las dos comparten tal relación. Formalmente, dos empresas X e Y están involucradas en un vínculo estrecho si:

• x (resp., Y ) posee directa o indirectamente el 20% o más del capital de Y (resp., X ), o
• un tercero común Z posee directa o indirectamente el 20% o más del capital social de X e Y.

Estas reglas se pueden escribir en un programa Vadalog que derivará todos los bordes de enlaces cerrados como el siguiente:

mcl ( X , Y , S )  :-  propio ( X , Y , S ).mcl ( X , Z , S1  *  S2 )  :-  mc1 ( X , Y , S1 ),  propio ( Y , Z , S2 ).cl1 ( X , Y )  :-  mcl ( X , Y , S ),  TS  =  suma ( S ),  TS  >  0,2 .cl2 ( X , Y )  :-  cl1 ( Z , X ),  cl1 ( Z , Y ),  X  ! =  Y .enlace cercano ( X , Y )  :-  cl1 ( X , Y ).enlace cercano ( X , Y )  :-  cl2 ( X , Y ).

La primera regla establece que dos empresas X e Y conectadas por una ventaja de propiedad son posibles vínculos estrechos. La segunda regla establece que, si X e Y son posibles vínculos estrechos con una acción S1 y existe una ventaja de propiedad de Y a una empresa Z con una acción S2 , entonces también X y Z son posibles vínculos estrechos con una acción S1 * S2 . La tercera regla establece que, si la suma de todas las acciones parciales S de Y propiedad directa o indirecta de X es mayor o igual al 20% del capital de Y , entonces son vínculos estrechos según la primera definición. La cuarta regla modela la segunda definición de vínculos estrechos, es decir, el caso de terceros.

• Registro de datos
• Prólogo
• Sistema de gestión de bases de datos
• Lenguaje de reglas de la Web semántica
• Base de datos de gráficos