La persecución es un algoritmo simple de punto fijo que prueba y aplica la implicación de las dependencias de datos en los sistemas de bases de datos . Desempeña un papel importante tanto en la teoría de bases de datos como en la práctica. Lo utilizan, directa o indirectamente, a diario las personas que diseñan bases de datos, y se utiliza en sistemas comerciales para razonar sobre la coherencia y corrección de un diseño de datos. [ cita necesaria ] 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 fundamentales 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 utiliza para probar si la proyección de un esquema de relación restringido por algunas dependencias funcionales en una descomposición dada puede recuperarse volviendo a unir las proyecciones . Sea t una tupla donde 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 ti debe coincidir con t en donde i = 1, 2, ..., k . Si ti no está activado , el valor es desconocido.
La búsqueda se puede realizar dibujando un cuadro (que es el mismo formalismo utilizado en la consulta del cuadro). Supongamos que R tiene 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 Si , pero subíndice la letra con i si el componente no está en Si . Entonces, t i concordará con t si está en Si 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]
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 }. Supongamos que R se descompone en tres esquemas de relación S 1 = { A , D }, S 2 = { A , C } y S 3 = { B , C , D }. Se puede determinar si esta descomposición no tiene pérdidas realizando una búsqueda como se muestra a continuación.
El cuadro inicial para esta descomposición es:
La primera fila representa S 1 . Los componentes de los atributos A y D no tienen índice y los de los atributos B y C tienen índice 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 la F dada para demostrar que t = ( a , b , c , d ) está realmente en R. Para hacerlo, el cuadro se puede seguir aplicando los FD en F para igualar los símbolos en el cuadro. Un cuadro final con una fila igual a 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 de modo 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 único atributo en el lado derecho: F = { A → B , B → C , CD → A }.)
Al equiparar dos símbolos, si uno de ellos no tiene índice, 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, cambie cualquiera para que sea el otro. Sin embargo, para evitar confusiones, se deben cambiar todas las apariciones.
Primero, aplique A → B al cuadro. La primera fila es ( a , b 1 , c 1 , d ) donde a no tiene índice y b 1 tiene subíndice 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:
Entonces considere B → C . Tanto la primera como la segunda fila tienen b 1 y observe que la segunda fila tiene un c sin suscripción . Por lo tanto, la primera fila cambia a ( a , b 1 , c , d ). Entonces el cuadro resultante es:
Ahora considere CD → A . La primera fila tiene una cy 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, cambie un 3 en la tercera fila por un . El cuadro resultante es:
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 para la prueba de persecución con R y F dados . Por lo tanto, siempre que R se proyecta sobre S 1 , S 2 y S 3 y se vuelve a unir, el resultado está en R . En particular, la tupla resultante es la misma que la tupla de R que se proyecta sobre { B , C , D }.
