Álgebra de Imieliński-Lipski

En teoría de bases de datos , el álgebra de Imieliński-Lipski es una extensión del álgebra relacional sobre tablas con distintos tipos de valores nulos . Se utiliza para operar sobre relaciones con información incompleta .

Las álgebras de Imieliński-Lipski se definen para satisfacer condiciones precisas para la extensión semánticamente significativa de los operadores relacionales habituales, como proyección, selección, unión y unión, desde operadores sobre relaciones a operadores sobre relaciones con varios tipos de "valores nulos".

Estas condiciones requieren que el sistema sea seguro en el sentido de que no se pueda derivar ninguna conclusión incorrecta utilizando un subconjunto específico F de los operadores relacionales; y que sea completo en el sentido de que todas las conclusiones válidas expresables por expresiones relacionales que utilicen operadores en F sean de hecho derivables en este sistema. Por ejemplo, es bien sabido que el enfoque de lógica de tres valores para tratar con valores nulos, que admite el tratamiento de valores nulos por SQL, no es completo; consulte el libro de Ullman . ^[1] Para demostrar esto, sea T:

Tomar la consulta SQL Q

SELECCIONE NOMBRE DE T DONDE ( CLASE = 'Redes' Y SEMESTRE = 'Primavera' ) O ( CALIFICACIÓN = 'A' Y SEMESTRE <> 'Primavera' )                  

La consulta SQL Q devolverá un conjunto vacío (sin resultados) bajo la semántica de 3 valores que actualmente adoptan todas las variantes de SQL. Esto se debe a que en SQL, NULL nunca es igual a ninguna constante; en este caso, ni a “Primavera” ni a “Otoño” ni a “Invierno” (si hay semestre de invierno en esta escuela). NULL='Spring'evaluará a TAL VEZ y también lo hará NULL='Fall'. La disyunción TAL VEZ O TAL VEZ evalúa a TAL VEZ (no VERDADERO). Por lo tanto, Igor no será parte de la respuesta (y, por supuesto, tampoco lo será Rohit). Pero Igor debería devolverse como la respuesta.

De hecho, independientemente del semestre en el que Igor haya cursado la asignatura de Redes (sin importar cuál haya sido el valor desconocido de NULL), la condición de selección será verdadera. SQL no detectará a este “Igor” y la respuesta de SQL estará incompleta según los requisitos de completitud especificados en Tomasz Imieliński y Witold Lipski , 'Información incompleta en bases de datos relacionales'. ^[2] También se argumenta allí que la lógica de 3 valores (VERDADERO, FALSO, TAL VEZ) nunca puede garantizar una respuesta completa para tablas con información incompleta.

Se definen como álgebras de Imielinski-Lipski tres álgebras que satisfacen condiciones de seguridad y completitud: el álgebra de tablas de Codd , el álgebra de tablas V y el álgebra de tablas condicionales (tablas C).

El álgebra de tablas Codd se basa en los valores NULL únicos habituales de Codd . La tabla T anterior es un ejemplo de tabla Codd. El álgebra de tablas Codd solo admite proyecciones y selecciones positivas. También se demuestra en [IL84 que no es posible extender correctamente más operadores relacionales sobre tablas Codd. Por ejemplo, una operación tan básica como la unión no se puede extender sobre tablas Codd. No es posible definir selecciones con condiciones booleanas que involucren negación y preservar la completitud. Por ejemplo, no se pueden admitir consultas como la consulta Q anterior. Para poder extender más operadores relacionales, se necesita una forma más expresiva de representación de valores nulos en tablas que se denominan V-tabla.

El álgebra de tablas V se basa en muchos valores nulos o variables diferentes ("marcados") que pueden aparecer en una tabla. Las tablas V permiten mostrar que un valor puede ser desconocido pero el mismo para diferentes tuplas. Por ejemplo, en la tabla siguiente, Gaurav e Igor piden la misma cerveza (pero desconocida) en dos bares desconocidos (que pueden ser diferentes o no, pero siguen siendo desconocidos). Gaurav y Jane frecuentan el mismo bar desconocido (Y1). Por lo tanto, en lugar de un valor NULL, utilizamos variables indexadas o constantes de Skolem . ^[3]

Se ha demostrado que el álgebra de tablas V admite correctamente la proyección, la selección positiva (sin que se produzca ninguna negación en la condición de selección), la unión y el cambio de nombre de los atributos, lo que permite procesar consultas conjuntivas arbitrarias. Una propiedad muy deseable de la que goza el álgebra de tablas V es que todos los operadores relacionales de las tablas se realizan exactamente de la misma manera que en el caso de las relaciones habituales.

A continuación se muestra un ejemplo de tabla condicional (c-table).

Tiene una columna adicional “con”, que es una condición booleana que involucra variables, valores nulos, igual que en las tablas V.

SELECCIONAR * DE T DONDE ( CLASE = 'Redes' Y SEMESTRE = 'Primavera' ) O ( CALIFICACIÓN = 'A' Y SEMESTRE <> 'Primavera' )                   

sobre la siguiente tabla c-table

El álgebra de tablas condicionales, de interés principalmente teórico, admite proyección, selección, unión, combinación y cambio de nombre. Bajo el supuesto de mundo cerrado , también puede manejar el operador de diferencia, por lo que puede admitir todos los operadores relacionales.

Las álgebras de Imieliński-Lipski fueron introducidas por Tomasz Imieliński y Witold Lipski Jr. en Información incompleta en bases de datos relacionales . ^[2]

• Abiteboul, S. ; Kanellakis, P.; Grahne, G. (1991). "Sobre la representación y consulta de conjuntos de mundos posibles" (PDF) . Theoretical Computer Science . 78 (1): 159–187. doi : 10.1016/0304-3975(51)90007-2 .
• Abiteboul, S.; Duschka, OM (1998). "Complejidad de la respuesta a consultas mediante vistas materializadas". Proc. ACM SIGMOD-SIGACT-SIGART, PODS : 254–263. CiteSeerX  10.1.1.92.2956 .
• Verde, TJ; Karvounarakis, G.; Tannen, Val (2007). "Procedencia Semiring". Proc. ACM SIGMOD-SIGACT-SIGART, VAINAS : 31–40.
• Karvounarakis, G.; Green, TJ (2012). "Datos anotados con semiring: consultas y procedencia" (PDF) . ACM SIGMOD . 41 (3): 5–14. doi :10.1145/2380776.2380778. S2CID  11600847.
• TJ Green (2009). Modelos para información incompleta y probabilística; Capítulo 2, en Gestión y minería de datos inciertos . Springer Link.
• Grahne, G.; Kiricenko, V. (noviembre de 2004). "Hacia una teoría algebraica de la integración de la información" (PDF) . Información y computación . 194 (2): 79–100. doi :10.1016/j.ic.2004.07.003.