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 un padre de brooke y brooke es un padre de damocles :
padre ( xerces , brooke ). padre ( brooke , damocles ).
Los nombres se escriben en minúsculas porque las cadenas que comienzan con mayúscula representan variables. A continuación se indican 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 "y", por lo que estas reglas significan:
X es un ancestro de Y si X es un padre de Y.
X es un ancestro de Y si X es un padre de algún Z, y Z es un ancestro de Y.
El significado de un programa se define como el conjunto de todos los hechos que se pueden deducir a partir de los hechos iniciales y las reglas. El significado de este programa viene dado por los siguientes hechos:
Algunas implementaciones de Datalog no deducen todos los hechos posibles, sino que responden consultas :
?- ancestro ( xerces , X ).
Esta consulta pregunta: ¿Quiénes son todos los X de los que xerces es antepasado? 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 una correlación entre Datalog, álgebra relacional y conceptos de SQL :
De manera más formal, el registro de datos no recursivo corresponde precisamente a las uniones de consultas conjuntivas o, equivalentemente, al álgebra relacional libre de negación.
Sintaxis
Un programa Datalog consta de una lista de reglas ( cláusulas de Horn ). [1] Si constante y variable son dos conjuntos contables de constantes y variables respectivamente y relación es un conjunto contable de símbolos de predicado , entonces la siguiente gramática BNF expresa la estructura de un programa Datalog:
Los átomos también se conocen como literales . El átomo a la izquierda del :-símbolo se denomina cabeza de la regla; los átomos a la derecha son el cuerpo . Todo programa Datalog debe satisfacer 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: poner las variables en mayúscula o anteponerles un signo de interrogación ?. [3]
Tenga en cuenta que, según esta definición, Datalog no incluye negación ni agregados; consulte § 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:
y ( x ) :- .
El conjunto de hechos se denomina base de datos extensional o EDB del programa Datalog. El conjunto de tuplas calculadas mediante la evaluación del 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 :-, de la siguiente manera:
r ( x ).
Algunos también permiten escribir relaciones 0-arias sin paréntesis, como así:
p :- q .
Éstas son simplemente abreviaturas ( azúcar sintáctica ); 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: teoría de modelos , punto fijo y teoría de pruebas . Estos tres enfoques pueden demostrarse 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, a partir de los hechos.
Teoría de modelos
Una regla se denomina fundamental si todos sus átomos (cabeza y cuerpo) son fundamentales. Una regla fundamental R 1 es una instancia fundamental de otra regla R 2 si R 1 es el resultado de una sustitución de constantes por todas las variables en R 2 . La base de Herbrand de un programa Datalog es el conjunto de todos los átomos fundamentales que se pueden crear 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 de modo 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 función T de I a I que suma todos los nuevos átomos base que se pueden derivar de las reglas del programa en un solo paso. La semántica del punto mínimo fijo define el punto mínimo fijo 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: comenzar con el conjunto de hechos básicos del programa y luego agregar repetidamente consecuencias de las reglas hasta que se alcance un punto fijo. Este algoritmo se denomina evaluación ingenua.
Teoría de la prueba
Árbol de pruebas 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 teoría de pruebas define el significado de un programa Datalog como el conjunto de hechos con sus correspondientes árboles de pruebas . De manera intuitiva, un árbol de pruebas muestra cómo derivar un hecho a partir de los hechos y las reglas de un programa.
A uno le podría interesar saber si un átomo fundamental en particular aparece o no en el modelo mínimo de Herbrand de un programa Datalog, tal vez sin preocuparse demasiado por el resto del modelo. Una lectura de arriba hacia abajo de los árboles de prueba descritos anteriormente sugiere un algoritmo para calcular los resultados de dichas consultas . Esta lectura informa el algoritmo de resolución SLD , que forma la base para la evaluación de Prolog .
Evaluación
Hay muchas formas diferentes de evaluar un programa Datalog, con diferentes características de rendimiento.
Estrategias de evaluación de abajo hacia arriba
Las estrategias de evaluación de abajo hacia arriba comienzan con los hechos del programa y aplican las reglas repetidamente hasta que se establece algún objetivo o 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 de 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 en el programa. Si cada átomo en el cuerpo de la instancia básica está en el conjunto de hechos conocidos, entonces el átomo principal se agrega al conjunto de hechos conocidos. Este proceso se repite hasta que se alcanza un punto fijo y no se pueden deducir más hechos. La evaluación ingenua produce el modelo mínimo completo del programa. [7]
Evaluación semi-ingenua
La evaluación semiingenua es una estrategia de evaluación de abajo hacia arriba que puede ser asintóticamente más rápida que la evaluación ingenua. [8]
Tanto la evaluación ingenua como la semiingenua evalúan las reglas recursivas de Datalog aplicándolas repetidamente a un conjunto de hechos conocidos hasta que se alcanza un punto fijo. En cada iteración, las reglas solo se ejecutan 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 los motores de registro de datos de abajo a arriba modernos, como Soufflé . Algunos motores de registro de datos integran bases de datos SQL directamente. [17]
La evaluación ascendente de Datalog también se puede realizar en paralelo . Los motores de Datalog paralelos se dividen generalmente en dos paradigmas:
Los motores de registro de datos que utilizan OpenMP [19] son instancias del paradigma MIMD.
En la configuración de no compartir , los motores Datalog se ejecutan en un grupo de nodos. Dichos motores generalmente operan dividiendo las relaciones en subconjuntos disjuntos en función de una función hash , realizando cálculos (uniones) en cada nodo y luego intercambiando tuplas recién generadas a través de la red. [20] Algunos ejemplos incluyen motores Datalog basados en MPI , [9] Hadoop , [21] y Spark . [22]
Las estrategias de evaluación de arriba hacia abajo comienzan con una consulta o un objetivo . Las estrategias de evaluación de abajo hacia arriba pueden responder a las consultas calculando todo el modelo mínimo y haciendo coincidir 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 mientras sigue utilizando la evaluación de abajo hacia arriba. [23] Se ha demostrado que una variante del algoritmo de conjuntos mágicos produce programas que, cuando se evalúan utilizando una evaluación semiingenua, son tan eficientes como la evaluación de arriba hacia abajo. [24]
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 la evaluación de programas Datalog: [25]
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.
Con respecto a la complejidad de los datos, el problema de decisión para Datalog es P-completo . Con respecto a la complejidad del programa, el problema de decisión es EXPTIME-completo . En particular, la evaluación de los 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 ampliaciones a Datalog, por ejemplo, para admitir la negación, las funciones agregadas , las desigualdades, para permitir la programación orientada a objetos o para permitir disyunciones como encabezados de cláusulas . Estas ampliaciones tienen un impacto significativo en la semántica del lenguaje y en la implementación de un intérprete correspondiente.
A diferencia de Prolog , las instrucciones de un programa Datalog se pueden indicar en cualquier orden. Datalog no tiene el operador de corte de Prolog . Esto hace que Datalog sea un lenguaje completamente 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),
no permite la negación,
requiere que cada variable que aparece en el encabezado de una cláusula también aparezca en un literal en el cuerpo de la cláusula.
También rechaza términos complejos como argumentos de predicados ,
requiere que cada variable que aparece en el encabezado 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. [30] [ ¿ fuente poco confiable? ]
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 sólo si es computable en tiempo polinomial. [31]
El problema de acotación para Datalog pregunta, dado un programa Datalog, si está acotado , es decir, la profundidad de recursión máxima alcanzada al evaluar el programa en una base de datos de entrada puede estar acotada por alguna constante. En otras palabras, esta pregunta pregunta si el programa Datalog podría reescribirse como un programa Datalog no recursivo o, equivalentemente, como una unión de consultas conjuntivas . La solución del problema de acotación en programas Datalog arbitrarios es indecidible , [32] pero puede hacerse decidible restringiéndolo a algunos fragmentos de Datalog.
A continuación se muestra una breve lista de sistemas que se basan en Datalog o proporcionan un intérprete de Datalog:
Software libre/código abierto
Software no libre
FoundationDB proporciona un enlace de base de datos gratuito para pyDatalog, con un tutorial sobre su uso. [37]
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. [38]
LogicBlox , una implementación comercial de Datalog utilizada para aplicaciones de planificación minorista y de seguros basadas en la web.
Profium Sense es una base de datos gráfica nativa compatible con RDF escrita en Java. Proporciona compatibilidad con la evaluación de registros de datos de reglas definidas por el usuario.
.QL , una variante comercial orientada a objetos de Datalog creada por Semmle para analizar el código fuente con el fin de detectar vulnerabilidades de seguridad. [39]
Stardog es una base de datos gráfica implementada en Java . Ofrece compatibilidad con RDF y todos los perfiles OWL 2, lo que proporciona amplias capacidades de razonamiento, incluida la evaluación de registros de datos.
StrixDB: un almacén de gráficos RDF comercial, compatible con SPARQL , con API de Lua y capacidades de inferencia de registros de datos. Puede utilizarse como módulo httpd ( servidor HTTP Apache ) o de forma independiente (aunque las versiones beta están sujetas a la licencia Perl Artistic License 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 números enteros o cadenas . Esta parsimonia es atractiva desde un punto de vista teórico, pero significa que Datalog per se rara vez se utiliza como lenguaje de programación o lenguaje de representación de conocimiento . [41] La mayoría de los motores Datalog implementan extensiones sustanciales de Datalog. Sin embargo, Datalog tiene una fuerte influencia en dichas implementaciones y muchos autores no se molestan en distinguirlas de Datalog como se presenta en este artículo. En consecuencia, las aplicaciones discutidas en esta sección incluyen aplicaciones de implementaciones realistas de lenguajes basados en Datalog.
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 (inicialmente desarrollado para la evaluación más rápida de consultas Datalog) está implementado en DB2 de IBM . [50]
Historia
Los orígenes de Datalog se remontan al comienzo de la programación lógica , pero se volvió prominente como un área separada alrededor de 1977 cuando Hervé Gallaire y Jack Minker organizaron un taller sobre lógica y bases de datos . [51] A David Maier se le atribuye la creación del término Datalog. [52]
^ Eisner, Jason; Filardo, Nathaniel W. (2011). "Dyna: Extendiendo Datalog para la IA moderna". En de Moor, Oege; Gottlob, Georg; Furche, Tim; Sellers, Andrew (eds.). Datalog Reloaded . Apuntes de clase en Ciencias de la Computación. 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.
^ 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, págs. 3–100, doi :10.1145/3191315.3191317, ISBN978-1-970001-99-0, S2CID 69379310 , consultado el 2 de marzo de 2023
^ Van Emden, MH; Kowalski, RA (1976-10-01). "La semántica de la lógica de predicados como lenguaje de programación". Revista de la ACM . 23 (4): 733–742. doi : 10.1145/321978.321991 . ISSN 0004-5411. S2CID 11048276.
^ Ceri, Gottlob y Tanca 1989, pág. 149.
^ Ceri, Gottlob y Tanca 1989, pág. 150.
^ Ceri, Gottlob y Tanca 1989, pág. 154.
^ Alvarez-Picallo, Mario; Eyers-Taylor, Alex; Peyton Jones, Michael; Ong, C.-H. Luke (2019). "Fijación de la computación incremental: derivadas de puntos fijos y la semántica recursiva de Datalog". En Caires, Luís (ed.). Lenguajes y sistemas de programación . Apuntes de clase en informática. Vol. 11423. Cham: Springer International Publishing. págs. 525–552. doi :10.1007/978-3-030-17184-1_19. ISBN .978-3-030-17184-1. Número de identificación del sujeto 53430789.
^ ab Gilray, Thomas; Sahebolamri, Arash; Kumar, Sidharth; Micinski, Kristopher (21 de noviembre de 2022). "Deducción estructurada de orden superior y datos paralelos". arXiv : 2211.11573 [cs.PL].
^ Subotić, Pavle; Jordan, Herbert; Chang, Lijun; Fekete, Alan; Scholz, Bernhard (1 de octubre de 2018). "Selección automática de índices para el cálculo de registros de datos a gran escala". Actas de la Fundación VLDB . 12 (2): 141–153. doi :10.14778/3282495.3282500. ISSN 2150-8097. S2CID 53569679.
^ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (18 de junio de 2017). "Transferencia de doop a Soufflé". Actas del 6.º Taller internacional ACM SIGPLAN sobre el estado del arte en 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. Número de identificación del sujeto 3074689."El motor LogicBlox realiza una optimización completa de las consultas".
^ Arch, Samuel; Hu, Xiaowen; Zhao, David; Subotić, Pavle; Scholz, Bernhard (2022). "Construcción de un optimizador de uniones para Soufflé". En Villanueva, Alicia (ed.). Síntesis y transformación de programas basados en lógica . Apuntes de clase en informática. Vol. 13474. Cham: Springer International Publishing. págs. 83–102. doi :10.1007/978-3-031-16767-6_5. ISBN978-3-031-16767-6.
^ Nappa, Patrick; Zhao, David; Subotic, Pavle; Scholz, Bernhard (2019). "Relaciones de equivalencia rápida en paralelo en un compilador de registro de datos". 2019 28.ª Conferencia internacional sobre arquitecturas paralelas y técnicas de compilación (PACT) . págs. 82–96. doi :10.1109/PACT.2019.00015. ISBN .978-1-7281-3613-4. S2CID 204827819 . Consultado el 28 de noviembre de 2023 .
^ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (17 de febrero de 2019). "Brie: un trie especializado para registros de datos concurrentes". Actas del 10.º Taller internacional sobre modelos de programación y aplicaciones para núcleos múltiples y muchos núcleos . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 31–40. doi :10.1145/3303084.3309490. ISBN978-1-4503-6290-0. Número de identificación del sujeto 239258588.
^ 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 . Apuntes de clase en informática. Vol. 3780. Berlín, Heidelberg: Springer. págs. 97–118. doi :10.1007/11575467_8. ISBN978-3-540-32247-4.S2CID 5223577 .
^ 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 . Apuntes de clase en informática. Vol. 6806. Berlín, Heidelberg: Springer. págs. 457–462. doi :10.1007/978-3-642-22110-1_36. ISBN978-3-642-22110-1.
^ Fan, Zhiwei; Zhu, Jianqiao; Zhang, Zuyu; Albarghouthi, Aws; Koutris, Paraschos; Patel, Jignesh (10 de diciembre de 2018). "Aumento del procesamiento de registros de datos en memoria: observaciones y técnicas". arXiv : 1812.03975 [cs.DB].
^ Shovon, Ahmedur Rahman; Dyken, Landon Richard; Green, Oded; Gilray, Thomas; Kumar, Sidharth (noviembre de 2022). "Aceleración de aplicaciones de registro de datos 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.S2CID256565728 .
^ 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ácticas de 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.S2CID59617209 .
^ Wu, Jiacheng; Wang, Jin; Zaniolo, Carlo (11 de junio de 2022). "Optimización de la evaluación recursiva paralela de registros de datos en máquinas multinúcleo". Actas de la Conferencia internacional de 2022 sobre gestión de datos . SIGMOD '22. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1433–1446. doi :10.1145/3514221.3517853. ISBN978-1-4503-9249-5.S2CID249578825 ."Estos enfoques implementan la idea de la evaluación ascendente paralela dividiendo las tablas en particiones disjuntas mediante funciones de discriminación, 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 tuplas recién generadas cuando es necesario.
^ Shaw, Marianne; Koutris, Paraschos; Howe, Bill; Suciu, Dan (2012). "Optimización de la evaluación de registros de datos semi-ingenuos a gran escala en Hadoop". En Barceló, Pablo; Pichler, Reinhard (eds.). Datalog in Academia and Industry . Lecture Notes in Computer Science. Vol. 7494. Berlín, Heidelberg: Springer. págs. 165–176. doi :10.1007/978-3-642-32925-8_17. ISBN978-3-642-32925-8.
^ Shkapsky, Alexander; Yang, Mohan; Interlandi, Matteo; Chiu, Hsuan; Condie, Tyson; Zaniolo, Carlo (14 de junio de 2016). "Big Data Analytics with Datalog Queries on Spark". Actas de la Conferencia internacional de 2016 sobre gestión de datos . 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.
^ Balbin, I.; Port, GS; Ramamohanarao, K.; Meenakshi, K. (1991-10-01). "Cálculo eficiente de abajo a arriba de consultas 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.
^ Ullman, JD (29 de marzo de 1989). "Bottom-up beats top-down for datalog". Actas del octavo simposio ACM SIGACT-SIGMOD-SIGART sobre Principios de 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.S2CID13269547 .
^ Dantsin, Evgeny; Eiter, Thomas; Gottlob, Georg; Voronkov, Andrei (1 de septiembre de 2001). "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.
^ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (11 de enero de 2023). "De SMT a ASP: enfoques basados en solucionadores para resolver problemas de síntesis de registros de datos 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.
^ Zaniolo, Carlo; Yang, Mohan; Das, Ariyam; Shkapsky, Alexander; Condie, Tyson; Interlandi, Matteo (septiembre de 2017). "Semántica de puntos fijos y optimización de programas Datalog recursivos con agregados*". Teoría y práctica de la programación lógica . 17 (5–6): 1048–1065. arXiv : 1707.05681 . doi :10.1017/S1471068417000436. ISSN 1471-0684. S2CID 6272867.
^ "Capítulo 7. Reglas - Manual de referencia de LogicBlox 3.10". developer.logicblox.com . Consultado el 4 de marzo de 2023 .
^ "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 sólo se permite cuando la plataforma puede determinar una forma de estratificar todas las reglas y restricciones que utilizan la negación".
^ Michael Lam; Dr. Sin Min Lee. "Datalog". Curso CS 157A . UNIVERSIDAD ESTATAL DE SAN JOSÉ, Departamento de Ciencias de la Computación. Archivado desde el original el 25 de marzo de 2017.
^ Kolaitis, Phokion G.; Vardi, Moshe Y. (2 de abril de 1990). "Sobre el poder expresivo de los registros de datos: 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. ISBN978-0-89791-352-2. {{cite book}}: |journal=ignorado ( ayuda )
^ Hillebrand, Gerd G; Kanellakis, Paris C; Mairson, Harry G; Vardi, Moshe Y (1995-11-01). "Problemas de acotación indecidible para programas de registro de datos". Revista de programación lógica . 25 (2): 163–190. doi : 10.1016/0743-1066(95)00051-K . ISSN 0743-1066.
^ Saenz-Pérez (2011), "DES: Un sistema de base de datos deductivo", Notas electrónicas en informática teórica , 271 , ES : 63–78, doi : 10.1016/j.entcs.2011.02.011.
^ Flujo de datos diferencial, julio de 2022
^ Kenny, Kevin B (12–14 de noviembre de 2014). Diagramas de decisión binaria, álgebra relacional y Datalog: razonamiento deductivo para Tcl (PDF) . Vigésima primera conferencia anual sobre Tcl/Tk. Portland, Oregón . Consultado el 29 de diciembre de 2015 .
^ El sistema XSB, versión 3.7.x, volumen 1: Manual del programador (PDF).
^ Tutorial de registro de datos de FoundationDB, archivado desde el original el 9 de agosto de 2013.
^ "Leapsight". Archivado desde el original el 11 de noviembre de 2018.
^ Semmle QL, 18 de septiembre de 2019.
^ "SecPAL". Microsoft Research . Archivado desde el original el 23 de febrero de 2007.
^ Lifschitz, Vladimir. "Fundamentos de la programación lógica". Principles of knowledge representation 3 (1996): 69-127. "Las posibilidades expresivas de [Datalog] son demasiado limitadas para aplicaciones significativas en la representación del conocimiento".
^ Huang, Green y Loo, "Registro de datos y aplicaciones emergentes", SIGMOD 2011 (PDF) , UC Davis{{citation}}: CS1 maint: multiple names: authors list (link).
^ Mei, Hongyuan; Qin, Guanghui; Xu, Minjie; Eisner, Jason (2020). "Registro de datos neuronal a través del tiempo: modelado temporal informado a través de la especificación lógica". Actas de ICML 2020 . arXiv : 2006.16723 .
^ Chin, Brian; Dincklage, Daniel von; Ercegovac, Vuk; Hawkins, Peter; Miller, Mark S.; Och, Franz; Olston, Christopher; Pereira, Fernando (2015). Ball, Thomas; Bodik, Rastislav; Krishnamurthi, Shriram; Lerner, Benjamin S.; Morrisett, Greg (eds.). Yedalog: Explorando el conocimiento a escala. 1.ª Cumbre sobre avances en lenguajes de programación (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 32. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. págs. 63–78. doi : 10.4230/LIPIcs.SNAPL.2015.63 . ISBN978-3-939897-80-4.
^ 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 . Apuntes de clase en informática. Vol. 3780. Berlín, Heidelberg: Springer. págs. 97–118. doi :10.1007/11575467_8. ISBN978-3-540-32247-4.S2CID 5223577 .
^ 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. ISBN978-1-4503-4241-4.S2CID 7531543 .
^ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (18 de junio de 2017). "Transferencia de doop a Soufflé". Actas del 6.º Taller internacional ACM SIGPLAN sobre el estado del arte en 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. Número de identificación del sujeto 3074689.
^ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (13 de noviembre de 2020). "Formulog: registro de datos 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.
^ 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.
^ Gryz; Guo; Liu; Zuzarte (2004). "Muestreo de consultas en DB2 Universal Database" (PDF) . Actas de la conferencia internacional ACM SIGMOD 2004 sobre gestión de datos - SIGMOD '04 . pág. 839. doi :10.1145/1007568.1007664. ISBN978-1581138597.S2CID 7775190 .
^ Gallaire, Hervé; Minker, John 'Jack', eds. (1978), "Lógica y bases de datos, Simposio sobre lógica y bases de datos, Centro de estudios e investigaciones de Toulouse, 1977", Avances en la teoría de bases de datos , Nueva York: Plenum Press, ISBN 978-0-822-2-3978-0-306-40060-5.
Ceri, S.; Gottlob, G.; Tanca, L. (marzo de 1989). "Lo que siempre quiso saber sobre Datalog (y nunca se atrevió a preguntar)" (PDF) . IEEE Transactions on Knowledge and Data Engineering . 1 (1): 146–166. CiteSeerX 10.1.1.210.1118 . doi :10.1109/69.43410. ISSN 1041-4347.
Abiteboul, S. (1995). Fundamentos de bases de datos. Richard Hull, Victor Vianu. Reading, Mass.: Addison-Wesley. ISBN 0-201-53771-0.OCLC 30546436 .
.jpg/1280px-Theta_supercomputer_-_389_071_002_(36954713450).jpg)