размерность дерева. Сбалансированные и не сбалансированные деревья.

"Дерево" может быть определено как иерархия узлов с попарными связями, в которой: самый верхний уровень иерархии имеет единственный узел, называемый корнем; каждый узел, кроме корня, связан с одним и только одним узлом, находящимся на более высоком уровне по сравнению с ним самим. "Дерево" может быть представлено как специальный вид направленного графа. Графы – структуры данных, состоящие из узлов, связанных дугами. Каждая дуга показывает однонаправленную связь между двумя узлами. Вершина графа называется корнем. Остальные элементы называют узлами иерархии. Узел, связанный с данным узлом и находящийся на более низком уровне в иерархии, называют дочерним узлом или потомком данного узла. Узел, связанный с данным узлом и находящийся на более высоком уровне в иерархии, называют родительским узлом или предком данного узла. Потомки, или дети, родительского узла – все узлы в поддереве, имеющие родительский узел корнем. Узлы дерева, которые не имеют потомков, называют листьями. Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев. Бинарное дерево назовем идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.

            В общем случае, дерево называется n-мерным, если его некоторый узел может иметь не более чем n узлов - потомков. Уровни иерархии. Диаграмма максимального пути. Глубина пути в иерархии. Семейство и размерность семейства иерархии. Стандартное графическое представление иерархии в ОС MS Windows

            Другой способ представления иерархий – вложенные множества. Здесь корень дерева – это внешнее или объемлющее множество, содержащее все узлы дерева. Каждый узел в дереве рассматривается как множество своих потомков.

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

Для работы с данными этого типа еще в 60-70 гг. прошлого века были разработаны иерархические СУБД, например IBM IMS, выполняющаяся на компьютерах IBM с архитектурой System/360, System/370. Однако подобные продукты в настоящее время в нашей стране не имеют широкого распространения. Другие средства работы с иерархиями предоставляются XML.

2)Предложение DELETE языка SQL. Удаление единственной записи. Удаление множества записей. Удаление с подзапросом.

DELETE FROM "table_name" WHERE {condition} – Удаление записи

Например: DELETE FROM Store_Information WHERE store_name = ‘Los Angeles’; - удаление строк, в которых store_name- Los Angeles.

3)Проектирование реляционных БД с использованием нормализации: нормальная форма Бойса-Кодда, четвертая нормальная форма.

Процесс нормализации это последовательное преобразование исходной БД к НФ, при этом каждая следующая НФ обязательно включает в себя предыдущую (что, собственно, и позволяет разбить процесс на этапы и производить его однократно, не возвращаясь к предыдущим этапам). Всего в реляционной теории насчитывается 6 НФ: Первая нормальная форма (обычно обозначается также 1НФ). Вторая нормальная форма. Третья нормальная форма. Нормальная форма Бойса-Кодда (НФБК). Четвёртая нормальная форма. Пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).

Рассмотрим следующий пример схемы отношения: СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, СОТР_ИМЯ, ПРО_НОМЕР, СОТР_ЗАДАН) Возможные ключи: СОТР_НОМЕР, ПРО_НОМЕР; СОТР_ИМЯ, ПРО_НОМЕР Функциональные зависимости: СОТР_НОМЕР -> CОТР_ИМЯ; СОТР_НОМЕР -> ПРО_НОМЕР; СОТР_ИМЯ -> CОТР_НОМЕР; СОТР_ИМЯ -> ПРО_НОМЕР; СОТР_НОМЕР, ПРО_НОМЕР -> CОТР_ЗАДАН; СОТР_ИМЯ, ПРО_НОМЕР -> CОТР_ЗАДАН

В этом примере мы предполагаем, что личность сотрудника полностью определяется как его номером, так и именем. В соответствии с определением отношение СОТРУДНИКИ-ПРОЕКТЫ находится в 3NF. Однако тот факт, что имеются функциональные зависимости атрибутов отношения от атрибута, являющегося частью первичного ключа, приводит к аномалиям. Например, для того, чтобы изменить имя сотрудника с данным номером согласованным образом, нам потребуется модифицировать все кортежи, включающие его номер. Детерминант - любой атрибут, от которого полностью функционально зависит некоторый другой атрибут.

Нормальная форма Бойса-Кодда Отношение R находится в нормальной форме Бойса-Кодда (BCNF) в том и только в том случае, если каждый детерминант является возможным ключом. Очевидно, что это требование не выполнено для отношения СОТРУДНИКИ-ПРОЕКТЫ. Можно произвести его декомпозицию к отношениям СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ: СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ) Возможные ключи: СОТР_НОМЕР; СОТР_ИМЯ Функциональные зависимости: СОТР_НОМЕР -> CОТР_ИМЯ; СОТР_ИМЯ -> СОТР_НОМЕР; СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН) Возможный ключ: СОТР_НОМЕР, ПРО_НОМЕР Функциональные зависимости: СОТР_НОМЕР, ПРО_НОМЕР -> CОТР_ЗАДАН

Возможна альтернативная декомпозиция, если выбрать за основу СОТР_ИМЯ. В обоих случаях получаемые отношения СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ находятся в BCNF, и им не свойственны отмеченные аномалии.

Рассмотрим пример следующей схемы отношения: ПРОЕКТЫ (ПРО_НОМЕР,ПРО_СОТР, ПРО_ЗАДАН)

Отношение ПРОЕКТЫ содержит номера проектов, для каждого проекта список сотрудников, которые могут выполнять проект, и список заданий, предусматриваемых проектом. Сотрудники могут участвовать в нескольких проектах, и разные проекты могут включать одинаковые задания. Каждый кортеж отношения связывает некоторый проект с сотрудником, участвующим в этом проекте, и заданием, который сотрудник выполняет в рамках данного проекта (мы предполагаем, что любой сотрудник, участвующий в проекте, выполняет все задания, предусмотренные этим проектом). По причине сформулированных выше условий единственным возможным ключом отношения является составной атрибут ПРО_НОМЕР, ПРО_СОТР, ПРО_ЗАДАН, и нет никаких других детерминантов. Следовательно, отношение ПРОЕКТЫ находится в BCNF. Но при этом оно обладает недостатками: если, например, некоторый сотрудник присоединяется к данному проекту, необходимо вставить в отношение ПРОЕКТЫ столько кортежей, сколько заданий в нем предусмотрено.

Многозначные зависимости В отношении R (A, B, C) существует многозначная зависимость R.A -> -> R.B в том и только в том случае, если множество значений B, соответствующее паре значений A и C, зависит только от A и не зависит от С. В отношении ПРОЕКТЫ существуют следующие две многозначные зависимости: ПРО_НОМЕР -> -> ПРО_СОТР; ПРО_НОМЕР -> -> ПРО_ЗАДАН

Легко показать, что в общем случае в отношении R (A, B, C) существует многозначная зависимость R.A -> -> R.B в том и только в том случае, когда существует многозначная зависимость R.A -> -> R.C.

Четвертая нормальная форма

Отношение R находится в четвертой нормальной форме (4NF) в том и только в том случае, если в случае существования многозначной зависимости A -> -> B все остальные атрибуты R функционально зависят от A.

В нашем примере можно произвести декомпозицию отношения ПРОЕКТЫ в два отношения ПРОЕКТЫ-СОТРУДНИКИ и ПРОЕКТЫ-ЗАДАНИЯ:

ПРОЕКТЫ-СОТРУДНИКИ (ПРО_НОМЕР, ПРО_СОТР)

ПРОЕКТЫ-ЗАДАНИЯ (ПРО_НОМЕР, ПРО_ЗАДАН)

Оба эти отношения находятся в 4NF и свободны от отмеченных аномалий.

Четвёртая нормальная форма запрещает существование многозначных зависимостей между столбцами. Если столбец вместо того, чтобы уникально идентифицировать другой столбец, ограничивает его значения некоторым предопределённым множеством значений – это означает, что между ними существует многозначная зависимость.

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