Cтраница 2
Пусть F - множество F-зависимостей, не содержащее F-зависимостей вида 0 - - К. Покажите, что ни одна схема с двумя атрибутами не может иметь в F транзитивных зависимостей. [16]
Пусть F - множество F-зависимостей, которым удовлетворяет г. Если гг ( XY) и r2 ( YZW) - два отношения из d, такие, что XY Л YZW Y, а зависимость Y - Z принадлежит F, то гг t nyz ( га) назовем r - paciiiupcuucM r с помощью Y - - Z. Y - Z содержит столько же кортежей, сколько и rlt и может быть вычислено за один проход через г1 и г2, если оба они отсортированы по Y. Отметим, что r1 nYZ ( / 2) nxrz ( r) - Такое соединение, в котором общие атрибуты функционально определяют все атрибуты одного из отношений, называется соединением расширения. [17]
Пусть F - множество F-зависимостей из примера 5.21. Покажите, что в Bj В2 - - А атрибут А не посторонний. [18]
Пусть F - множество F-зависимостей, не содержащее F-зависимостей вида 0 - К. Покажите, что ни одна схема с двумя атрибутами не может иметь в F транзитивных зависимостей. [19]
Пусть F - множество F-зависимостей, которым удовлетворяет г. Если rx ( XY) и r2 ( YZW) - два отношения из d, такие, что XY fl YZW Y, а зависимость Y - - Z принадлежит F, то rl t nYZ ( r2) назовем - расширением гг с помощью Y - - Z. Заметим, что га-расширение гх с помощью Y - Z содержит столько же кортежей, сколько и г1; и может быть вычислено за один проход через г и г2, если оба они отсортированы по Y. Отметим, что гх яУ2 ( г2) Л-X YZ ( г) - Такое соединение, в котором общие атрибуты функционально определяют все атрибуты одного из отношений, называется соединением расширения. [20]
Если F - неизбыточное множество F-зависимостей, то в нем нет лишних F-зависимостей в том смысле, что нельзя уменьшить F, удалив некоторые F-зависимости. [21]
Неизбыточное покрытие G множества F-зависимостей не обязательно имеет столько же F-зависимостей, сколько любое другое покрытие G ( см. упр. [22]
Неизбыточное покрытие G множества F-зависимостей не обязательно имеет столько же F-завнсимостей, сколько любое другое покрытие G ( см. упр. [23]
Покажите, что для множества F-зависимостей не существует ни одного отношения, удовлетворяющего всем F-зависимостям в F - и только им. [24]
Как показано ранее, множество F-зависимостей F может быть разделено на классы с эквивалентными левыми частями. [25]
Определение 5.4. Пусть F - множество F-зависимостей над схемой R и X - Y принадлежит F. F-зависимость Х - Y называется редуцированной слева, если X не содержит атрибута А, постороннего в X - Y. Зависимость X - Y называется редуцированной справа, если Y не содержит атрибута А, постороннего для X - У. Редуцированная слева F-зависимость называется также полной F-зависимостью. [26]
Алгоритм определения того, что множество F-зависимостей навязано, принадлежит Beeri, Honeyman [1981], которые показали также, то проверка, покрывает множество Q подмножество F, навязанное схеме, или нет, является NP-полной. [27]
Алгоритм определения того, что множество F-зависимостей навязано, принадлежит Beeri, Honeyman [1981], которые показали также, что проверка, покрывает множество G подмножество F, навязанное схеме, или нет, является NP-полной. [28]
Определение 5.4. Пусть F - множество F-зависимостей над схемой R и X - Y принадлежит F. F-зависимость Х - Y называется редуцированной слева, если X не содержит атрибута А, постороннего в X - Y. Зависимость X - Y называется редуцированной справа, если Y не содержит атрибута А, постороннего для X - Y. Редуцированная слева F-зависимость называется также полной F-зависимостью. [29]
Повторяющееся применение правила заполнения для множества F F-зависимостей аналогично прогонке на табло. [30]