Чейз (алгоритм)

Погоня — это простое тестирование алгоритма с фиксированной точкой и обеспечение учета зависимостей данных в системах баз данных . Он играет важную роль как в теории баз данных , так и на практике.Он используется, прямо или косвенно, ежедневно людьми, проектирующими базы данных, а также в коммерческих системах для оценки согласованности и правильности структуры данных. Новые применения поиска в управлении метаданными и обмене данными все еще обнаруживаются.

Погоня берет свое начало в двух основополагающих статьях 1979 года, одна из которых написана Альфредом В. Ахо , Катриэль Бири и Джеффри Д. Уллманом. а другой — Дэвидом Майером , Альберто О. Мендельзоном и Иеошуа Сагивом .

В простейшем применении погоня используется для проверки того, может ли проекция схемы отношения , ограниченной некоторыми функциональными зависимостями , быть восстановлена ​​на заданную декомпозицию путем повторного соединения проекций . Пусть t будет кортежем в $\pi _{S_{1}}(R)\bowtie \pi _{S_{2}}(R)\bowtie ...\bowtie \pi _{S_{k}}(R)$ где R – отношение , а F – множество функциональных зависимостей (ФЗ). Если кортежи в R представлены как t ₁ , ..., t _k , соединение проекций каждого ti _должно согласовываться с t на $\pi _{S_{i}}(R)$ где я = 1, 2, ..., к . Если я _{включен} не $\pi _{S_{i}}(R)$, значение неизвестно.

Погоню можно выполнить, нарисовав таблицу (это тот же формализм, который используется в запросе таблицы ). Предположим, что R имеет атрибуты A, B,... и компоненты t — это a, b,... . Для ti _S используйте ту же букву, что и t, в компонентах, входящих в S _i, но добавляйте букву i, если компонент не входит в _i . Тогда t _i будет согласовываться с t, если оно находится в Si _, и в противном случае будет иметь уникальное значение.

Процесс преследования является слитным . Существуют реализации алгоритма преследования, некоторые из них также имеют открытый исходный код.

Пример

Пусть R ( A , B , C , D ) — схема отношений, о которой известно, что она подчиняется множеству функциональных зависимостей F = { A → B , B → C , CD→A }. Предположим, что R разложено на три схемы отношений S ₁ = { A , D }, S ₂ = { A , C } и S ₃ = { B , C , D }. Определить, является ли это разложение без потерь, можно, выполнив поиск, как показано ниже.

Исходная таблица для этого разложения:

А	Б	С	Д
а	б 1	с 1	д
а	б 2	с	д 2
aа3	б	с	д

Первая строка представляет S ₁ . Компоненты атрибутов A и D не имеют индексов, а компоненты атрибутов B и C имеют индекс i = 1. Вторая и третья строки заполняются таким же образом S ₂ и S ₃ соответственно.

Цель этого теста — использовать заданный F , чтобы доказать, что = ( a , b , c , d ) действительно находится в R. t Для этого таблицу можно просмотреть, применив FD в F для приравнивания символов в таблице. Итоговая таблица со строкой, такой же, как t, подразумевает, что любой кортеж t в соединении проекций на самом деле является кортежем R .
Чтобы выполнить тест преследования, сначала разложите все FD в F так, чтобы каждый FD имел один атрибут в правой части «стрелки». (В этом примере F остается неизменным, поскольку все его FD уже имеют один атрибут в правой части: F = { A → B , B → C , CD → A }.)

При приравнивании двух символов, если один из них не имеет индекса, сделайте другой таким же, чтобы в окончательной таблице могла быть строка, точно такая же, как t = ( a , b , c , d ). Если оба имеют свой собственный индекс, измените один на другой. Однако во избежание путаницы все вхождения следует изменить.
Сначала примените A → B к таблице.Первая строка — это ( a , b ₁ , c ₁ , d ), где a не имеет индекса, а b ₁ имеет индекс 1. Сравнивая первую строку со второй, измените b ₂ на b ₁ . третьей строке есть 3 _{Поскольку в} , b в третьей строке остается прежним. Итоговая таблица:

А	Б	С	Д
а	б 1	с 1	д
а	б 1	с	д 2
aа3	б	с	д

рассмотрим B → C. Затем И первая, и вторая строки имеют b ₁ и обратите внимание, что вторая строка имеет безиндексный c . Поэтому первая строка меняется на ( , b1 , ₎ c , d a . Тогда результирующая таблица будет такой:

А	Б	С	Д
а	б 1	с	д
а	б 1	с	д 2
aа3	б	с	д

рассмотрим CD → A. Теперь В первой строке есть c без индекса и d без индекса , что такое же, как и в третьей строке. Это означает, что значение A для первой и третьей строк также должно быть одинаковым. Следовательно, измените в ₃ строке на . третьей Итоговая таблица:

А	Б	С	Д
а	б 1	с	д
а	б 1	с	д 2
а	б	с	д

На этом этапе обратите внимание, что третья строка — это ( a , b , c , d ), которая совпадает с t . это окончательная таблица для теста преследования с заданными R и F. Таким образом , Следовательно, всякий раз, когда R проецируется на S ₁ , S ₂ и S ₃ и снова соединяется, результат находится в R . В частности, результирующий кортеж такой же, как кортеж R , который проецируется на { B , C , D }.

Ссылки

• Серж Абитебул , Ричард Б. Халл , Виктор Виану : Основы баз данных. Аддисон-Уэсли, 1995.
• А. В. Ахо , К. Бери и Дж. Д. Ульман : Теория объединений в реляционных базах данных . Транзакции ACM в системах баз данных 4 (3): 297–314, 1979.
• Дж. Д. Ульман : Принципы баз данных и систем баз знаний, том I. Computer Science Press, Нью-Йорк, 1988.
• Дж. Д. Ульман , Дж. Видом : Первый курс систем баз данных (3-е изд.). стр. 96–99. Пирсон Прентис Холл, 2008.
• Майкл Бенедикт , Джордж Константинидис , Джансальваторе Мекка , Борис Мотик , Паоло Папотти , Донателло Санторо , Эфтимия Цамура : Сравнительный анализ погони . В Proc. ПОДС, 2017.

Дальнейшее чтение

• Серджио Греко; Франческа Спеццано; Кристиан Молинаро (2012). Неполные данные и зависимости данных в реляционных базах данных . Издательство Морган и Клейпул. ISBN  978-1-60845-926-1 .