R в 3NF тогда и только тогда, когда R в BCNF?

Рассмотрим отношение R и набор функциональных зависимостей F, включающий только одну функциональную зависимость: {X->A}. докажите, что если R в 3NF тогда и только тогда, когда R в BCNF.

Пока что для ‹-направления тривиально по определению. Но я борюсь в направлении ->. Что мы знаем о F-closure? из определения мне нужно проверить для каждой функциональной зависимости Y->B, что в F-closure, что ее тривиально или Y является суперключом. Есть ли какие-то выводы о суперключе R, которые мне не хватает?


database primary-key functional-dependencies 3nf bcnf
person user2637293    schedule 28.01.2016    source источник
comment
Это звучит как домашние задания, stackoverflow не решает домашние задания для студентов.   -  person Chris Marisic    schedule 28.01.2016
comment
@ChrisMarisic, похоже, я согласен, но это не так. если это действительно беспокоит вас, я действительно пытался решить сам. Я отредактирую.   -  person user2637293    schedule 28.01.2016
comment
Пожалуйста, покажите, что вы сделали, чтобы решить эту проблему.   -  person Chris Marisic    schedule 28.01.2016
comment
Из вашего вопроса неясно, как F относится к FD, которые могут быть в вашем отношении. F не может быть замыканием, потому что в нем нет {A}->{A}. Может быть, это каноническая оболочка, т.е. замыкание — это именно те ФД, которые должны присутствовать, когда они есть. Без выяснения этого вопроса нельзя ответить.   -  person philipxy    schedule 08.02.2016

Ответы (1)


arrow_upward
1
arrow_downward

Вот набросок доказательства.

Тот факт, что схема отношения в НФБК подразумевает, что схема также находится в 3НФ, обусловлен определением 3НФ (каждый определитель является суперключом или подразумевает только простые атрибуты, и мы знаем, что каждый детерминант является суперключом, поскольку схема находится в НФБК). ).

Итак, мы должны показать, что если отношение находится в 3НФ, то оно также находится в НФБК.

Теперь рассмотрим единственную зависимость, {X->A}. Для определения 3NF либо X является суперключом, либо A является простым.

В первом случае, если X является суперключом, мы знаем, что схема также находится в BCNF.

Итак, нам нужно проверить только случай, когда X не является (супер)ключом, а A — простым. Мы можем доказать, что этот случай невозможен, выполнив следующие шаги.

У нас есть только две возможности: либо X содержит A, либо нет.

  1. Если X содержит A, то эта зависимость тривиальна, и, поскольку других зависимостей нет, X является ключом, а это нарушает нашу гипотезу, поэтому имеем противоречие.

  2. Если, с другой стороны, X не содержится в A, то X снова является ключом, а это снова противоречит нашей гипотезе.

Наконец, обратите внимание, что в этом доказательстве я предположил, что в R части из XU{A} нет других атрибутов, иначе эти другие атрибуты должны присутствовать в любом ключе отношения, и с ними должна быть как минимум другая зависимость.

person Renzo    schedule 28.01.2016