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 realizadas sobre bases de datos relacionales pueden expresarse de esta forma. 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) dada 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 sin usar 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 la forma normal prenexa , por lo que esta forma generalmente se asume simplemente.

Por tanto, 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}}$,

las variables libres se denominan variables distinguidas y las variables ligadas se denominan 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; ver teorema de Codd . Esta fórmula no se puede implementar en el fragmento seleccionar-proyecto-unir del álgebra relacional y, por lo tanto, no debe considerarse 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 . Por poner un ejemplo, imaginemos una base de datos relacional para almacenar información sobre los 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 alumna 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)

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 coursesólo student2están cuantificadas existencialmente , es decir, no distinguidas.

Fragmentos

Las consultas conjuntivas sin variables distinguidas se denominan consultas conjuntivas booleanas . Las consultas conjuntivas donde se distinguen todas las variables (y ninguna variable está vinculada) se denominan consultas de unión equi , ^[1] porque son el equivalente, en el cálculo relacional , de las consultas de unión equi en el álgebra relacional (al seleccionar todas las columnas del resultado).

Relación con otros lenguajes de consulta

Las consultas conjuntivas también corresponden a consultas de selección de unión de proyecto en álgebra relacional (es decir, consultas de álgebra relacional que no utilizan las operaciones unión o diferencia) y a consultas de selección desde dónde en SQL en las que la condición dónde 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 "=", combinadas mediante "y". 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 atiende a1 , género g1 , atiende a2 , género g2 , vive l donde a1 . estudiante = g1 . estudiante y a2 . estudiante = g2 . estudiante y yo . estudiante = g1 . estudiante y a1 . curso = a2 . curso y g1 . género = 'masculino' y g2 . género = 'mujer' ;                                   

Registro de datos

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

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

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

Si bien cualquier consulta conjuntiva se puede escribir como una regla de Datalog, no todos los programas de Datalog se pueden escribir como una consulta conjuntiva. De hecho, sólo las reglas únicas sobre símbolos de predicados extensionales pueden reescribirse fácilmente como una consulta conjuntiva equivalente. El problema de decidir si para un programa Datalog determinado existe un programa no recursivo equivalente (correspondiente a una consulta de álgebra relacional positiva o, de manera equivalente, una fórmula de lógica existencial positiva de primer orden o, como caso especial, una consulta conjuntiva) Se conoce como problema de acotación del registro de datos y es indecidible. ^[2]

Extensiones

Las extensiones de consultas conjuntivas que capturan un poder más 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 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 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, 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 generalmente se denomina complejidad combinada , mientras que la complejidad del problema de evaluar una consulta en una base de datos relacional, donde la consulta se supone fija, se llama complejidad de datos . ^[3]

Las consultas conjuntivas son NP-completas con respecto a la complejidad combinada , ^[4] mientras que la complejidad de los datos de las consultas conjuntivas es muy baja, en la clase de complejidad paralela AC0 , que está contenida en LOGSPACE y, por tanto, en tiempo polinómico . La dureza NP 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 igual de difíciles (de hecho, el álgebra relacional es PSPACE completo con respecto a la complejidad combinada y, por lo tanto, es aún más difícil en condiciones ampliamente extendidas). sostenían supuestos teóricos de la complejidad). 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 los algoritmos de enumeración , con una caracterización (bajo algunos supuestos de dureza computacional ) de las consultas para las cuales se puede realizar la enumeración con preprocesamiento de tiempo lineal y retraso constante entre cada solución. Específicamente, estas son 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 en el sentido de 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 bases de datos del mismo esquema si y sólo 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 resultante de evaluar la consulta en la instancia simplemente como . Dadas dos consultas y un esquema de base de datos , el problema de contención de consultas es el problema de decidir si para todas las instancias de base de datos posibles sobre el esquema de base de datos de entrada ,. La principal aplicación de la contención de consultas es la optimización de consultas: es posible decidir si dos consultas son equivalentes 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 á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 integridad NP 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 tanto, la contención de la consulta, es LOGCFL completa y, por 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 sólo si tiene un ancho de hiperárbol 1. Para el caso especial de consultas conjuntivas en donde 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 sólo 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 qué tan cerca de acíclico está un hipergrafo, análogo al ancho de árbol acotado en los gráficos . Las consultas conjuntivas de ancho de árbol acotado tienen una complejidad combinada LOGCFL . ^[10]

Las consultas conjuntivas sin restricciones sobre datos de árbol (es decir, una base de datos relacional que consta de una relación hija binaria de un árbol así como relaciones unarias para etiquetar los nodos del árbol) tienen una complejidad combinada en 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 límites indecidibles para programas de registro de datos. J. Registro. Programa. 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 ACM sobre teoría de la informática - 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 ACM sobre teoría de la informática [2]
5. Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne (2007). Duparc, Jacques; Henzinger, Thomas A. (eds.). "Sobre consultas conjuntivas acíclicas y enumeración de retraso constante". Lógica informática . Apuntes de conferencias sobre informática. 4646 . Springer Berlín Heidelberg: 208–222. doi :10.1007/978-3-540-74915-8_18. ISBN 9783540749158.
6. Serge Abiteboul , Richard B. Hull, Victor Vianu : fundamentos de las bases de datos. Addison-Wesley, 1995.
7. Kolaítis, 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". Revista de la ACM 48 (3): 431–498. doi :10.1145/382780.382783.
10. Georg Gottlob , Nicola Leone y Francesco Scarcello: descomposiciones de hiperárbol y consultas manejables. J. Computación. Sistema. Ciencia. 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 utilizando vistas lógicas Theoretical Computer Science, 2000, 239, 189-210 ^{[ enlace muerto ]}
• Georg Gottlob , Presentación sobre métodos de descomposición estructural para la evaluación eficaz de consultas conjuntivas (PDF)