Consulta conjuntiva

En teoría de bases de datos , una consulta conjuntiva es una forma restringida de consultas de primer orden que utilizan el operador de conjunción lógica . Muchas consultas de primer orden se pueden escribir como consultas conjuntivas. En particular, una gran parte de las consultas emitidas en bases de datos relacionales se pueden expresar de esta manera. Las consultas conjuntivas también tienen una serie de propiedades teóricas deseables que las clases más grandes de consultas (por ejemplo, las consultas de álgebra relacional ) no comparten.

Definición

Las consultas conjuntivas son el fragmento de lógica de primer orden (independiente del dominio) dado por el conjunto de fórmulas que se pueden construir a partir de fórmulas atómicas utilizando la conjunción ∧ y la cuantificación existencial ∃, pero sin utilizar la disyunción ∨, la negación ¬ o la cuantificación universal ∀. Cada una de estas fórmulas se puede reescribir (de manera eficiente) en una fórmula equivalente en forma normal prenex , por lo que esta forma generalmente se asume simplemente.

Así pues, las consultas conjuntivas tienen la siguiente forma general:

${\displaystyle (x_{1},\ldots ,x_{k}).\exists x_{k+1},\ldots x_{m}.A_{1}\wedge \ldots \wedge A_{r}}$,

con las variables libres denominadas variables distinguidas, y las variables ligadas denominadas variables no distinguidas. son fórmulas atómicas . ${\displaystyle x_{1},\ldots ,x_{k}}$ ${\displaystyle x_{k+1},\ldots ,x_{m}}$ ${\displaystyle A_{1},\ldots ,A_{r}}$

Como ejemplo de por qué es importante la restricción a la lógica de primer orden independiente del dominio, considere , que no es independiente del dominio; consulte el teorema de Codd . Esta fórmula no se puede implementar en el fragmento select-project-join del álgebra relacional y, por lo tanto, no se debe considerar una consulta conjuntiva. ${\displaystyle x_{1}.\exists x_{2}.R(x_{2})}$

Las consultas conjuntivas pueden expresar una gran proporción de consultas que se emiten con frecuencia en bases de datos relacionales . Para dar un ejemplo, imaginemos una base de datos relacional para almacenar información sobre estudiantes, su dirección, los cursos que toman y su género. Encontrar todos los estudiantes varones y sus direcciones que asisten a un curso al que también asiste una estudiante mujer se expresa mediante la siguiente consulta conjuntiva:

(estudiante, dirección). ∃ (estudiante2, curso). asiste(estudiante, curso) ∧ género(estudiante, 'masculino') ∧ asiste(estudiante2, curso) ∧ género(estudiante2, 'femenino') ∧ vidas(estudiante, dirección)

Nótese que dado que la única entidad de interés es el estudiante masculino y su dirección, estas son las únicas variables distinguidas, mientras que las variables course, student2sólo se cuantifican existencialmente , es decir, no se distinguen.

Fragmentos

Las consultas conjuntivas sin variables distinguidas se denominan consultas conjuntivas booleanas . Las consultas conjuntivas en las que se distinguen todas las variables (y no se vincula ninguna variable) se denominan consultas de igualación , ^[1] porque son el equivalente, en el cálculo relacional , de las consultas de igualación en el álgebra relacional (cuando se seleccionan todas las columnas del resultado).

Relación con otros lenguajes de consulta

Las consultas conjuntivas también corresponden a las consultas select-project-join en álgebra relacional (es decir, consultas de álgebra relacional que no utilizan las operaciones union o difference) y a las consultas select-from-where en SQL en las que la condición where utiliza exclusivamente conjunciones de condiciones de igualdad atómica, es decir, condiciones construidas a partir de nombres de columnas y constantes que no utilizan operadores de comparación distintos de "=", combinados utilizando "and". En particular, esto excluye el uso de agregación y subconsultas. Por ejemplo, la consulta anterior se puede escribir como una consulta SQL del fragmento de consulta conjuntiva como

seleccione l . estudiante , l . dirección de asiste a1 , género g1 , asiste a2 , género g2 , vive l donde a1 . estudiante = g1 . estudiante y a2 . estudiante = g2 . estudiante y l . estudiante = g1 . estudiante y a1 . curso = a2 . curso y g1 . género = 'masculino' y g2 . género = 'femenino' ;                                   

Registro de datos

Además de su notación lógica, las consultas conjuntivas también pueden escribirse como reglas de Datalog . De hecho, muchos autores prefieren la siguiente notación de Datalog para la consulta anterior:

 resultado ( estudiante ,  dirección )  :  asiste a ( estudiante ,  curso ),  género ( estudiante ,  masculino ),  asiste a ( estudiante2 ,  curso ),  género ( estudiante2 ,  femenino ),  vive ( estudiante ,  dirección ).

Aunque no hay cuantificadores en esta notación, las variables que aparecen en el encabezado de la regla siguen estando implícitamente cuantificadas universalmente , mientras que las variables que solo aparecen en el cuerpo de la regla siguen estando implícitamente cuantificadas existencialmente.

Si bien cualquier consulta conjuntiva puede escribirse como una regla de Datalog, no todos los programas de Datalog pueden escribirse como una consulta conjuntiva. De hecho, solo las reglas individuales sobre símbolos de predicados extensionales pueden reescribirse fácilmente como una consulta conjuntiva equivalente. El problema de decidir si para un programa de Datalog dado existe un programa no recursivo equivalente (que corresponde a una consulta de álgebra relacional positiva o, equivalentemente, una fórmula de lógica de primer orden existencial positiva o, como caso especial, una consulta conjuntiva) se conoce como el problema de acotación de Datalog y es indecidible. ^[2]

Extensiones

Las extensiones de consultas conjuntivas que capturan mayor poder expresivo incluyen:

• Uniones de consultas conjuntivas , que son equivalentes al álgebra relacional positiva (es decir, libre de negación ).
• consultas conjuntivas extendidas por unión y negación , que por el teorema de Codd corresponden al álgebra relacional y a la lógica de primer orden
• consultas conjuntivas con predicados incorporados , por ejemplo, predicados aritméticos
• consultas conjuntivas con funciones agregadas .

El estudio formal de todas estas extensiones se justifica por su aplicación en bases de datos relacionales y se encuentra en el ámbito de la teoría de bases de datos .

Complejidad

Para el estudio de la complejidad computacional de la evaluación de consultas conjuntivas, se deben distinguir dos problemas. El primero es el problema de evaluar una consulta conjuntiva en una base de datos relacional donde tanto la consulta como la base de datos se consideran parte de la entrada. La complejidad de este problema suele denominarse complejidad combinada , mientras que la complejidad del problema de evaluar una consulta en una base de datos relacional, donde se supone que la consulta es fija, se denomina complejidad de datos . ^[3]

Las consultas conjuntivas son NP-completas con respecto a la complejidad combinada , ^[4] mientras que la complejidad de datos de las consultas conjuntivas es muy baja, en la clase de complejidad paralela AC0 , que está contenida en LOGSPACE y, por lo tanto, en tiempo polinomial . La NP-dureza de las consultas conjuntivas puede parecer sorprendente, ya que el álgebra relacional y SQL subsumen estrictamente las consultas conjuntivas y, por lo tanto, son al menos tan difíciles (de hecho, el álgebra relacional es PSPACE -completa con respecto a la complejidad combinada y, por lo tanto, es incluso más difícil bajo los supuestos teóricos de la complejidad ampliamente aceptados). Sin embargo, en el escenario de aplicación habitual, las bases de datos son grandes, mientras que las consultas son muy pequeñas, y el modelo de complejidad de datos puede ser apropiado para estudiar y describir su dificultad.

El problema de enumerar todas las respuestas a una consulta conjuntiva no booleana se ha estudiado en el contexto de algoritmos de enumeración , con una caracterización (bajo ciertas suposiciones de dificultad computacional ) de las consultas para las que se puede realizar la enumeración con preprocesamiento de tiempo lineal y retraso constante entre cada solución. Específicamente, estas son las consultas conjuntivas acíclicas que también satisfacen una condición de conexión libre . ^[5]

Propiedades formales

Las consultas conjuntivas son una de las grandes historias de éxito de la teoría de bases de datos , ya que muchos problemas interesantes que son computacionalmente difíciles o indecidibles para clases más grandes de consultas son factibles para consultas conjuntivas. ^[6] Por ejemplo, considere el problema de contención de consultas. Escribimos para dos relaciones de base de datos del mismo esquema si y solo si cada tupla que ocurre en también ocurre en . Dada una consulta y una instancia de base de datos relacional , escribimos la relación de resultado de evaluar la consulta en la instancia simplemente como . Dadas dos consultas y y un esquema de base de datos , el problema de contención de consultas es el problema de decidir si para todas las posibles instancias de base de datos sobre el esquema de base de datos de entrada, . La principal aplicación de la contención de consultas es en la optimización de consultas: decidir si dos consultas son equivalentes es posible simplemente verificando la contención mutua. ${\displaystyle R\subseteq S}$ ${\displaystyle R,S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle Q}$ ${\displaystyle I}$ ${\displaystyle Q(I)}$ ${\displaystyle Q_{1}}$ ${\displaystyle Q_{2}}$ ${\displaystyle I}$ ${\displaystyle Q_{1}(I)\subseteq Q_{2}(I)}$

El problema de contención de consultas es indecidible para el álgebra relacional y SQL , pero es decidible y NP-completo para consultas conjuntivas. De hecho, resulta que el problema de contención de consultas para consultas conjuntivas es exactamente el mismo problema que el problema de evaluación de consultas. ^[6] Dado que las consultas tienden a ser pequeñas, la NP-completitud aquí generalmente se considera aceptable. El problema de contención de consultas para consultas conjuntivas también es equivalente al problema de satisfacción de restricciones . ^[7]

Una clase importante de consultas conjuntivas que tienen complejidad combinada en tiempo polinomial son las consultas conjuntivas acíclicas . ^[8] La evaluación de la consulta, y por lo tanto la contención de la consulta, es LOGCFL -completa y por lo tanto en tiempo polinomial . ^[9] La aciclicidad de las consultas conjuntivas es una propiedad estructural de las consultas que se define con respecto al hipergrafo de la consulta : ^[6] una consulta conjuntiva es acíclica si y solo si tiene un ancho de hiperárbol de 1. Para el caso especial de consultas conjuntivas en las que todas las relaciones utilizadas son binarias, esta noción corresponde al ancho de árbol del gráfico de dependencia de las variables en la consulta (es decir, el gráfico que tiene las variables de la consulta como nodos y un borde no dirigido entre dos variables si y solo si hay una fórmula atómica o en la consulta) y la consulta conjuntiva es acíclica si y solo si su gráfico de dependencia es acíclico . ${\displaystyle \{x,y\}}$ ${\displaystyle R(x,y)}$ ${\displaystyle R(y,x)}$

Una generalización importante de la aciclicidad es la noción de ancho de hiperárbol acotado , que es una medida de cuán cerca de acíclico está un hipergrafo, análogo al ancho de árbol acotado en los grafos . Las consultas conjuntivas de ancho de árbol acotado tienen una complejidad combinada LOGCFL . ^[10]

Las consultas conjuntivas sin restricciones sobre datos de árboles (es decir, una base de datos relacional que consta de una relación binaria secundaria de un árbol, así como relaciones unarias para etiquetar los nodos del árbol) tienen una complejidad combinada de tiempo polinomial. ^[11]

Referencias

1. Dan Olteanu, Jakub Závodný, Límites de tamaño para representaciones factorizadas de resultados de consultas , 2015, DOI 10.1145/2656335, [1]
2. Gerd G. Hillebrand, Paris C. Kanellakis , Harry G. Mairson, Moshe Y. Vardi : Problemas de acotación indecidible para programas de registro de datos. J. Log. Program. 25(2): 163-190 (1995)
3. Vardi, Moshe Y. (1982), "La complejidad de los lenguajes de consulta relacionales (Resumen ampliado)", Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación - STOC '82, págs. 137-146, CiteSeerX  10.1.1.331.6045 , doi :10.1145/800070.802186, ISBN 978-0897910705, S2CID  7869248, archivado desde el original el 23 de agosto de 2011 , consultado el 16 de mayo de 2011
4. Ashok K. Chandra y Philip M. Merlin, 1977. Implementación óptima de consultas conjuntivas en bases de datos relacionales . STOC '77: Actas del noveno simposio anual de la ACM sobre teoría de la computación [2]
5. Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne (2007). Duparc, Jacques; Henzinger, Thomas A. (eds.). "Sobre consultas conjuntivas acíclicas y enumeración de retardo constante". Lógica informática . Apuntes de clase en informática. 4646. Springer Berlin Heidelberg: 208–222. doi :10.1007/978-3-540-74915-8_18. ISBN . 9783540749158.
6. Serge Abiteboul , Richard B. Hull, Victor Vianu : Fundamentos de bases de datos. Addison-Wesley, 1995.
7. Kolaitis, Phokion G.; Vardi, Moshe Y. (2000), "Contención de consultas conjuntivas y satisfacción de restricciones", Journal of Computer and System Sciences , 61 (2): 302–332, doi : 10.1006/jcss.2000.1713
8. Mihalis Yannakakis : Algoritmos para esquemas de bases de datos acíclicos. Proc. VLDB 1981: 82-94.
9. Georg Gottlob , Nicola Leone y Francesco Scarcello (2001). "La complejidad de las consultas conjuntivas acíclicas". Journal of the ACM 48 (3): 431–498. doi :10.1145/382780.382783.
10. Georg Gottlob , Nicola Leone y Francesco Scarcello: Descomposiciones de hiperárboles y consultas manejables. J. Comput. Syst. Sci. 64(3): 579-627 (2002)
11. Georg Gottlob , Christoph Koch, Klaus U. Schulz: Consultas conjuntivas sobre árboles. J. ACM 53(2): 238-272 (2006)

Enlaces externos

• Ullman, JD Integración de información mediante vistas lógicas Theoretical Computer Science, 2000, 239, 189-210 ^{[ enlace roto ]}
• Georg Gottlob , Presentación sobre métodos de descomposición estructural para la evaluación eficiente de consultas conjuntivas (PDF)