consulta conjuntiva

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

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 usando la conjunción ∧ y la cuantificación existencial ∃, pero no usando la disyunción ∨ , la negación ¬ o la cuantificación universal ∀. Cada una de estas fórmulas se puede reescribir (eficientemente) en una fórmula equivalente en forma normal prenexa , 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${\displaystyle x_{1},\ldots ,x_{k}}$llamadas variables distinguidas y variables ligadas${\displaystyle x_{k+1},\ldots ,x_{m}}$se denominan variables indistinguibles.${\displaystyle A_{1},\ldots ,A_{r}}$son fórmulas atómicas .

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

Las consultas conjuntivas pueden expresar una gran proporción de las consultas que se realizan con frecuencia en bases de datos relacionales . Por 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 a 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') ∧ vive(estudiante, dirección)

Tenga en cuenta que, dado que la única entidad de interés es el estudiante varón y su dirección, estas son las únicas variables distinguidas, mientras que las variables course, student2solo se cuantifican existencialmente , es decir, no se distinguen.

Las consultas conjuntivas sin variables distinguidas se denominan consultas conjuntivas booleanas . Las consultas conjuntivas en las que todas las variables son distinguidas (y ninguna variable está ligada) se denominan consultas de equi-unión , ^{[ 1 ]} porque son el equivalente, en el cálculo relacional , de las consultas de equi-unión en el álgebra relacional (cuando se seleccionan todas las columnas del resultado).

Las consultas conjuntivas también se corresponden con las consultas select-project-join en álgebra relacional (es decir, consultas de álgebra relacional que no utilizan las operaciones unión o diferencia) y con las consultas select-from-where en SQL en las que la condición where utiliza exclusivamente conjunciones de condiciones de igualdad atómicas, es decir, condiciones construidas a partir de nombres de columnas y constantes sin utilizar operadores de comparación distintos de "=", combinadas mediante "and". Cabe destacar que 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

seleccionar 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' ;

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

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

Aunque esta notación no contiene cuantificadores, las variables que aparecen en la cabeza 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 Datalog, no todos los programas 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 Datalog dado existe un programa no recursivo equivalente (que corresponda a una consulta de álgebra relacional positiva, o, equivalentemente, a una fórmula de lógica existencial positiva de primer orden , o, como caso especial, a una consulta conjuntiva) se conoce como el problema de acotación de Datalog y es indecidible. ^{[ 2 ]}

Entre las extensiones de las consultas conjuntivas que capturan un mayor poder expresivo se 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 según 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 de agregación .

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

Para el estudio de la complejidad computacional de la evaluación de consultas conjuntivas, es necesario 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 se suele denominar 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-dificultad de las consultas conjuntivas puede parecer sorprendente, ya que el álgebra relacional y SQL engloban estrictamente las consultas conjuntivas y, por lo tanto, son al menos igual de 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 supuestos teóricos de 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 listar todas las respuestas a una consulta conjuntiva no booleana se ha estudiado en el contexto de los algoritmos de enumeración , con una caracterización (bajo ciertas suposiciones de dificultad computacional ) de las consultas para las que la enumeración puede realizarse con un preprocesamiento de tiempo lineal y un retardo constante entre cada solución. Específicamente, se trata de las consultas conjuntivas acíclicas que también satisfacen una condición de conexión libre . ^{[ 5 ]}

Las consultas conjuntivas son uno de los grandes éxitos de la teoría de bases de datos, ya que muchos problemas interesantes que son computacionalmente difíciles o indecidibles para clases más amplias de consultas son factibles para consultas conjuntivas. ^{[ 6 ]} Por ejemplo, consideremos el problema de contención de consultas . Escribimos${\displaystyle R\subseteq S}$para dos relaciones de base de datos${\displaystyle R,S}$del mismo esquema si y solo si cada tupla que aparece en${\displaystyle R}$también ocurre en${\displaystyle S}$. Dada una consulta${\displaystyle Q}$y una instancia de base de datos relacional${\displaystyle I}$, escribimos la relación de resultado de evaluar la consulta en la instancia simplemente como${\displaystyle Q(I)}$. Dadas dos consultas${\displaystyle Q_{1}}$y${\displaystyle Q_{2}}$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${\displaystyle I}$sobre el esquema de la base de datos de entrada,${\displaystyle Q_{1}(I)\subseteq Q_{2}(I)}$La principal aplicación de la contención de consultas reside en la optimización de consultas: es posible decidir si dos consultas son equivalentes simplemente comprobando la contención mutua.

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

Una clase importante de consultas conjuntivas que tienen una complejidad combinada de tiempo polinomial son las consultas conjuntivas acíclicas . ^{[ 9 ]} 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 . ^{[ 10 ]} 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 grafo de dependencia de las variables en la consulta (es decir, el grafo que tiene las variables de la consulta como nodos y una arista no dirigida).${\displaystyle \{x,y\}}$entre dos variables si y solo si existe una fórmula atómica${\displaystyle R(x,y)}$o${\displaystyle R(y,x)}$en la consulta) y la consulta conjuntiva es acíclica si y solo si su grafo de dependencia es acíclico .

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 ser acíclico está un hipergrafo, análoga al ancho de árbol acotado en grafos . Las consultas conjuntivas de ancho de árbol acotado tienen una complejidad combinada LOGCFL . ^{[ 11 ]}

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

• Georg Gottlob , Presentación sobre métodos de descomposición estructural para la evaluación eficiente de consultas conjuntivas (PDF)