Хранение отношений

существует 2 подхода к физической организации хранения:

1. кортежное хранение(!) – более распространённое;

2. поатрибутное хранение.

При 1 обеспечивается быстрый доступ к целому кортежу, но т.к. в разных кортежах значения атрибутов могут дублироваться, то такая БД может создать лишнюю дублируемую информацию, и если требуется часть кортежа, то может потребоваться лишнее обращение к памяти. При 2 столбец хранится с исключёнными дубликатами Þ требуется меньше внешней памяти; при операциях соединения есть преимущества; но требуются дополнительные операции, когда требуется целый кортеж.

В основе 1 лежит страничная организация внешней памяти. Страница внешней памяти = страница кадра ОЗУ.

Каждый кортеж имеет уникальный идентификатор (tid), который не изменяется. Обычно кортеж целиком хранится на одной странице. Если кортеж не умещается на одной станице, то кортеж может хранится в отдельном файле, а ссылки на него хранить на странице или в виде деревьев.

Как правило, с одной страницей связывается одно отношение. Если хранить на одной странице несколько отношений, то это усложнит структуру описателей. Встаёт проблема реорганизации при добавлении столбцов: новое отношение вводится только для новых кортежей, а в старых могут быть неопределённые значения. При удалении какого-либо отношения (?).

При 2 гранится полный набор доменов, но для доступа необходим целый кортеж, а следовательно его нужно “сконструировать”, т.е. должна быть информация, описывающая для каждого кортежа – кортеж такой же степени, содержащий ссылки на места расположения необходимой информации в соответствующих столбцах: <{домен, №_элемента_в_домене}>.

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