En la 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 simplemente 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 forma normal prenex , por lo que esta forma generalmente se asume simplemente.
Por tanto, las consultas conjuntivas tienen la siguiente forma general:
- ,
con las variables libres siendo llamadas variables distinguidas, y las variables ligadas siendo llamadas variables indistinguibles. 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, considere , que no es independiente del dominio; vea 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 debe considerarse una consulta conjuntiva.
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, imagine una base de datos relacional para almacenar información sobre los estudiantes, su dirección, los cursos que toman y su género. La búsqueda de todos los estudiantes varones y sus direcciones que asisten a un curso al que también asiste una estudiante se expresa mediante la siguiente consulta conjuntiva:
(estudiante, dirección). ∃ (alumno2, curso). asiste (estudiante, curso) ∧ género (estudiante, 'hombre') ∧ asiste (estudiante2, curso) ∧ género (estudiante2, 'mujer') ∧ vidas (estudiante, dirección)
Tenga en cuenta que dado que la única entidad de interés es el alumno y su dirección, éstas son las variables que se distinguen solamente, mientras que las variables course
, student2
sólo son cuantificadas existencialmente , es decir, un sitio mediocre.
Fragmentos
Las consultas conjuntivas sin variables distinguidas se denominan consultas conjuntivas booleanas . Las consultas conjuntivas en las que se distinguen todas las variables (y ninguna variable está vinculada) se denominan consultas de combinación equitativa , [1] porque son equivalentes, en el cálculo relacional , de las consultas de combinación equitativa 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 select-project-join en álgebra relacional (es decir, consultas de álgebra relacional que no usan la unión o diferencia de operaciones) y a consultas select-from-where en SQL en las que la condición where usa 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 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 l . 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 existencialmente implícitamente.
Si bien cualquier consulta conjuntiva se puede escribir como una regla de registro de datos, no todos los programas de registro de datos se pueden escribir como una consulta conjuntiva. De hecho, solo las reglas únicas sobre los símbolos de predicado extensional se pueden reescribir fácilmente como una consulta conjuntiva equivalente. El problema de decidir si para un programa de Datalog dado hay 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 el problema de los límites de Datalog 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 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 está justificado por su aplicación en bases de datos relacionales y está en el ámbito de la teoría de bases de datos .
Complejidad
Para el estudio de la complejidad computacional de evaluar 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 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 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 tanto, en tiempo polinomial . 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 tan 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 términos generales sostuvo 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 un preprocesamiento de tiempo lineal y un 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 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 la contención de consultas. Nosotros escribimospara dos relaciones de base de datos del mismo esquema si y solo si cada tupla que ocurre en también ocurre en . Dada una consultay 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 la contención de consultas es el problema de decidir si para todas las posibles instancias de la base de datos sobre el esquema de la base de datos de entrada, . La principal aplicación de la contención de consultas es la optimización de consultas: decidir si dos consultas son equivalentes es posible simplemente verificando la contención mutua.
El problema de la 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 completitud 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 una complejidad combinada de tiempo polinómico 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 hipergrama de la consulta : [6] una consulta conjuntiva es acíclica si y solo si tiene un ancho de hiperárbol 1. Para el caso especial de consultas conjuntivas en 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 .
Una generalización importante de la aciclicidad es la noción de ancho de árbol acotado, que es una medida de cuán cerca de acíclico está un hipergráfico, análogo al ancho de árbol acotado en los gráficos . Las consultas conjuntivas de ancho de árbol limitado tienen una complejidad combinada de LOGCFL . [10]
Las consultas conjuntivas no restringidas sobre datos de árbol (es decir, una base de datos relacional que consta de una relación secundaria binaria de un árbol, así como relaciones unarias para etiquetar los nodos del árbol) tienen una complejidad combinada de tiempo polinómico. [11]
Referencias
- ^ Dan Olteanu, Jakub Závodný, Límites de tamaño para representaciones factorizadas de resultados de consultas , 2015, DOI 10.1145 / 2656335, [1]
- ^ Gerd G. Hillebrand , Paris C. Kanellakis , Harry G. Mairson , Moshe Y. Vardi : Problemas de delimitación indecidibles para programas de registro de datos. J. Log. Programa. 25 (2): 163-190 (1995)
- ^ Vardi, Moshe Y. (1982), "La complejidad de los lenguajes de consulta relacionales (resumen extendido)" , Actas del simposio sobre teoría de la computación : 137-146, CiteSeerX 10.1.1.331.6045 , doi : 10.1145 / 800070.802186 , ISBN 978-0897910705, archivado desde el original el 23 de agosto de 2011 , consultado el 16 de mayo de 2011
- ^ 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 computación [2]
- ^ 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 conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 4646 : 208–222. doi : 10.1007 / 978-3-540-74915-8_18 . ISBN 9783540749158.
- ^ a b c Serge Abiteboul , Richard B. Hull , Victor Vianu : Fundamentos de bases de datos. Addison-Wesley, 1995.
- ^ Kolaitis, Phokion G .; Vardi, Moshe Y. (2000), "Conjunctive-Query Containment and Constraint Satisfaction", Journal of Computer and System Sciences , 61 (2): 302–332, doi : 10.1006 / jcss.2000.1713
- ^ Mihalis Yannakakis : algoritmos para esquemas de base de datos acíclicos. Proc. VLDB 1981: 82-94.
- ^ Georg Gottlob , Nicola Leone y Francesco Scarcello (2001). "La complejidad de las consultas conjuntivas acíclicas". Revista del ACM 48 (3): 431–498. doi : 10.1145 / 382780.382783 .
- ^ Georg Gottlob , Nicola Leone y Francesco Scarcello : Descomposiciones de hiperárboles y consultas tratables. J. Comput. Syst. Sci. 64 (3): 579-627 (2002)
- ^ 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 Ciencias de la computación teóricas , 2000, 239, 189-210 [ enlace muerto ]
- Georg Gottlob , Presentación sobre métodos de descomposición estructural para la evaluación eficiente de consultas conjuntivas (PDF)