Декомпозиция без потерь. Теорема Хита.

При нормализации БД выполняются декомпозиции (разбиения путем проецирования) отношения, находящегося в предыдущей нормальной форме, на два или более отношений, удовлетворяющих требованиям следующей нормальной формы. Считаются правильными такие декомпозиции отношения, которые обратимы, т. е. имеется возможность собрать исходное отношение из декомпозированных отношений без потери информации. Такие декомпозиции называются декомпозициями без потерь.

Теорема Хита: Если есть отношение  R у которого есть атрибуты A, B, C, связанные зависимостью A -> B, то декомпозиция на r1(A, B) и r2(A,C) будет обратимой: R(A, B, C) = r1(A, B) join r2(A,C).

Например, вы с друзьями посидели в пабе. Имеет место отношение Pub (man, beer, payment).

man	beer	payment
Darth	Leffe Blonde	5$
Yoda	Heineken	10$
Jabba the Hutt	Amstel Light	8$

Каждый из вас пьет один определенный сорт пива. Это зависимость man -> beer.
Значит, по теореме Хита мы можем разделить данные на 2 отношения:

• man -> beer == beer_man (man, beer)

man	beer
Darth	Leffe Blonde
Yoda	Heineken
Jabba the Hutt	Amstel Light

• man -> payment == pay_man (man, payment)

man	payment
Darth	5$
Yoda	10$
Jabba the Hutt	8$

Этих данных достаточно, чтобы однозначно и правильно воссоздать оригинальное отношение Pub (man, beer, payment), используя natural join:

•        beer_man JOIN pay_man = pub

P.S. На всякий случай напоминаю, что при  natural join, о котором идет речь в теореме, все пары атрибутов из двух отношений, имеющих общее имя, приравниваются, а одна из пар равных атрибутов удаляется путем проекции.

Нормализация БД. Усиленная 3 форма (нормальная форма Бойса-Кодда)

Википедия говорит, что отношения находится в нормальной форме Бойса-Кодда тогда и только тогда, когда детерминанты всех ее функциональных зависимостей являются потенциальными ключами.

Иначе говоря:

• Детерминант функциональной зависимости - это то, что в левой её части 

• Потенциальный ключ - подмножество атрибутов, удовлетворяющее требованиям уникальности и минимальности (несократимости)

• Для проверки на соответствие НФБК нужно выделить все функциональные зависимости. Если любой детерминант можно выбрать в качестве ключа - отношение соответствует усиленной 3 форме.

• НФБК может отличаться  от 3 НФ только в том случае, если у отношения несколько потенциальных ключей

Например, есть следующая таблица:

producer_id	producer_name	product_name	amount
1	Alpha	Apricot	10
1	Alpha	Peach	20
1	Alpha	Strawberry	50
2	Beta	Apricot	10
2	Beta	Strawberry	30

Есть 2 варианта выбора ключа:

•  producer_id + product_name

producer_id	producer_name	product_name	amount
1	Alpha	Apricot	10
1	Alpha	Peach	20
1	Alpha	Strawberry	50
2	Beta	Apricot	10
2	Beta	Strawberry	30

• producer_name + product_name

producer_id	producer_name	product_name	amount
1	Alpha	Apricot	10
1	Alpha	Peach	20
1	Alpha	Strawberry	50
2	Beta	Apricot	10
2	Beta	Strawberry	30

Отношение соответствует 1, 2, 3 НФ.

Для того, чтобы доказать, что данное отношение не находится в НФБК, нужно найти такое функциональное отношение, в котором левая часть (детерминант)  не равна   producer_id + product_name или  producer_name + product_name (т.е. потенциальному ключу).

Таких зависимостей две:

• producer_name -> producer_id
• producer_id -> producer_name

Для приведения к НБКФ таблицу можно преобразовать так:

producer_id	producer_name
1	Alpha
2	Beta

producer_id	product_name	amount
1	Apricot	10
1	Peach	20
1	Strawberry	50
2	Apricot	10
2	Strawberry	30

Нормализация БД. 1, 2, 3 НФ

Для избавления  от части головняка, возникающего при использовании БД, талантливые камрады разработали целую теорию, как уменьшить избыточность хранимых данных, устранить аномалии обновления и т.д.. Нормализация БД - это и есть применение данной теории.

1 нормальная форма (1 НФ):

• В отношении нет одинаковых кортежей
• Кортежи не упорядочены 
• Атрибуты  не упорядочены и различаются по наименованию 
• Все атрибуты атомарны

Иначе говоря, в таблице

• нет одинаковых строк
• порядок строк не имеет значения
• колонки имеют различные имена, их очередность не играет роли
• в ячейку таблицы не втюхнут список или что-то подобное

В качестве примера используем таблицу с генеалогической информацией.

house	father	children
Lannister	Tywin	Cersei, Jaime, Tyrion
Stark	Eddard	Robb, Sansa, Arya, Bran, Rickon
Baratheon	Robert	Joffrey, Myrcella, Tommen

    Данная таблица не соответствует 1 НФ, так как атрибут children при разбиении на части или переупорядочивании эго состовляющих не теряет смысла. Т.е. атрибут children неатомарен.
    Таблица, соответствующая 1 НФ выглядит так:

house	father	child
Lannister	Tywin	Cersei
Lannister	Tywin	Jaime
Lannister	Tywin	Jaime
Stark	Eddard	Robb
Stark	Eddard	Sansa
Stark	Eddard	Arya
Stark	Eddard	Bran
Stark	Eddard	Rickon
Baratheon	Robert	Joffrey
Baratheon	Robert	Myrcella
Baratheon	Robert	Tommen

2 НФ: Каждый неключевой элемент неприводимо зависит от первичного ключа. Если потенциальный ключ отношения является простым, то отношение автоматически находится в 2НФ.

Иначе говоря:

• если ключ состоит из 1 поля и соблюдены требования 1 НФ, 2 НФ соблюдена
• если ключ составной, то другие атрибуты должны зависеть от всего ключа, а не от одного из его полей

name	position	small council member
Tywin Lannister	Hand Of The King	TRUE
Varys	Master Of Whisperers	TRUE
Robb Stark	King In The North	FALSE
Eddard Stark	Hand Of The King	TRUE

В данной таблице первичный ключ - имя и должность. Однако атрибут small council member зависит только от занимаемой должности. Иначе говоря, зависимость от первичного ключа неполная. Следовательно, таблица не соответствует 2 НФ. Для приведения ко 2 НФ выполняем декомпозицию:

name	position
Tywin Lannister	Hand Of The King
Varys	Master Of Whisperers
Robb Stark	King In The North
Eddard Stark	Hand Of The King

position	small council member
Hand Of The King	TRUE
Master Of Whisperers	TRUE
King In The North	FALSE

3 НФ: 

• Все неключевые атрибуты взаимно независимы
• Неключевые элементы не находятся в транзитивной зависимости от первичного ключа

Иначе говоря:

• каждое из неключевых полей зависит исключительно от ключа 

Снова возьмем таблицу должностей, однако, в этот раз первичным ключом будет только атрибут name.

name	position	small council member
Tywin Lannister	Hand Of The King	TRUE
Varys	Master Of Whisperers	TRUE
Robb Stark	King In The North	FALSE
Eddard Stark	Hand Of The King	TRUE

Пускай членство человека в малом совете зависит только от его должности. Тогда получаем следующие зависимости:

• name -> position
• position -> small council membership
• name -> small council membership 

Отношение не находится в 3 НФ, т.к.:

• неключевой атрибут small council member зависит от неключевого position
• name -> small council membership - транзитивная зависимость

Приводим к 3 НФ:

name	position
Tywin Lannister	Hand Of The King
Varys	Master Of Whisperers
Robb Stark	King In The North
Eddard Stark	Hand Of The King

position	small council member
Hand Of The King	TRUE
Master Of Whisperers	TRUE
King In The North	FALSE

На практике редко используются НФ более высокого порядка, так как дальнейшая нормализация зачастую не приводит к росту продуктивности.

Type Bounds

Существуют следующие ограничения типов:

• upper bound - ключевое слово extends
• lower bound - ключевое слово super.

При использовании wildcard тип передаваемого объекта можно:

• не ограничивать

University unboundedUniversity;
University<?> sameUnboundedUniversity;

• ограничивать снизу

University<? extends Student> lowerBoundedUniversity;

• ограничивать сверху

University<? super Genius> upperBoundedUniversity

При объявлении параметризованного класса тип параметра можно ограничить только сверху, зато сразу несколькими ограничителями (правила наследования в силе - можно ограничить одним классов и любым количеством интерфейсов).

class University<T extends Student & Educable & Callable> 

Generics

Несколько важных штук о дженериках:
1. Type erasure (стирание типов). Означает, что проверка соответствие типов в дженериках проводится исключительно на этапе компиляции. Далее данные о типах будут стёрты.

List<Clever> geniuses = new ArrayList<>();
List<Stupid> losers = new ArrayList<>();
System.out.println(geniuses.getClass() == losers.getClass());  //true

2. Как следствие type erasure, нельзя создать массив дженериков.

class University<T> {
    T[] group = new T[30];  //error
}

3. Дженерики не коваринтны.

List<Student> students = new ArrayList<>();
students = new ArrayList<Clever>(); //ошибка компиляции

4. При использовании wildcard (<?>, <? extends T>, <? super T>) стоит помнить о принципе PECS - Producer Extends Consumer Super. Этот принцип гласит:

Если метод имеет аргументы с параметризованным типом (например, Collection<T> или Predicate<T>), то в случае, если аргумент — производитель (producer), нужно использовать ? extends T, а если аргумент — потребитель(consumer), нужно использовать ? super T.

Производитель и потребитель, кто это такие? Очень просто: если метод читает данные из аргумента, то этот аргумент —производитель, а если метод передаёт данные в аргумент, то аргумент является потребителем. Важно заметить, что определяя производителя или потребителя, мы рассматриваем только данные типа T.

Примеры производителя - коллекции, потребителя - предикаты.

5. Можно использовать множественные ограничения:

class University<T extends Student & Serializable> 

Ковариантность

Скучное определение википедии:

"Ковариантностью называется сохранение иерархии наследования исходных типов в производных типах в том же порядке."

А на практике (в джаве) это значит, что: 

 1) при перегрузке методов можно менять возвращаемый тип на дочерний:

class Animal {
    public Animal createBaby(){
        return new Animal();
    }
}
 
class Cat extends Animal {
    @Override
    public Cat createBaby() {
        return new Cat();
    }
}

2) Творить всякие чудеса с массивами, так как они ковариантны:

Animal[] animals = new Animal[3];
animals = new Cat[4];

А вот дженерики не ковариантны. Поэтому такой трюк с коллекциями не прокатит:

List<Animal> animalList = new ArrayList<>();
List<Cat> catList = new ArrayList<>();
animalList = catList;  //compilation error

Более весело и подробно изложено тут с примерами для шарпа.