stringtranslate.com

Registro de datos

Datalog es un lenguaje de programación de lógica declarativa . Si bien es sintácticamente 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 diferentes de Prolog . A menudo se utiliza 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 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:

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:

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 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:

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

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]

Consideraciones de rendimiento

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

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:

Estrategias de evaluación de arriba hacia abajo

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

Juegos de magia

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]

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.

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

Muchas implementaciones de Datalog amplían Datalog con características adicionales; consulte § Motores de Datalog para obtener más información.

Agregación

El registro de datos se puede ampliar para admitir funciones agregadas . [27]

Los motores de registro de datos notables que implementan agregación incluyen:

Negación

Añadir 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 añadir negación con la semántica del modelo estable es exactamente la programación de conjuntos de respuestas .

Se puede agregar la negación estratificada a Datalog mientras se conserva su semántica de punto fijo y de teoría de modelos. Entre los motores Datalog destacados que implementan la negación estratificada se incluyen:

Comparación con Prolog

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

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

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 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.

Motores de registro de datos

Los sistemas que implementan lenguajes inspirados en Datalog, ya sean compiladores , intérpretes , bibliotecas o DSL integrados , se conocen como motores Datalog . Los motores Datalog a menudo implementan extensiones de Datalog, extendiéndolo con tipos de datos adicionales , interfaces de funciones externas o soporte para redes definidas por el usuario . Dichas extensiones pueden permitir escribir programas no terminantes o mal definidos. [ cita requerida ]

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

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.

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 . [42] [43] Google ha desarrollado una extensión de Datalog para el procesamiento de big data . [44]

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

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]

Véase también

Notas

  1. ^ ab 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, págs. 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". Revista de la 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). "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.
  9. ^ 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].
  10. ^ 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.
  11. ^ 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".
  12. ^ 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. ISBN 978-3-031-16767-6.
  13. ^ 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 .
  14. ^ 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. ISBN 978-1-4503-6290-0.S2CID239258588  .​
  15. ^ 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. ISBN 978-3-540-32247-4.S2CID 5223577  .
  16. ^ 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. ISBN . 978-3-642-22110-1.
  17. ^ 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].
  18. ^ 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.ID S2C  256565728.
  19. ^ 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  .​
  20. ^ 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. ISBN 978-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.
  21. ^ 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. ISBN 978-3-642-32925-8.
  22. ^ Shkapsky, Alexander; Yang, Mohan; Interlandi, Matteo; Chiu, Hsuan; Condie, Tyson; Zaniolo, Carlo (14 de junio de 2016). "Análisis de macrodatos con consultas de registros de datos en 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.
  23. ^ 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.
  24. ^ 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  .​
  25. ^ Dantsin, Evgeny; Eiter, Thomas; Gottlob, Georg; Voronkov, Andrei (1 de septiembre de 2001). "Complejidad y poder expresivo de la programación lógica". Encuestas de computación de la ACM . 33 (3): 374–425. doi :10.1145/502807.502810. ISSN  0360-0300.
  26. ^ 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.
  27. ^ 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.
  28. ^ "Capítulo 7. Reglas - Manual de referencia de LogicBlox 3.10". developer.logicblox.com . Consultado el 4 de marzo de 2023 .
  29. ^ "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".
  30. ^ 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.
  31. ^ 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. ISBN 978-0-89791-352-2. {{cite book}}: |journal=ignorado ( ayuda )
  32. ^ 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.
  33. ^ 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.
  34. ^ Flujo de datos diferencial, julio de 2022
  35. ^ 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 .
  36. ^ El sistema XSB, versión 3.7.x, volumen 1: Manual del programador (PDF).
  37. ^ Tutorial de registro de datos de FoundationDB, archivado desde el original el 9 de agosto de 2013.
  38. ^ "Leapsight". Archivado desde el original el 11 de noviembre de 2018.
  39. ^ Semmle QL, 18 de septiembre de 2019.
  40. ^ "SecPAL". Microsoft Research . Archivado desde el original el 23 de febrero de 2007.
  41. ^ 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".
  42. ^ Huang, Green y Loo, "Registro de datos y aplicaciones emergentes", SIGMOD 2011 (PDF) , UC Davis{{citation}}: CS1 maint: multiple names: authors list (link).
  43. ^ 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 .
  44. ^ 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–78. doi : 10.4230/LIPIcs.SNAPL.2015.63 . ISBN 978-3-939897-80-4.
  45. ^ 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. ISBN 978-3-540-32247-4.S2CID 5223577  .
  46. ^ 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  .
  47. ^ 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.
  48. ^ 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.
  49. ^ 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.
  50. ^ 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. ISBN 978-1581138597. Número de identificación del sujeto  7775190.
  51. ^ 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.
  52. ^ Abiteboul, Serge ; Hull, Richard; Vianu, Victor (1995), Fundamentos de bases de datos, Addison-Wesley, pág. 305, ISBN 9780201537710.

Referencias