53. Назначение служебной и информационной частей хранимой записи

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

Существует несколько способов размещения элементов данных в хранимой записи, или иначе видов формата хранимой записи.

54.Методы обработки файлов на физическом уровне. Алгоритм поиска по бинарному дереву.

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

Бинарное дерево поиска — это двоичное дерево, для которого выполняются след условия:

• оба поддерева — левое и правое, являются двоичными деревьями поиска.

• у всех узлов левого поддерева произвольного узла x значения ключей данных меньше, нежели значение ключа данных узла x.

• у всех узлов правого поддерева произвольного узла x значения ключей данных больше, нежели значение ключа данных узла x.

Алгоритм поиска элемента:

Дано: дерево Т и ключ K.

Алгоритм:

Если дерево пусто, сообщить, что узел не найден, и остановиться.

Иначе сравнить K со значением ключа корневого узла X.

Если K=X, выдать ссылку на этот узел и остановиться.

Если K>X, рекурсивно искать ключ K в правом поддереве Т.

Если K<X, рекурсивно искать ключ K в левом поддереве Т.

55.Правила перехода от er- модели предметной области к схеме базы данных.

1. Для каждой сущности создается отношение с тем же именем. Каждый простой (не многозначный и не составной) атрибут сущности становится атрибутом отношения с тем же именем.

2. Атрибуты, входящие в ключ сущности, становятся первичным ключом отношения. Если имеется несколько возможных ключей, выбирается наиболее используемый и самый короткий из ключей, значения атрибутов которого не будут изменяться.

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

4. Если сущность содержит необязательный атрибут, и соответствующим свойством обладают многие экземпляры сущности, предпочтительно добавить этот атрибут к создаваемому отношению с указанием на возможность неопределенных значений (NULL). Если же это свойство – редкое, т.е. имеется у небольшого количества экземпляров объектов, то предпочтительно создать отдельное отношение для его хранения, содержащее атрибут первичного ключа (из ключа сущности) и атрибут для хранения значения редкого свойства.

5. Если сущность содержит составной атрибут, то предпочтительно создать отдельный атрибут отношения для каждого элемента составного свойства.

6. Для каждой связи один-к-одному (1:1) в одно из отношений (любое) добавляются атрибуты первичного ключа, связанного с ним отношения и из этих атрибутов создается внешний ключ. Если класс принадлежности обеих сущностей в этой связи является обязательным, то нужно рассмотреть вариант объединения этих двух сущностей в одном отношении: ликвидировать одно из отношений, предварительно перенеся все неключевые атрибуты из него во второе отношение. Если связь имеет атрибуты, то их нужно добавить к атрибутам созданного отношения.

7. Для каждой связи один-ко-многим (1:N) в отношение на стороне связи «многие» добавляются атрибуты первичного ключа связанного с ним отношения и из этих атрибутов создается внешний ключ. Если класс принадлежности одной из сущностей в этой связи является необязательным, то ключ сущности с необязательным классом добавляется в отношение, соответствующее сущности с обязательным классом принадлежности.

8. Для каждой связи многие-ко-многим (М:N) создается отношение связи (в дополнение к уже созданным отношениям, соответствующим связываемым сущностям). В отношение связи нужно включить ключевые атрибуты обоих связываемых отношений, и создать два внешних ключа; при этом первичным ключом отношения связи будут все его атрибуты. Если связь имеет атрибуты, то их нужно добавить к атрибутам отношения связи.

9. Для каждой N-арной связи, аналогично связи M:N, создается отношение связи (в дополнение к отношениям сущностей). Отношение, порождаемое связью, будет иметь среди своих атрибутов ключи каждой сущности. В отношение связи нужно включить ключевые атрибуты обоих связываемых отношений, и создать два внешних ключа; при этом первичным ключом отношения связи будут все его атрибуты. Если связь имеет атрибуты, то их нужно добавить к атрибутам отношения связи.

10. Для обобщающей сущности создается одно отношение, содержащее все общие для всех ролевых сущностей атрибуты; первичным ключом отношения становится ключ сущности. Для каждой ролевой сущности и каждой связи, в которых она участвует, отношения создаются по вышеприведенным правилам.

11. Для всех возможных ключей всех сущностей, кроме первичных, создаются ограничения уникальности UNIQUE.