La persecución es un algoritmo de punto fijo simple que prueba y hace cumplir la implicación de las dependencias de datos en los sistemas de bases de datos . Desempeña un papel importante en la teoría de las bases de datos y en la práctica. Es utilizado, directa o indirectamente, a diario por personas que diseñan bases de datos, y se utiliza en sistemas comerciales para razonar sobre la consistencia y corrección de un diseño de datos. [ cita requerida ] Todavía se están descubriendo nuevas aplicaciones de la persecución en la gestión de metadatos y el intercambio de datos.
La persecución tiene su origen en dos artículos seminales de 1979, uno de Alfred V. Aho , Catriel Beeri y Jeffrey D. Ullman [1] y el otro de David Maier , Alberto O. Mendelzon y Yehoshua Sagiv . [2]
En su aplicación más simple, la persecución se usa para probar si la proyección de un esquema de relación restringido por algunas dependencias funcionales en una descomposición dada se puede recuperar volviendo a unir las proyecciones . Vamos t ser una tupla dedonde R es una relación y F es un conjunto de dependencias funcionales (FD). Si las tuplas en R se representan como t 1 , ..., t k , la unión de las proyecciones de cada t i debería estar de acuerdo con t endonde i = 1, 2, ..., k . Si t i no es el, el valor es desconocido.
La persecución se puede realizar dibujando un cuadro (que es el mismo formalismo utilizado en la consulta del cuadro ). Supongamos que R ha atributos A, B, ... y los componentes de t son a, b, ... . Para t i use la misma letra que t en los componentes que están en S i pero subíndice la letra con i si el componente no está en S i . Entonces, t i estará de acuerdo con t si está en S i y tendrá un valor único en caso contrario.
El proceso de persecución es confluente . Existen implementaciones del algoritmo de persecución, [3] algunas de ellas también son de código abierto. [4]
Ejemplo
Sea R ( A , B , C , D ) un esquema de relación que se sabe que obedece al conjunto de dependencias funcionales F = { A → B , B → C , CD → A }. Suponga que R se descompone en tres esquemas de relación S 1 = { A , D }, S 2 = { A , C } y S 3 = { B , C , D }. Para determinar si esta descomposición no tiene pérdidas, puede realizar una persecución como se muestra a continuación.
El cuadro inicial de esta descomposición es:
A | B | C | D |
---|---|---|---|
a | b 1 | c 1 | D |
a | b 2 | C | d 2 |
un 3 | B | C | D |
La primera fila representa S 1 . Los componentes de los atributos A y D no están subindicados y los de los atributos B y C están subindicados con i = 1. La segunda y tercera filas se rellenan de la misma manera con S 2 y S 3 respectivamente.
El objetivo de esta prueba es utilizar el dado F para probar que t = ( un , b , c , d ) que realmente está en R . Para hacerlo, el cuadro se puede perseguir aplicando los FD en F para equiparar símbolos en el cuadro. Una tabla final con una fila que es la misma que t implica que cualquier tupla t en la unión de las proyecciones es en realidad una tupla de R .
Para realizar la prueba de persecución, primero descomponga todos los FD en F para que cada FD tenga un único atributo en el lado derecho de la "flecha". (En este ejemplo, F permanece sin cambios porque todos sus FD ya tienen un solo atributo en el lado derecho: F = { A → B , B → C , CD → A }.)
Al equiparar dos símbolos, si uno de ellos no está suscrito, haga que el otro sea el mismo para que el cuadro final pueda tener una fila que sea exactamente igual a t = ( a , b , c , d ). Si ambos tienen su propio subíndice, cámbielo por el otro. Sin embargo, para evitar confusiones, se deben cambiar todas las ocurrencias.
Primero, aplique A → B al cuadro. La primera fila es ( a , b 1 , c 1 , d ) donde a no tiene suscripción y b 1 está subindicada con 1. Comparando la primera fila con la segunda, cambie b 2 por b 1 . Dado que la tercera fila tiene un 3 , b en la tercera fila permanece igual. El cuadro resultante es:
A | B | C | D |
---|---|---|---|
a | b 1 | c 1 | D |
a | b 1 | C | d 2 |
un 3 | B | C | D |
Entonces considere B → C . Tanto la primera como la segunda fila tienen b 1 y observe que la segunda fila tiene una c sin suscripción . Por lo tanto, la primera fila cambia a ( a , b 1 , c , d ). Entonces el cuadro resultante es:
A | B | C | D |
---|---|---|---|
a | b 1 | C | D |
a | b 1 | C | d 2 |
un 3 | B | C | D |
Consideremos ahora el CD → A . La primera fila tiene una c sin suscripción y una d sin suscripción , que es la misma que en la tercera fila. Esto significa que el valor A para las filas uno y tres también debe ser el mismo. Por lo tanto, cambiar un 3 en la tercera fila a una . El cuadro resultante es:
A | B | C | D |
---|---|---|---|
a | b 1 | C | D |
a | b 1 | C | d 2 |
a | B | C | D |
En este punto, observe que la tercera fila es ( a , b , c , d ) que es lo mismo que t . Por lo tanto, este es el cuadro final de la prueba de persecución con R y F dados . Por lo tanto, siempre que R se proyecta en S 1 , S 2 y S 3 y se reunió, el resultado es en R . En particular, la tupla resultante es la misma que la tupla de R que se proyecta sobre { B , C , D }.
Referencias
- ^ Alfred V. Aho , Catriel Beeri y Jeffrey D. Ullman : "La teoría de las uniones en bases de datos relacionales", ACM Trans. Datab. Syst. 4 (3): 297-314, 1979.
- ^ David Maier , Alberto O. Mendelzon y Yehoshua Sagiv : "Prueba de las implicaciones de las dependencias de los datos". ACM Trans. Datab. Syst. 4 (4): 455-469, 1979.
- ^ Michael Benedikt , George Konstantinidis , Giansalvatore Mecca , Boris Motik , Paolo Papotti , Donatello Santoro , Efthymia Tsamoura : Evaluación comparativa de la persecución . En Proc. de PODS, 2017.
- ^ "El motor de persecución de limpieza y mapeo de Llunatic" .
- Serge Abiteboul , Richard B. Hull , Victor Vianu : Fundamentos de bases de datos. Addison-Wesley, 1995.
- AV Aho , C. Beeri y JD Ullman : La teoría de las uniones en bases de datos relacionales . Transacciones ACM en sistemas de bases de datos 4 (3): 297-314, 1979.
- JD Ullman : Principios de base de datos y sistemas de conocimiento-base, Volumen I . Computer Science Press, Nueva York, 1988.
- JD Ullman , J. Widom : Un primer curso en sistemas de bases de datos (3ª ed.). págs. 96–99. Pearson Prentice Hall, 2008.
- Michael Benedikt , George Konstantinidis , Giansalvatore Mecca , Boris Motik , Paolo Papotti , Donatello Santoro , Efthymia Tsamoura : Evaluación comparativa de la persecución . En Proc. de PODS, 2017.
Otras lecturas
- Sergio Greco; Francesca Spezzano; Cristian Molinaro (2012). Datos incompletos y dependencias de datos en bases de datos relacionales . Editores Morgan & Claypool. ISBN 978-1-60845-926-1.