Hispanopedia Wiki
Articulo de referencia

Registro de datos

Datalog es un lenguaje de programación lógica declarativa . Si bien sintácticamente es un subconjunto de Prolog , Datalog generalmente utiliza un modelo de evaluación ascendente...

Hispanopedia WikiContenido en espanolLectura gratuita

Datalog es un lenguaje de programación lógica declarativa . Si bien sintácticamente es un subconjunto de Prolog , Datalog generalmente utiliza un modelo de evaluación ascendente en lugar de descendente. Esta diferencia produce un comportamiento y propiedades significativamente distintos a los de Prolog . Se utiliza frecuentemente como lenguaje de consulta para bases de datos deductivas . Datalog se ha aplicado a problemas de integración de datos , redes , análisis de programas y más.

Ejemplo

Un programa Datalog consta de hechos , que son afirmaciones que se consideran verdaderas, y reglas , que indican cómo deducir nuevos hechos a partir de hechos conocidos. Por ejemplo, aquí hay dos hechos que significan que Xerces es padre de Brooke y que Brooke es padre de Damocles :

padre ( xerces , brooke ). padre ( brooke , damocles ).

Los nombres están escritos en minúsculas porque las cadenas que comienzan con una letra mayúscula representan variables. Aquí hay dos reglas:

ancestro ( X , Y ) :- padre ( X , Y ). ancestro ( X , Y ) :- padre ( X , Z ), ancestro ( Z , Y ).

El :-símbolo se lee como "si" y la coma se lee como "y", por lo que estas reglas significan:

  • X es un antepasado de Y si X es un padre de Y.
  • X es un antepasado de Y si X es un progenitor de algún Z, y Z es un antepasado de Y.

El significado de un programa se define como el conjunto de todos los hechos que se pueden deducir utilizando los hechos iniciales y las reglas. El significado de este programa viene dado por los siguientes hechos:

padre ( xerces , brooke ). padre ( brooke , damocles ). antepasado ( xerces , brooke ). antepasado ( brooke , damocles ). antepasado ( xerces , damocles ).

Algunas implementaciones de Datalog no deducen todos los hechos posibles, sino que responden a consultas :

?- antepasado ( xerces , X ).

Esta consulta pregunta: ¿Quiénes son todos los X de los que Xerces es un ancestro? Para este ejemplo, devolvería Brooke y Damocles .

Comparación con bases de datos relacionales

El subconjunto no recursivo de Datalog está estrechamente relacionado con los lenguajes de consulta para bases de datos relacionales , como SQL . La siguiente tabla muestra la relación entre Datalog, el álgebra relacional y los conceptos de SQL :

De forma más formal, Datalog no recursivo se corresponde precisamente con uniones de consultas conjuntivas o, equivalentemente, con álgebra relacional sin negación.

Sintaxis

Un programa Datalog consta de una lista de reglas ( cláusulas Horn ). [ 1 ] Si constante y variable son dos conjuntos numerables de constantes y variables respectivamente, y relación es un conjunto numerable de símbolos de predicado , entonces la siguiente gramática BNF expresa la estructura de un programa Datalog:

< programa > ::= < regla > < programa > | "" < regla > ::= < átomo > ":-" < lista de átomos > "." < átomo > ::= < relación > "(" < lista de términos > ")" < lista de átomos > ::= < átomo > | < átomo > "," < lista de átomos > | "" < término > ::= < constante > | < variable > < lista de términos > ::= < término > | < término > "," < lista de términos > | ""

Los átomos también se denominan literales . El átomo a la izquierda del :-símbolo se llama cabeza de la regla; los átomos a la derecha son el cuerpo . Todo programa Datalog debe cumplir la condición de que cada variable que aparece en la cabeza de una regla también aparezca en el cuerpo (esta condición a veces se denomina restricción de rango ). [ 1 ] [ 2 ]

Existen dos convenciones comunes para los nombres de variables: escribir las variables con mayúscula inicial o anteponerles un signo de interrogación ?. [ 3 ]

Tenga en cuenta que, según esta definición, Datalog no incluye la negación ni las agregaciones; consulte la sección  Extensiones para obtener más información sobre esas construcciones.

Las reglas con cuerpos vacíos se denominan hechos . Por ejemplo, la siguiente regla es un hecho:

r ( x ) :- .

El conjunto de hechos se denomina base de datos extensional o EDB del programa Datalog. El conjunto de tuplas calculadas al evaluar el programa Datalog se denomina base de datos intensional o IDB .

azúcar sintáctico

Muchas implementaciones de programación lógica extienden la gramática anterior para permitir escribir hechos sin el :-, como por ejemplo:

r ( x ).

Algunos también permiten escribir relaciones 0-arias sin paréntesis, como por ejemplo:

p :- q .

Se trata simplemente de abreviaturas ( azúcar sintáctico ); no tienen ningún impacto en la semántica del programa.

Semántica

Existen tres enfoques ampliamente utilizados para la semántica de los programas Datalog: el basado en modelos , el de punto fijo y el basado en pruebas . Se puede demostrar que estos tres enfoques son equivalentes. [ 4 ]

Un átomo se denomina fundamental si ninguno de sus subtérminos es variable. Intuitivamente, cada una de las semánticas define el significado de un programa como el conjunto de todos los átomos fundamentales que se pueden deducir de las reglas del programa, partiendo de los hechos.

Teórico de modelos

Una regla se llama fundamental si todos sus átomos (cabeza y cuerpo) son fundamentales. Una regla R 2 es una instancia fundamental de otra regla R 1 si R 2 es el resultado de una sustitución de constantes por todas las variables en R 1 . La base de Herbrand de un programa Datalog es el conjunto de todos los átomos fundamentales que se pueden formar con las constantes que aparecen en el programa. El modelo de Herbrand de un programa Datalog es el subconjunto más pequeño de la base de Herbrand tal que, para cada instancia fundamental de cada regla en el programa, si los átomos en el cuerpo de la regla están en el conjunto, entonces también lo está la cabeza. [ 5 ] La semántica de la teoría de modelos define el modelo mínimo de Herbrand como el significado del programa.

Punto fijo

Sea I el conjunto potencia de la base de Herbrand de un programa P. El operador de consecuencia inmediata para P es una aplicación T de I a I que agrega todos los nuevos átomos básicos que se pueden derivar de las reglas del programa en un solo paso. La semántica del punto fijo mínimo define el punto fijo mínimo de T como el significado del programa; esto coincide con el modelo mínimo de Herbrand. [ 6 ]

La semántica de punto fijo sugiere un algoritmo para calcular el modelo mínimo: se parte del conjunto de hechos básicos del programa y, a continuación, se añaden repetidamente las consecuencias de las reglas hasta alcanzar un punto fijo. Este algoritmo se denomina evaluación ingenua .

Demostración teórica

Árbol de prueba que muestra la derivación del átomo fundamental path(x, z)a partir del programa. 
borde ( x , y ). borde ( y , z ). ruta ( A , B ) :- borde ( A , B ). ruta ( A , C ) :- ruta ( A , B ), borde ( B , C ).

La semántica de la teoría de la demostración define el significado de un programa Datalog como el conjunto de hechos con sus correspondientes árboles de demostración . Intuitivamente, un árbol de demostración muestra cómo derivar un hecho a partir de los hechos y las reglas de un programa.

Podría interesar saber si un átomo fundamental específico aparece en el modelo mínimo de Herbrand de un programa Datalog, quizás sin prestar mucha atención al resto del modelo. Una lectura descendente de los árboles de prueba descritos anteriormente sugiere un algoritmo para calcular los resultados de dichas consultas . Esta lectura sirve de base para el algoritmo de resolución SLD , que constituye la base para la evaluación de Prolog .

Evaluación

Existen muchas maneras diferentes de evaluar un programa Datalog, con distintas características de rendimiento.

Estrategias de evaluación ascendente

Las estrategias de evaluación ascendente parten de los datos del programa y aplican repetidamente las reglas hasta que se establece algún objetivo o se plantea alguna pregunta, o hasta que se produce el modelo mínimo completo del programa.

Evaluación ingenua

La evaluación ingenua refleja la semántica de punto fijo para los programas Datalog. La evaluación ingenua utiliza un conjunto de "hechos conocidos", que se inicializa con los hechos del programa. Procede enumerando repetidamente todas las instancias básicas de cada regla del programa. Si cada átomo del cuerpo de la instancia básica pertenece al conjunto de hechos conocidos, entonces el átomo de la cabeza se añade a dicho conjunto. Este proceso se repite hasta alcanzar un punto fijo, momento en el que ya no se pueden deducir más hechos. La evaluación ingenua genera el modelo mínimo completo del programa. [ 7 ]

Evaluación semiingenua

La evaluación semiingenua es una estrategia de evaluación ascendente que puede ser asintóticamente más rápida que la evaluación ingenua. [ 8 ] En la evaluación ingenua, los mismos hechos pueden descubrirse una y otra vez, mientras que la evaluación semiingenua evita este cálculo repetido al trabajar únicamente con las nuevas tuplas generadas en la iteración anterior. [ 9 ]

Consideraciones de rendimiento

Se evaluó un motor Datalog paralelo en la supercomputadora Theta del Laboratorio Nacional Argonne . [ 10 ]

La evaluación ingenua y la semiingenua evalúan las reglas recursivas de Datalog aplicándolas repetidamente a un conjunto de hechos conocidos hasta alcanzar un punto fijo. En cada iteración, las reglas se ejecutan solo para "un paso", es decir, de forma no recursiva. Como se mencionó anteriormente , cada regla no recursiva de Datalog corresponde precisamente a una consulta conjuntiva . Por lo tanto, muchas de las técnicas de la teoría de bases de datos utilizadas para acelerar las consultas conjuntivas son aplicables a la evaluación ascendente de Datalog, como

Muchas de estas técnicas se implementan en motores Datalog modernos de abajo hacia arriba, como Soufflé . Algunos motores Datalog integran bases de datos SQL directamente. [ 18 ]

La evaluación ascendente de Datalog también es susceptible de paralelización . Los motores Datalog paralelos generalmente se dividen en dos paradigmas:

Estrategias de evaluación descendentes

La resolución SLD es sólida y completa para los programas Datalog.

Juegos mágicos

Las estrategias de evaluación descendentes comienzan con una consulta o un objetivo . Las estrategias de evaluación ascendentes pueden responder consultas calculando el modelo mínimo completo y comparando la consulta con él, pero esto puede ser ineficiente si la respuesta solo depende de un pequeño subconjunto del modelo completo. El algoritmo de conjuntos mágicos toma un programa Datalog y una consulta, y produce un programa más eficiente que calcula la misma respuesta a la consulta utilizando la evaluación ascendente. [ 24 ] Se ha demostrado que una variante del algoritmo de conjuntos mágicos produce programas que, cuando se evalúan mediante evaluación semiingenua , son tan eficientes como la evaluación descendente. [ 25 ]

Complejidad

La formulación del problema de decisión de la evaluación de Datalog es la siguiente: "Dado un programa Datalog P dividido en un conjunto de hechos (EDB) E y un conjunto de reglas R , y un átomo base A. ¿ Está A en el modelo mínimo de P ?" En esta formulación, hay tres variaciones de la complejidad computacional de evaluar programas Datalog: [ 26 ]

  • La complejidad de los datos es la complejidad del problema de decisión cuando A y E son entradas y R es fijo.
  • La complejidad del programa es la complejidad del problema de decisión cuando A y R son entradas y E es fijo.
  • La complejidad combinada es la complejidad del problema de decisión cuando A , E y R son entradas.

En cuanto a la complejidad de los datos, el problema de decisión para Datalog es P-completo (véase el Teorema 4.4 en [ 26 ] ). La P-completitud para la complejidad de los datos implica que existe una consulta Datalog fija cuya evaluación es P-completa. La demostración se basa en el metaintérprete Datalog para programas de lógica proposicional.

Con respecto a la complejidad del programa, el problema de decisión es EXPTIME-completo . En particular, la evaluación de programas Datalog siempre termina; Datalog no es Turing-completo .

Algunas extensiones de Datalog no conservan estos límites de complejidad. Las extensiones implementadas en algunos motores de Datalog , como los tipos de datos algebraicos, pueden incluso hacer que el lenguaje resultante sea Turing-completo.

Extensiones

Se han realizado varias extensiones a Datalog, por ejemplo, para admitir la negación, las funciones agregadas , las desigualdades, la programación orientada a objetos o las disyunciones como cabezas de cláusulas . Estas extensiones tienen un impacto significativo en la semántica del lenguaje y en la implementación del intérprete correspondiente.

Datalog es un subconjunto sintáctico de Prolog , Datalog disyuntivo , programación de conjuntos de respuestas , DatalogZ y programación lógica con restricciones . Cuando se evalúa como un programa de conjuntos de respuestas, un programa Datalog produce un único conjunto de respuestas, que es precisamente su modelo mínimo. [ 27 ]

Muchas implementaciones de Datalog amplían Datalog con funciones adicionales; consulte la sección "  Motores de Datalog" para obtener más información.

Agregación

Datalog se puede extender para admitir funciones de agregación . [ 28 ]

Entre los motores Datalog más destacados que implementan la agregación se incluyen:

Negación

Agregar la negación a Datalog complica su semántica, lo que da lugar a lenguajes y estrategias de evaluación completamente nuevos. Por ejemplo, el lenguaje que resulta de agregar la negación con la semántica del modelo estable es precisamente la programación de conjuntos de respuestas .

La negación estratificada se puede agregar a Datalog conservando su semántica de punto fijo y basada en la teoría de modelos. Algunos motores Datalog destacados que implementan la negación estratificada son:

Comparación con Prolog

A diferencia de Prolog , las instrucciones de un programa Datalog pueden escribirse en cualquier orden. Datalog no tiene el operador de corte de Prolog . Esto convierte a Datalog en un lenguaje totalmente declarativo .

A diferencia de Prolog, Datalog

  • no permite términos complejos como argumentos de predicados , por ejemplo, p(x, y)es admisible pero no p(f(x), y),
  • prohíbe la negación,
  • requiere que cada variable que aparece en la cabeza de una cláusula también aparezca en un literal en el cuerpo de la cláusula.

Este artículo trata principalmente sobre Datalog sin negación (véase también Sintaxis y semántica de la programación lógica §  Negación ). Sin embargo, la negación estratificada es una adición común a Datalog; la siguiente lista compara Prolog con Datalog con negación estratificada. Datalog con negación estratificada

  • también prohíbe los términos complejos como argumentos de predicados ,
  • requiere que cada variable que aparece en la cabeza de una cláusula también aparezca en un átomo positivo (es decir, no negado) en el cuerpo de la cláusula,
  • requiere que cada variable que aparece en un literal negativo en el cuerpo de una cláusula también aparezca en algún literal positivo en el cuerpo de la cláusula. [ 31 ]

Expresividad

Datalog generaliza muchos otros lenguajes de consulta. Por ejemplo, las consultas conjuntivas y la unión de consultas conjuntivas se pueden expresar en Datalog. Datalog también puede expresar consultas de ruta regulares .

Cuando consideramos bases de datos ordenadas , es decir, bases de datos con una relación de orden en su dominio activo , entonces el teorema de Immerman-Vardi implica que el poder expresivo de Datalog es precisamente el de la clase PTIME : una propiedad puede expresarse en Datalog si y solo si es computable en tiempo polinomial. [ 32 ]

El problema de acotación para Datalog plantea, dado un programa Datalog, si está acotado , es decir, si la profundidad máxima de recursión alcanzada al evaluar el programa en una base de datos de entrada puede acotarse mediante alguna constante. En otras palabras, esta pregunta plantea si el programa Datalog podría reescribirse como un programa Datalog no recursivo o, equivalentemente, como una unión de consultas conjuntivas . Resolver el problema de acotación en programas Datalog arbitrarios es indecidible [ 33 ] , pero puede hacerse decidible restringiéndolo a algunos fragmentos de Datalog.

Motores de registro de datos

Los sistemas que implementan lenguajes inspirados en Datalog, ya sean compiladores , intérpretes , bibliotecas o DSL integrados , se denominan motores Datalog . Estos motores suelen implementar extensiones de Datalog, añadiendo tipos de datos adicionales , interfaces de funciones externas o compatibilidad con retículos definidos por el usuario . Dichas extensiones pueden permitir la escritura de programas no terminantes o mal definidos.

Aquí hay una breve lista de sistemas que se basan en Datalog o que proporcionan un intérprete de Datalog:

Software libre/código abierto

Software no libre

  • FoundationDB proporciona una vinculación de base de datos gratuita para pyDatalog, con un tutorial sobre su uso. [ 38 ]
  • Leapsight Semantic Dataspace (LSD) es una base de datos deductiva distribuida que ofrece alta disponibilidad, tolerancia a fallos, simplicidad operativa y escalabilidad. LSD utiliza Leaplog (una implementación de Datalog) para consultas y razonamiento, y fue creada por Leapsight. [ 39 ]
  • LogicBlox , una implementación comercial de Datalog utilizada para aplicaciones web de planificación minorista y seguros.
  • Profium Sense es una base de datos gráfica nativa compatible con RDF escrita en Java. Proporciona soporte para la evaluación de reglas definidas por el usuario mediante Datalog.
  • .QL , una variante comercial orientada a objetos de Datalog creada por Semmle para analizar el código fuente y detectar vulnerabilidades de seguridad. [ 40 ]
  • SecPAL es un lenguaje de políticas de seguridad desarrollado por Microsoft Research . [ 41 ]
  • Stardog es una base de datos de grafos , implementada en Java . Ofrece soporte para RDF y todos los perfiles OWL 2 , proporcionando amplias capacidades de razonamiento, incluida la evaluación de registros de datos.
  • StrixDB: un almacén de grafos RDF comercial, compatible con SPARQL , con API Lua y capacidades de inferencia Datalog. Puede utilizarse como módulo de httpd ( servidor HTTP Apache ) o de forma independiente (aunque las versiones beta están bajo la Licencia Artística Perl 2.0).

Usos e influencia

Datalog es bastante limitado en su expresividad. No es Turing-completo y no incluye tipos de datos básicos como enteros o cadenas . Esta parsimonia resulta atractiva desde un punto de vista teórico, pero implica que Datalog en sí mismo rara vez se utiliza como lenguaje de programación o lenguaje de representación del conocimiento . [ 42 ] La mayoría de los motores Datalog implementan extensiones sustanciales de Datalog. Sin embargo, Datalog ejerce una fuerte influencia en dichas implementaciones, y muchos autores no se molestan en distinguirlas de Datalog tal como se presenta en este artículo. Por consiguiente, las aplicaciones analizadas en esta sección incluyen aplicaciones de implementaciones realistas de lenguajes basados ​​en Datalog.

Datalog se ha aplicado a problemas de integración de datos , extracción de información , redes , seguridad , computación en la nube y aprendizaje automático . [ 43 ] [ 44 ] Google ha desarrollado una extensión de Datalog para el procesamiento de big data . [ 45 ]

Datalog se ha aplicado en el análisis estático de programas . [ 46 ] El dialecto Soufflé se ha utilizado para escribir análisis de punteros para Java y un análisis de flujo de control para Scheme . [ 47 ] [ 48 ] Datalog se ha integrado con solucionadores SMT para facilitar la escritura de ciertos análisis estáticos. [ 49 ] El dialecto Flix también es adecuado para escribir análisis estáticos de programas. [ 50 ]

Algunos sistemas de bases de datos ampliamente utilizados incluyen ideas y algoritmos desarrollados para Datalog. Por ejemplo, el estándar SQL:1999 incluye consultas recursivas , y el algoritmo Magic Sets (desarrollado inicialmente para la evaluación más rápida de consultas Datalog) está implementado en DB2 de IBM . [ 51 ]

Historia

Los orígenes de Datalog se remontan a los inicios de la programación lógica , pero cobró relevancia como área independiente alrededor de 1977, cuando Hervé Gallaire y Jack Minker organizaron un taller sobre lógica y bases de datos . [ 52 ] Se atribuye a David Maier la creación del término Datalog. [ 53 ]

Véase también

Notas

  1. ^ Ceri , Gottlob y Tanca 1989 , pág. 146.
  2. ^ Eisner, Jason; Filardo, Nathaniel W. (2011). "Dyna: ampliación del registro de datos para la IA moderna" . En de Moor, Oege; Gottlob, Georg; Furche, Tim; Vendedores, Andrew (eds.). Registro de datos recargado . Apuntes de conferencias sobre informática. vol.  6702. Berlín, Heidelberg: Springer. págs. 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. (1 de septiembre de 2018), "Datalog: conceptos, historia y perspectivas" , Programación lógica declarativa: teoría, sistemas y aplicaciones , vol. 20, Association for Computing Machinery y Morgan & Claypool, pp. 3–100 , doi : 10.1145/3191315.3191317 , ISBN   978-1-970001-99-0, S2CID 69379310 , consultado el 2 de marzo de 2023 
  4. ↑ Van Emden, MH; Kowalski, RA (1976-10-01). "La semántica de la lógica de predicados como lenguaje de programación" . Journal of the ACM . 23 (4): 733– 742. doi : 10.1145/321978.321991 . ISSN 0004-5411 . S2CID 11048276 .  
  5. ^ Ceri, Gottlob y Tanca 1989 , pág. 149.
  6. ^ Ceri, Gottlob y Tanca 1989 , pág. 150.
  7. ^ Ceri, Gottlob y Tanca 1989 , pág. 154.
  8. ↑ Alvarez-Picallo, Mario; Eyers-Taylor, Alex; Peyton Jones, Michael; Ong, C.-H. Luke (2019). "Fixing Incremental Computation: Derivatives of Fixpoints, and the Recursive Semantics of Datalog" . En Caires, Luís (ed.). Programming Languages ​​and Systems . Lecture Notes in Computer Science. Vol. 11423. Cham: Springer International Publishing. pp. 525–552 . doi : 10.1007/978-3-030-17184-1_19 . ISBN   978-3-030-17184-1. S2CID 53430789 . 
  9. ↑ Willsey, Max. "Datalog" . Análisis y optimización de programas declarativos CS294-260, primavera de 2024. Consultado el 15 de mayo de 2026 .
  10. 1 2 Gilray, Thomas; Sahebolamri, Arash; Kumar, Sidharth; Micinski, Kristopher (2022-11-21). "Deducción estructurada paralela de datos de orden superior". arXiv : 2211.11573 [ cs.PL ].
  11. ↑ Subotić, Pavle; Jordan, Herbert; Chang, Lijun; Fekete, Alan; Scholz, Bernhard (2018-10-01). "Selección automática de índices para el cálculo de datalog a gran escala" . Actas de la Fundación VLDB . 12 (2): 141– 153. doi : 10.14778/3282495.3282500 . ISSN 2150-8097 . S2CID 53569679 .  
  12. ↑ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (18 de junio de 2017). «Porting doop to Soufflé» . Actas del 6.º Taller Internacional ACM SIGPLAN sobre el Estado del Arte en el Análisis de Programas . SOAP 2017. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 25-30 . doi : 10.1145/3088515.3088522 . ISBN  978-1-4503-5072-3. S2CID 3074689 . "El motor LogicBlox realiza una optimización completa de las consultas."
  13. ↑ Arch, Samuel; Hu, Xiaowen; Zhao, David; Subotić, Pavle; Scholz, Bernhard (2022). "Construyendo un optimizador de unión para Soufflé" . En Villanueva, Alicia (ed.). Síntesis y transformación de programas basados ​​en lógica . Lecture Notes in Computer Science. Vol. 13474. Cham: Springer International Publishing. pp. 83–102 . doi : 10.1007/978-3-031-16767-6_5 . ISBN   978-3-031-16767-6.
  14. ↑ Nappa, Patrick; Zhao, David; Subotic, Pavle; Scholz, Bernhard (2019). "Relaciones de equivalencia paralelas rápidas en un compilador Datalog". 2019 28.ª Conferencia Internacional sobre Arquitecturas Paralelas y Técnicas de Compilación (PACT) . pp. 82–96 . doi : 10.1109/PACT.2019.00015 . ISBN  978-1-7281-3613-4. S2CID 204827819 . 
  15. ↑ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (17 de febrero de 2019). «Brie: Un Trie especializado para Datalog concurrente» . Actas del 10.º Taller Internacional sobre Modelos de Programación y Aplicaciones para Multicore y Manycore . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 31–40 . doi : 10.1145/3303084.3309490 . ISBN  978-1-4503-6290-0. S2CID 239258588 . 
  16. ↑ Whaley, John; Avots, Dzintars; Carbin, Michael; Lam, Monica S. (2005). "Uso de Datalog con diagramas de decisión binarios para el análisis de programas" . En Yi, Kwangkeun (ed.). Lenguajes y sistemas de programación . Lecture Notes in Computer Science. Vol. 3780. Berlín, Heidelberg: Springer. pp. 97–118 . doi : 10.1007/11575467_8 . ISBN   978-3-540-32247-4. S2CID 5223577 . 
  17. ↑ Hoder, Kryštof; Bjørner, Nikolaj; de Moura, Leonardo (2011). "μZ – un motor eficiente para puntos fijos con restricciones" . En Gopalakrishnan, Ganesh; Qadeer, Shaz (eds.). Verificación asistida por computadora . Lecture Notes in Computer Science. Vol. 6806. Berlín, Heidelberg: Springer. pp. 457–462 . doi : 10.1007/978-3-642-22110-1_36 . ISBN   978-3-642-22110-1.
  18. ↑ 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 ].
  19. ↑ Shovon, Ahmedur Rahman; Dyken, Landon Richard; Green, Oded; Gilray, Thomas; Kumar, Sidharth (noviembre de 2022). "Aceleración de aplicaciones Datalog con cuDF". Taller IEEE/ACM de 2022 sobre aplicaciones irregulares: arquitecturas y algoritmos (IA3) . IEEE. págs. 41–45 . doi : 10.1109/IA356718.2022.00012 . ISBN  978-1-6654-7506-8. S2CID 256565728 . 
  20. ↑ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (16 de febrero de 2019). «Un árbol B especializado para la evaluación concurrente de registros de datos» . Actas del 24.º Simposio sobre Principios y Práctica de la Programación Paralela . PPoPP '19. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 327–339 . doi : 10.1145/3293883.3295719 . ISBN  978-1-4503-6225-2. S2CID 59617209 . 
  21. ↑ Wu, Jiacheng; Wang, Jin; Zaniolo, Carlo (11 de junio de 2022). «Optimización de la evaluación recursiva paralela de Datalog en máquinas multinúcleo» . Actas de la Conferencia Internacional de Gestión de Datos de 2022. SIGMOD '22. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1433–1446 . doi : 10.1145/3514221.3517853 . ISBN  978-1-4503-9249-5. S2CID 249578825 . Estos enfoques implementan la idea de evaluación paralela ascendente dividiendo las tablas en particiones disjuntas mediante funciones discriminantes, como el hash, donde cada partición se asigna a uno de los trabajadores paralelos. Después de cada iteración, los trabajadores se coordinan entre sí para intercambiar las tuplas recién generadas cuando sea necesario.
  22. ↑ Shaw, Marianne; Koutris, Paraschos; Howe, Bill; Suciu, Dan (2012). "Optimizing Large-Scale Semi-Naïve Datalog Evaluation in Hadoop" . En Barceló, Pablo; Pichler, Reinhard (eds.). Datalog in Academia and Industry . Lecture Notes in Computer Science. Vol. 7494. Berlín, Heidelberg: Springer. pp. 165–176 . doi : 10.1007/978-3-642-32925-8_17 . ISBN   978-3-642-32925-8.
  23. ↑ Shkapsky, Alexander; Yang, Mohan; Interlandi, Matteo; Chiu, Hsuan; Condie, Tyson; Zaniolo, Carlo (14 de junio de 2016). "Análisis de Big Data con consultas Datalog en Spark" . Actas de la Conferencia Internacional de Gestión de Datos de 2016. SIGMOD '16. Vol. 2016. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1135–1149 . doi : 10.1145/2882903.2915229 . ISBN   978-1-4503-3531-7. PMC 5470845 . PMID 28626296 .  
  24. ↑ Balbin, I.; Port, GS; Ramamohanarao, K.; Meenakshi, K. (1991-10-01). "Cálculo eficiente de consultas de abajo hacia arriba en bases de datos estratificadas" . The Journal of Logic Programming . 11 (3): 295– 344. doi : 10.1016/0743-1066(91)90030-S . ISSN 0743-1066 . 
  25. ↑ Ullman, JD (29 de marzo de 1989). "El enfoque ascendente supera al descendente en datalog" . Actas del octavo simposio ACM SIGACT-SIGMOD-SIGART sobre Principios de los sistemas de bases de datos - PODS '89 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 140-149 . doi : 10.1145/73721.73736 . ISBN  978-0-89791-308-9. S2CID 13269547 . 
  26. 1 2 Dantsin, Evgeny; Eiter, Thomas; Gottlob, Georg; Voronkov, Andrei (2001-09-01). "Complejidad y poder expresivo de la programación lógica" . ACM Computing Surveys . 33 (3): 374– 425. doi : 10.1145/502807.502810 . ISSN 0360-0300 . 
  27. ↑ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (2023-01-11). "De SMT a ASP: Enfoques basados ​​en solucionadores para resolver problemas de síntesis de Datalog como selección de reglas" . Actas de la ACM sobre lenguajes de programación . 7 (POPL): 7:185–7:217. doi : 10.1145/3571200 . S2CID 253525805 . 
  28. ↑ Zaniolo, Carlo; Yang, Mohan; Das, Ariyam; Shkapsky, Alexander; Condie, Tyson; Interlandi, Matteo (septiembre de 2017). "Semántica de punto fijo y optimización de programas Datalog recursivos con agregados*" . Theory and Practice of Logic Programming . 17 ( 5–6 ): 1048–1065 . arXiv : 1707.05681 . doi : 10.1017/S1471068417000436 . ISSN 1471-0684 . S2CID 6272867 .  
  29. ↑ "Capítulo 7. Reglas - Manual de referencia de LogicBlox 3.10" . developer.logicblox.com . Consultado el 4 de marzo de 2023 .
  30. ↑ "6.4. Negación - Manual de referencia de LogicBlox 3.10" . developer.logicblox.com . Consultado el 4 de marzo de 2023 ."Además, la negación solo está permitida cuando la plataforma puede determinar una forma de estratificar todas las reglas y restricciones que utilizan la negación."
  31. ↑ Michael Lam; Dr. Sin Min Lee. "Datalog" . Curso CS 157A . UNIVERSIDAD ESTATAL DE SAN JOSÉ, Departamento de Ciencias de la Computación. Archivado del original el 25 de marzo de 2017.
  32. ↑ Kolaitis, Phokion G.; Vardi, Moshe Y. (1990-04-02). "Sobre el poder expresivo de Datalog: Herramientas y un estudio de caso" . Actas del noveno simposio ACM SIGACT-SIGMOD-SIGART sobre Principios de los sistemas de bases de datos . ACM. págs. 61–71 . doi : 10.1145/298514.298542 . ISBN  978-0-89791-352-2.{{cite book}}: |journal=ignorado ( ayuda )
  33. ↑ Hillebrand, Gerd G; Kanellakis, Paris C; Mairson, Harry G; Vardi, Moshe Y (1995-11-01). "Problemas de acotación indecidibles para programas datalog" . The Journal of Logic Programming . 25 (2): 163– 190. doi : 10.1016/0743-1066(95)00051-K . ISSN 0743-1066 . 
  34. ↑ Saenz-Perez (2011), "DES: Un sistema de base de datos deductivo", Electronic Notes in Theoretical Computer Science , 271 , ES : 63–78 , doi : 10.1016/j.entcs.2011.02.011.
  35. ↑ Flujo de datos diferencial , julio de 2022
  36. ↑ Kenny, Kevin B (12–14 de noviembre de 2014). Diagramas de decisión binarios, álgebra relacional y Datalog: razonamiento deductivo para Tcl (PDF) . Vigésimo primera Conferencia Anual Tcl/Tk. Portland, Oregón . Recuperado el 29 de diciembre de 2015 .
  37. ↑ El sistema XSB, versión 3.7.x, volumen 1: Manual del programador (PDF).
  38. ^ Tutorial de registro de datos de FoundationDB{{citation}}: CS1 maint: servicio de archivado obsoleto ( enlace ) .
  39. ↑ "Leapsight" . Archivado del original el 11 de noviembre de 2018.
  40. ↑ Semmle QL , 18 de septiembre de 2019.
  41. ↑ "SecPAL" . Microsoft Research . Archivado del original el 23 de febrero de 2007.
  42. ↑ Lifschitz, Vladimir. "Fundamentos de la programación lógica." Principios de representación del conocimiento 3 (1996): 69-127. "Las posibilidades expresivas de [Datalog] son ​​demasiado limitadas para aplicaciones significativas en la representación del conocimiento."
  43. ↑ Huang, Green y Loo, "Datalog y aplicaciones emergentes", SIGMOD 2011 (PDF) , UC Davis{{citation}}: CS1 maint: nombres múltiples: lista de autores ( enlace ) .
  44. ↑ 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 .
  45. ^ Barbilla, Brian; Dincklage, Daniel von; Ercegovac, Vuk; Hawkins, Peter; Molinero, Mark S.; Ah, Franz; Olston, Cristóbal; Pereira, Fernando (2015). Bola, Thomas; Bodik, Rastislav; Krishnamurthi, Shriram; Lerner, Benjamín S.; Morrisett, Greg (eds.). Yedalog: Explorando el conocimiento a escala . 1ª Cumbre sobre Avances en Lenguajes de Programación (SNAPL 2015). Procedimientos internacionales de informática de Leibniz (LIPIcs). vol. 32. Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. págs. 63 a 78. doi : 10.4230/LIPIcs.SNAPL.2015.63 . ISBN   978-3-939897-80-4.
  46. ↑ Whaley, John; Avots, Dzintars; Carbin, Michael; Lam, Monica S. (2005). "Uso de Datalog con diagramas de decisión binarios para el análisis de programas" . En Yi, Kwangkeun (ed.). Lenguajes y sistemas de programación . Lecture Notes in Computer Science. Vol. 3780. Berlín, Heidelberg: Springer. pp. 97–118 . doi : 10.1007/11575467_8 . ISBN   978-3-540-32247-4. S2CID 5223577 . 
  47. ↑ Scholz, Bernhard; Jordan, Herbert; Subotić, Pavle; Westmann, Till (17 de marzo de 2016). «Sobre el análisis rápido de programas a gran escala en Datalog» . Actas de la 25.ª Conferencia Internacional sobre Construcción de Compiladores . CC 2016. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 196–206 . doi : 10.1145/2892208.2892226 . ISBN  978-1-4503-4241-4. S2CID 7531543 . 
  48. ↑ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (18 de junio de 2017). «Porting doop to Soufflé» . Actas del 6.º Taller Internacional ACM SIGPLAN sobre el Estado del Arte en el Análisis de Programas . SOAP 2017. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 25-30 . doi : 10.1145/3088515.3088522 . ISBN  978-1-4503-5072-3. S2CID 3074689 . 
  49. ↑ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (2020-11-13). "Formulog: Datalog para análisis estático basado en SMT" . Actas de la ACM sobre lenguajes de programación . 4 (OOPSLA): 141:1–141:31. doi : 10.1145/3428209 . S2CID 226961727 . 
  50. ^ Madsen, Magnus; Sí, Ming-Ho; Lhoták, Ondřej (2 de junio de 2016). "De Datalog a flix: un lenguaje declarativo para puntos fijos en celosías" . Avisos ACM SIGPLAN . 51 (6): 194– 208. doi : 10.1145/2980983.2908096 . ISSN 0362-1340 . 
  51. ↑ Gryz; Guo; Liu; Zuzarte (2004). "Muestreo de consultas en la base de datos universal DB2" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 2004 sobre gestión de datos - SIGMOD '04 . pág. 839. doi : 10.1145/1007568.1007664 . ISBN  978-1581138597. S2CID 7775190 . 
  52. ^ Gallaire, Hervé; Minker, John 'Jack', eds. (1978), "Lógica y bases de datos, Simposio sobre lógica y bases de datos, Centre d'études et de recherches de Toulouse, 1977", Avances en la teoría de las bases de datos , Nueva York: Plenum Press, ISBN 978-0-306-40060-5.
  53. ↑ Abiteboul, Serge ; Hull, Richard; Vianu, Victor (1995), Fundamentos de bases de datos , Addison-Wesley, pág. 305, ISBN  9780201537710.

Referencias

  • Ceri, S.; Gottlob, G.; Tanca, L. (marzo de 1989). "Lo que siempre quisiste saber sobre Datalog (y nunca te atreviste a preguntar)" (PDF) . IEEE Transactions on Knowledge and Data Engineering . 1 (1): 146– 166. Bibcode : 1989ITKDE...1..146C . CiteSeerX 10.1.1.210.1118 . doi : 10.1109/69.43410 . ISSN 1041-4347 .  
  • Abiteboul, S. (1995). Fundamentos de las bases de datos . Richard Hull, Victor Vianu. Reading, Mass.: Addison-Wesley. ISBN 0-201-53771-0OCLC 30546436 .​ 
Obtenido de " https://en.wikipedia.org/w/index.php?title=Datalog&oldid=1360645844 "