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

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

Пример: Пусть дан список студентов, содержащий их фамили и средний бал успеваемости (см. таблицу). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычислятся как ([номер_записи] -1) * [длина_записи]. Пусть аргумент поиска "Петров". На рисунке показаны одно из возможных для этого набора данных бинарных деревьев поиска и путь поиска.

 

Таблица 1.1.
Студент	Балл
Васильев	4,2
Иванов	3,4
Кузнецов	3,5
Петров	3,2
Сидоров	4,6
Тихомиров	3,8

 

 

 

Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

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

70.Слабые сущности в инфологической модели «Сущность-связь». Определение, пример, графическая интерпретация.

В модели «сущность—связь» определен особый тип сущности, называемый слабой сущностью (weak entity). К слабым сущностям относятся такие сущности, которые могут существовать в базе данных только в том случае, если в ней присутствует сущность некоторого другого типа. Сущность, не являющаяся слабой, называется сильной сущностью (strong entity).
Чтобы разобраться в том, что такое слабые сущности, рассмотрим базу данных отдела кадров с классами сущностей СОТРУДНИКИ-ПОДЧИНЕННЫЙ. Предположим, что в соответствии с деловым регламентом, экземпляр сущности Сотрудник может существовать, не будучи связанным ни с одной сущностью класса ПОДЧИНЕННЫЙ, но сущность ПОДЧИНЕННЫЙ не может существовать вне связи с какой-либо сущностью класса СОТРУДНИК. Тогда сущность ПОДЧИНЕННЫЙ является слабой. Это означает, что данные о сущности ПОДЧИНЕННЫЙ могут появиться в базе данных только в том случае, если эта сущность имеет связь с какой-либо сущностью класса СОТРУДНИК.

 

85.Реляционная схема таблиц. Логический и физический ключ реляционных отношений. Определение, назначение, пример.

 

Реляционная модель строится на основе отношений. Отношение- некоторое подмножество одного или более доменов. Домен- это некоторое множество, набор однородных значений. Если в структуру отношения добавить ограничения на возможные значения данных, то получается реляционная схема. Схема данных- имя отношения с перечнем столбцов и строк. Термин «ключ отношения» имеет различные значения на стадиях проектирования и реализации. Если в процессе проектирования под ключом понимается один или несколько столбцов, однозначным образом идентифицирующий картежи отношения, то на стадии реализации под ключом понимается столбец, на базе которого строится индекс с целью повышения эффективности обработки данных. Чтобы различить 2 значения ключа, употребляют термины «логический ключ» и «физический ключ». Логический ключ - это уникальный идентификатор. Физический ключ- столбец, на основе которого создается индекс или другая структура хранения с целью увеличения скорости обработки.