Persecución (algoritmo)

El algoritmo de persecución es un método sencillo de punto fijo que prueba y verifica las implicaciones de las dependencias de datos en los sistemas de bases de datos . Desempeña un papel fundamental tanto en la teoría como en la práctica de las bases de datos. Quienes diseñan bases de datos lo utilizan a diario, directa o indirectamente, y en sistemas comerciales se emplea para analizar la coherencia y la corrección del diseño de datos. Aún se están descubriendo nuevas aplicaciones del algoritmo de 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 sobre una descomposición dada se puede recuperar volviendo a unir las proyecciones . Sea t una tupla en${\displaystyle \pi _{S_{1}}(R)\bowtie \pi _{S_{2}}(R)\bowtie ...\bowtie \pi _{S_{k}}(R)}$donde R es una relación y F es un conjunto de dependencias funcionales (DF). Si las tuplas en R se representan como t ₁ , ..., t _k , la unión de las proyecciones de cada t _i debe coincidir con t en${\displaystyle \pi _{S_{i}}(R)}$donde i = 1, 2, ..., k . Si t _i no está en${\displaystyle \pi _{S_{i}}(R)}$, el valor es desconocido.

La búsqueda se puede realizar dibujando un tableau (que es el mismo formalismo que se usa en la consulta de tableau ). 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 S _i, pero agregue un subíndice a la letra con i si el componente no está en S _i . Entonces, t _i coincidirá 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 ]}

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 ₁ = { A , D }, S ₂ = { A , C } y S ₃ = { B , C , D }. Determinar si esta descomposición es sin pérdida se puede hacer realizando una búsqueda como se muestra a continuación.

El cuadro inicial para esta descomposición es:

La primera fila representa S ₁ . Los componentes para los atributos A y D no tienen subíndice y los de los atributos B y C tienen subíndice con i = 1. La segunda y tercera filas se rellenan de la misma manera con S ₂ y S ₃ respectivamente.

El objetivo de esta prueba es usar la matriz F dada para demostrar que t = ( a , b , c , d ) pertenece realmente a R. Para ello, se puede realizar una prueba de seguimiento aplicando las dependencias funcionales (DF) de F para igualar los símbolos de la matriz. Una matriz 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 seguimiento, primero se descomponen todas las DF de F de modo que cada DF tenga un único atributo en el lado derecho de la "flecha". (En este ejemplo, F permanece sin cambios porque todas sus DF ya tienen un único atributo en el lado derecho: F = { A → B , B → C , CD → A }).

Al igualar dos símbolos, si uno de ellos no tiene subíndice, el otro debe tener el mismo para que la tabla final tenga una fila idéntica a t = ( a , b , c , d ). Si ambos tienen su propio subíndice, se debe cambiar _uno por el otro. Sin embargo, para evitar confusiones, se deben cambiar todas las ocurrencias. Primero, se aplica A → B a la tabla. La primera fila es ( a , b1 , c1 , d ), donde a no tiene subíndice y b1 tiene el _{subíndice 1.} Comparando la primera fila con la segunda, se cambia b2 por b1 _. Como la tercera fila tiene a3 _, b _en la tercera fila permanece igual. La tabla resultante es:

Consideremos entonces B → C. Tanto la primera como la segunda fila tienen b ₁ y observemos que la segunda fila tiene una c sin subíndice . Por lo tanto, la primera fila cambia a ( a , b ₁ , c , d ). Entonces, el tableau resultante es:

Ahora consideremos CD → A. La primera fila tiene una c sin subíndice y una d sin subíndice , que es la misma que en la tercera fila. Esto significa que el valor de A para la primera y la tercera fila también debe ser el mismo. Por lo tanto, cambiamos un ₃ en la tercera fila por un 3. El tableau resultante es:

En este punto, observe que la tercera fila es ( a , b , c , d ), que es la misma que t . Por lo tanto, este es el tableau final para la prueba de persecución con R y F dados . En consecuencia, siempre que R se proyecte sobre S1 _, S2 _y S3 _y se vuelva 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 }.

• Serge Abiteboul , Richard B. Hull , Victor Vianu : Fundamentos de las bases de datos. Addison-Wesley, 1995.
• AV Aho , C. Beeri y JD Ullman : La teoría de las uniones en bases de datos relacionales . ACM Transactions on Database Systems 4(3): 297-314, 1979.
• JD Ullman : Principios de bases de datos y sistemas de conocimiento, Volumen I. Computer Science Press, Nueva York, 1988.
• J. D. Ullman , J. Widom : Un primer curso sobre 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 Caza . En Proc. de PODS, 2017.

• Sergio Greco; Francesca Spezzano; Cristian Molinaro (2012). Datos incompletos y dependencias de datos en bases de datos relacionales . Morgan & Claypool Publishers. ISBN 978-1-60845-926-1.