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

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

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

Определение

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

\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})

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

Фрагменты

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

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

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

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

Ссылки

^ Феджин, Рональд (2009). «Зависимости, порождающие кортежи». В ЛЮ, ЛИНГ ; ОЗСУ, М. ТАМЕР (ред.). Энциклопедия систем баз данных . Спрингер США. стр. 3201–3202 . дои : 10.1007/978-0-387-39940-9_1274 . ISBN 9780387355443 .
^ Бенедикт, Майкл; Бури, Пьер; Жаше, Луи; Томазо, Микаэль (август 2019 г.). Рассуждения о раскрытии информации при интеграции данных при наличии ограничений по источникам . IJCAI 2019 – 28-я Международная совместная конференция по искусственному интеллекту. Макао, Китай. стр. 1551–1557. arXiv : 1906.00624 . дои : 10.24963/ijcai.2019/215 .
^ Консоль, Марко; Колайтис, Фокион Г.; Пиерис, Андреас (июнь 2021 г.). Теоретико-модельные характеристики онтологий, основанных на правилах . Симпозиум по принципам систем баз данных. PODS'21: Материалы 40-го симпозиума ACM SIGMOD-SIGACT-SIGAI по принципам систем баз данных . Виртуальное мероприятие, Китай. стр. 416–428. дои : 10.1145/3452021.3458310 . hdl : 11573/1568516 .
^ Колайтис, Фокион Г. «Учебное пособие по зависимостям баз данных» (PDF) . Калифорнийский университет в Санта-Крус и исследовательский центр IBM — Альмаден Получено 1 декабря 2021 г. ^{[ мертвая ссылка ]}

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

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

[1] Феджин, Рональд (2009). «Зависимости, порождающие кортежи». В ЛЮ, ЛИНГ ; ОЗСУ, М. ТАМЕР (ред.). Энциклопедия систем баз данных . Спрингер США. стр. 3201–3202 . дои : 10.1007/978-0-387-39940-9_1274 . ISBN 9780387355443 .

[2] Бенедикт, Майкл; Бури, Пьер; Жаше, Луи; Томазо, Микаэль (август 2019 г.). Рассуждения о раскрытии информации при интеграции данных при наличии ограничений по источникам . IJCAI 2019 – 28-я Международная совместная конференция по искусственному интеллекту. Макао, Китай. стр. 1551–1557. arXiv : 1906.00624 . дои : 10.24963/ijcai.2019/215 .

[3] Консоль, Марко; Колайтис, Фокион Г.; Пиерис, Андреас (июнь 2021 г.). Теоретико-модельные характеристики онтологий, основанных на правилах . Симпозиум по принципам систем баз данных. PODS'21: Материалы 40-го симпозиума ACM SIGMOD-SIGACT-SIGAI по принципам систем баз данных . Виртуальное мероприятие, Китай. стр. 416–428. дои : 10.1145/3452021.3458310 . hdl : 11573/1568516 .

[4] Колайтис, Фокион Г. «Учебное пособие по зависимостям баз данных» (PDF) . Калифорнийский университет в Санта-Крус и исследовательский центр IBM — Альмаден Получено 1 декабря 2021 г. ^{[ мертвая ссылка ]}

[1]

[2]

[3]

[4]