Зависимость, генерирующая кортеж

В теории реляционных баз данных зависимость , генерирующая кортежи (TGD), представляет собой определенный вид ограничения на реляционную базу данных . Это подкласс класса встроенных зависимостей (ED).

Алгоритм, известный как погоня, принимает в качестве входных данных экземпляр, который может удовлетворять или не удовлетворять набору TGD (или, в более общем смысле, ED), и, если он завершается (что априори неразрешимо), выводит экземпляр, который удовлетворяет TGD.

Определение

Зависимость, порождающая кортеж, представляет собой предложение в логике первого порядка следующего вида: ^[1]

${\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \exists y_{1},\ldots ,y_{m},\psi (x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m})}$

где — возможно пустое, а — непустая конъюнкция реляционных атомов . Реляционный атом имеет форму , где каждый из членов — это переменные или константы. ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle R(w_{1},\ldots ,w_{h})}$ ${\displaystyle w,\ldots ,w_{h}}$

Фрагменты

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

Существуют также некоторые фрагменты TGD, которые можно выразить в защищенной логике , в частности: ^{[2] [3]}

• в TGD с защитой границы (FGTGD) все переменные, общие для тела и заголовка правила (называемые граничными переменными ), должны встречаться вместе в некотором атоме;
• Защищенные TGD (GTGD) — это особые FGTGD, в которых все переменные, используемые в теле правила, должны встречаться вместе в некотором атоме;
• Линейные ТГД (ЛТГД) — это особые ГТГД, тело которых состоит из одного атома;
• зависимости включения (IND) являются частными LTGD, где в обеих сторонах правила есть только один реляционный атом. ^[4]

В SQL зависимости включения обычно выражаются посредством более сильного ограничения, называемого внешним ключом , которое заставляет граничные переменные быть потенциальным ключом в таблице, соответствующей реляционному атому . ${\displaystyle \psi }$

Ссылки

1. Fagin, Ronald (2009). «Tuple-Generating Dependencies» (Зависимости, генерирующие кортежи). В LIU, LING ; ÖZSU, M. TAMER (ред.). Encyclopedia of Database Systems (Энциклопедия систем баз данных ). Springer US. стр. 3201–3202. doi :10.1007/978-0-387-39940-9_1274. ISBN 9780387355443.
2. Бенедикт, Майкл; Бурхис, Пьер; Жачье, Луи; Томазо, Микаэль (август 2019 г.). Рассуждение о раскрытии информации при интеграции данных при наличии ограничений источника . IJCAI 2019 — 28-я Международная совместная конференция по искусственному интеллекту. Макао, Китай. стр. 1551–1557. arXiv : 1906.00624 . doi : 10.24963/ijcai.2019/215.
3. Консоль, Марко; Колайтис, Фокион Г.; Пиерис, Андреас (июнь 2021 г.). Модельно-теоретические характеристики онтологий, основанных на правилах . Симпозиум по принципам систем баз данных. PODS'21: Труды 40-го симпозиума ACM SIGMOD-SIGACT-SIGAI по принципам систем баз данных . Виртуальное мероприятие, Китай. стр. 416–428. doi : 10.1145/3452021.3458310 . hdl : 11573/1568516 .
4. Колайтис, Фокион Г. «Учебное пособие по зависимостям баз данных» (PDF) . Калифорнийский университет в Санта-Крус и IBM Research — Альмаден . Проверено 10 декабря 2021 г. ^{[ мертвая ссылка ‍ ]}

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

• Абитбул, Серж ; Халл, Ричард Б.; Виану, Виктор (1995). Основы баз данных . Эддисон-Уэсли. ISBN 0-201-53771-0.
• Алин Дойч, Моделирование ограничений целостности FOL, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf