Модели данных

Плеханова
Экономический факультет
Кафедра вычислительной техники и информационных технологий

взаимосвязей и операций их обработки.
Трехуровневая архитектура (инфологический, даталогический и физический

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

Рис. Классификация моделей данных

стадиях проектирования для описания структур данных в процессе разработки приложения,

а дата-логические модели уже поддерживаются конкретной СУБД.
Документальные модели данных соответствуют представлению о слабоструктурированной информации, ориентированной в основном на свободные форматы документов, текстов на естественном языке.
Модели, основанные на языках разметки документов, связаны прежде всего со стандартным общим языком разметки — SGML (Standart Generalised Markup Language), который был утвержден ISO в качестве стандарта еще в 80-х годах. Для каждого класса документов определяется свой набор правил, описывающих грамматику соответствующего языка разметки. Но ввиду некоторой своей сложности SGML использовался в основном для описания синтаксиса других языков (наиболее известным из которых является HTML), и немногие приложения работали с SGML-документами напрямую. 

SGML, язык HTML позволяет определять оформление элементов документа и имеет

некий ограниченный набор инструкций — тегов, при помощи которых осуществляется процесс разметки. Однако HTML сегодня уже не удовлетворяет в полной мере требованиям, предъявляемым современными разработчиками к языкам подобного рода. И ему на смену был предложен новый язык гипертекстовой разметки, мощный, гибкий и, одновременно с этим, удобный язык XML.
XML (Extensible Markup Language) — это язык разметки, описывающий целый класс объектов данных, называемых XML-документами. Он используется в качестве средства для описания грамматики других языков и контроля за правильностью составления документов. То есть сам по себе XML не содержит никаких тегов, предназначенных для разметки, он просто определяет порядок их создания.

словарей, содержат определенные языковые конструкции и принципы их взаимодействия в

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

(ИМД) является наиболее простой среди всех даталогических моделей. Исторически она

появилась первой среди всех даталогических моделей: именно эту модель поддерживает первая из зарегистрированных промышленных СУБД IMS фирмы IBM.
Основными информационными единицами в иерархической модели являются: база данных (БД), сегмент и поле. Поле данных определяется как минимальная, неделимая единица данных, доступная пользователю с помощью СУБД.
Сегмент в терминологии Американской Ассоциации по базам данных DBTG (Data Base Task Group) называется записью, при этом в рамках иерархической модели определяются два понятия: тип записи и экземпляр записи.
ИМД свойственна многим реальным древовидным структурам (классификаторы, структуры управления и т. п.). Существуют графовая и табличная формы представления данных ИМД. Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева.
 

не содержит циклов.
Иерархическая древовидная структура, ориентированная от корня определяется условиями:
иерархия

начинается с корневого узла, который находится на первом уровне иерархии;
на нижних уровнях находятся порожденные узлы;
каждый порожденный узел, находящийся на і-том уровне, связан непосредственно с одним исходным (родительским) узлом, находящимся на (і-1) уровне иерархии;
каждый исходный узел может иметь один или несколько непосредственно порожденных узлов;
доступ к порожденному узлу осуществляется через его исходный узел;
существует единственный иерархический путь доступа к узлу, начиная от корня дерева (рис. 2.).
 
 

– «сверху-вниз», «слева-направо».
Манипулирование данными: Примерами типичных операторов манипулирования иерархически организованными

данными могут быть следующие операторы:
найти указанное дерево БД;
перейти от одного дерева к другому;
перейти от одной записи к другой внутри дерева (например, от группы - к первому студенту);
перейти от одной записи к другой в порядке обхода иерархии;
вставить новую запись в указанную позицию;
удалить текущую запись.
Ограничения целостности: Автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя.
 
 

Integrated Database Management System (IDMS) компании Cullinet Software, Inc. Архитектура

системы основана на предложениях Data Base Task Group (DBTG) Комитета по языкам программирования (Conference on Data Systems Languages - CODASYL). Отчет DBTG был опубликован в 1971 г., а в 70-х годах появилось несколько систем, среди которых IDMS.
Сетевой подход к организации данных является расширением иерархического. В иерархических структурах запись-потомок должна иметь в точности одного предка; в сетевой структуре данных потомок может иметь любое число предков.
Сетевая БД состоит из набора записей, соответствующих каждому экземпляру объекта предметной области, и набора связей между этими записями.
Простой пример сетевой схемы БД приведен на рис.4.
 

Циклом называется ситуация, в которой исходный узел является в то

же время порожденным узлом.
В некоторых случаях один элемент данных может быть связан с целой совокупностью других элементов данных. Например, одно изделие может поставляться несколькими поставщиками, каждый из которых установил свою цену. Элемент данных ЦЕНА не может быть ассоциирован только с записью ИЗДЕЛИЕ или только с записью ПОСТАВЩИК, а должен быть связан с двумя этими записями. Данные, ассоциированные с совокупностью записей, называют данными пересечения.
Любую сетевую модель можно представить в виде иерархической путем введения избыточности (рис.5). Сеть преобразуется в дерево указанием некоторых узлов дважды. Пациент, сотрудник, вкладчик – на эти три записи расчленилась запись житель. При этом часть полей в этих записях будут дублированными (например, поле ФИО).



 

найти конкретную запись в наборе однотипных записей (инженера Сидорова);
перейти

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



 

данными во внешней памяти на низком уровне;
возможность построения вручную

эффективных прикладных систем;
возможность экономии памяти за счет разделения подобъектов (в сетевых системах).
Недостатки дореляционных СУБД:
слишком сложно пользоваться;
фактически необходимы знания о физической организации данных;
прикладные программы зависят от физической организации;
логика прикладных программ перегружена деталями организации доступа к БД.



 

модели определяет способ размещения данных в среде хранения и способы

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

выделить следующие аспекты проблемы физического представления данных:

Как найти нужную запись?

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

основные факторы, влияющие на физическую организацию данных для конкретных БД:
произвольная

или последовательная обработка данных. Для определения вида обработки используют коэффициент активности файла (k)
k=z1/z ,
где z1 – число записей, считанных за 1 прогон;
z - число записей, просмотренных за 1 прогон.
Если k высок, то используют последовательную обработку, например при расчете заработной платы;
частота обращения к определенным записям;
время ответа (важно для систем реального времени);
способность к расширению (особенно, если добавляется записей больше, чем уничтожается);
возможность организации поиска по нескольким ключам.

поиска записей
Последовательное сканирование файла с проверкой ключа каждой записи. Такой

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

как файл — это линейная последовательность записей, то всегда в

файле можно определить текущую запись, предшествующую ей и следующую за ней. Всегда существует понятие первой и последней записи файла.
В соответствии с методами управления доступом различают устройства внешней памяти с произвольной адресацией (магнитные и оптические диски) и устройства с последовательной адресацией (магнитофоны, стримеры).
Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (УПД), являются файлами прямого доступа.
В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи (NZ).
Для файлов с постоянной длиной записи адрес размещения записи с номером K может быть вычислен по формуле:
ВА + (К- 1) * LZ + 1,
где ВА — базовый адрес, LZ — длина записи.

устройствах последовательного доступа могут быть организованы файлы только последовательного доступа.
Файлы

с переменной длиной записи всегда являются файлами последовательного доступа. Они могут быть организованы двумя способами:
Конец записи отличается специальным маркером.
В начале каждой записи записывается ее длина.
При организации файлов прямого доступа в некоторых очень редких случаях возможно построение функции, которая по значению ключа однозначно вычисляет адрес (номер записи файла).
NZ = F(K),
где NZ — номер записи, K — значение ключа, F( ) — функция.
Когда не удается построить взаимно-однозначную функцию, либо эта функция будет иметь множество незадействованных значений, которые соответствуют недопустимым значениям ключа применяют различные методы хэширования (рандомизации) и создают специальные хэш- функции.

методов хэширования состоит в том, что берутся значения ключа (

или некоторые его характеристики) и используются для начала поиска, то есть вычисляется некоторая хэш-функция h(k) и полученное значение берется в качестве адреса начала поиска.
Допускается, что нескольким разным ключам может соответствовать одно значение хэш-функции (то есть один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами.
Поэтому при использовании хэширования как метода доступа необходимо принять два независимых решения:
выбрать хэш-функцию;
выбрать метод разрешения коллизий.

данных
Для ускорения доступа к записям по ключевому атрибуту (или группе

атрибутов) создаётся специальная структура – индекс, который определяет соответствие значения атрибута (группы атрибутов) и местоположение записи.
Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс.
Сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.
В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом.

с плотным индексом, или индексно-прямые файлы
Рассмотрим файлы с плотным индексом.

В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:
Значение ключа Номер записи

Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
Так как индексные файлы строятся для первичных ключей, однозначно определяющих запись, то в них не может быть двух записей, имеющих одинаковые значения первичного ключа. В индексных файлах с плотным индексом для каждой записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном пространстве.

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

в количестве обращений к устройству внешней памяти, которым обычно является диск. Именно обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в оперативной памяти.
Наиболее эффективным алгоритмом поиска на упорядоченном массиве является логарифмический, или бинарный, поиск. Максимальное количество шагов поиска определяется двоичным логарифмом от общего числа элементов в искомом пространстве поиска:
Tn = log2N,
где N — число элементов.
При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения)

с неплотным индексом, или индексно-последовательные файлы
Неплотный индекс строится именно для

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

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

если первичным ключом являются целые числа.

процедуры добавления и удаления новой записи при подобном индексе.
Здесь новая

запись должна заноситься сразу в требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новую запись, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, так же как и в первом случае, должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL server этот процент называется Full-factor и используется при формировании кластеризованных индексов.
Кластеризованными называются как раз индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется. Уничтожение записи происходит путем ее физического удаления из основной области, при этом индексная область обычно не корректируется, даже если удаляется первая запись блока. Поэтому количество обращений к диску при удалении записи такое же, как и при добавлении новой записи.

индексов в виде B-tree (В-деревьев)
Построение В-деревьев связано с простой идеей

построения индекса над уже построенным индексом. Действительно, если мы построим неплотный индекс, то сама индексная область может быть рассмотрена нами как основной файл, над которым надо снова построить неплотный индекс, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок.
Мы в общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными (balanсed) именно потому, что путь от корня до любого листа в этом древе одинаков. Именно термин "сбалансированное" от английского "balanced" — "сбалансированный, взвешенный" и дал название данному методу организации индекса.

том случае, если каждому значению индекса соответствует уникальное значение ключа,

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

индексы на основе В-дерева
Типичное В–дерево содержит три уровня: корневую вершину,

промежуточную вершину и листья, хотя способно включать и промежуточное количество уровней.
В В–дереве ключевые значения, указанные в вершинах-листьях, являются копиями ключей записей файла данных. Ключи распределены по вершинам листьям слева направо в порядке возрастания значений.
B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева являются порядок n и количество уровней. Порядок – это количество ссылок из вершины i-го уровня на вершины (i+1)-го уровня.
Каждое B-дерево должно удовлетворять следующим условиям:
1. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с меньшими по значению ключами, а вправо – к вершине с большими ключами.
2. Любая неконечная вершина имеет не менее n/2 подчинённых вершин.
3. Если неконечная вершина содержит k (k € n) ключей, то ей подчинена (k+1) вершина на следующем уровне иерархии.
4. Все конечные вершины расположены на одном уровне.

индексные файлы используются для ускорения доступа по первичному ключу, то

для ускорения доступа по вторичному ключу используются структуры, называемые инвертированными списками. Вторичными ключами является атрибут или набор атрибутов, которому соответствует несколько искомых записей. Например, для таблицы «Книги» вторичным ключом может служить место издания, год издания. Множество книг могут быть изданы в одном месте, и множество книг могут быть изданы в одном году.
Инвертированный список в общем случае – это трехуровневая индексная структура.
На первом уровне находится файл или часть файла, в которой упорядоченно расположены значения вторичных ключей. Каждая запись с вторичным ключом имеет ссылку на номер первого блока в цепочке блоков, содержащих номера записей с данным значением вторичного ключа.
На втором уровне находится цепочка блоков, содержащих номера записей с одним и тем же значением вторичного ключа. При этом блоки второго уровня упорядочены по значениям вторичного ключа.
На третьем уровне находится основной файл с записями.

механизм доступа к записям по вторичному ключу:
Шаг_1. В области первого

уровня ищется заданное значение вторичного ключа;
Шаг_2.По ссылке считываются блоки второго уровня, содержащие номера записей с заданным значением вторичного ключа;
Шаг_3. В рабочую область пользователя прямым доступом загружается содержимое всех записей с заданным значением вторичного ключа.
Для одного основного файла может быть создано несколько инвертированных списков по разным вторичным ключам. Однако при модификации основного файла требуется внести изменения во все инвертированные списки. Поэтому можно утверждать, что построение инвертированных списков ускоряет процесс доступа только в том случае, если БД стабильна и ее содержимое не изменяется.
Для моделирования связей на файловых структурах используется принцип организации цепочек записей внутри файла и ссылки на номера записей для нескольких взаимосвязанных файлов. Цепочка – это совокупность записей, расположенных в разных местах и связанных последовательностью указателей

файла с цепочкой может быть условно представлена в виде:
Ключ

Запись Ссылка-указатель на следующую запись

Для моделирования отношения один-ко-многим связываются два файла, например F1 и F2, причем предполагается, что одна запись в файле F1 может быть связана с несколькими записями в файле F2. Структура файла F1 может быть условно представлена:
<Ключ> <Запись> <Ссылка-указатель на первую запись в файле F2, с которой начинается цепочка записей файла, связанных с данной записью файла F1>
Структура записи файла F2 имеет вид:
<Указатель на следующую запись в цепочке> <Содержимое записи>

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

эффективного управления ресурсами и/или для технологического удобства всё пространство памяти БД обычно разделяется на части (области, разделы и др.). (Во многих системах область соответствует файлу). Области памяти используются для размещения хранимых записей одного или нескольких типов и разбиваются на пронумерованные страницы фиксированного размера. В большинстве систем обработку данных на уровне страниц ведёт операционная система (ОС), а обработку записей внутри страницы обеспечивает только СУБД.
Реляционные СУБД хранят во внешней памяти БД:
строки таблиц - основная часть БД;
управляющие структуры - индексы, создаваемые по инициативе пользователя (администратора) из соображений повышения эффективности выполнения запросов;
журнальная информация, поддерживаемая для удовлетворения потребности в надежном хранении данных;
служебная информация.

используемые в указанной классификации.
Чанк (chank) — представляет собой часть диска,

физическое пространство на диске, которое ассоциировано одному процессу (online процессу обработки данных).
Чанк характеризуется маршрутным именем, смещением (от физического начала устройства до начальной точки на устройстве, которая используется как чанк), размером, заданным в Кбайтах или Мбайтах.
Экстент — это непрерывная область дисковой памяти.
Для моделирования каждой таблицы используется 2 типа экстентов: первый и последующие.
Первый экстент задается при создании нового объекта типа таблица, его размер задается при создании. EXTENTSIZE — размер первого экстента, NEXT SIZE — размер каждого следующего экстента.
Минимальный размер экстента в каждой системе свой, но в большинстве случаев он равен 4 страницам, максимальный — 2 Гбайтам.
Внутри экстента идет учет свободных станиц.
Совокупность экстентов моделирует логическую единицу — таблицу-отношение (tblspace).

четырех типов страниц: страницы данных, страницы индексов, битовые страницы и

страницы blob-объектов. Blob — это сокращение Binary Larg Object, и соответствует оно неструктурированным данным.
Основной единицей осуществления операций обмена (ввода-вывода) является страница данных. Все данные хранятся постранично. При табличном хранении данные на одной странице являются однородными, то есть станица может хранить только данные или только индексы.

Хранение данных во внешней памяти в известных СУБД (Oracle, IBM DB2, Microsoft SQL Server, Sybase и Informix и др.) организовано очень похожим образом.

информации включает пространства (либо табличные пространства).
Блок данных (block) или

страница (page) является единицей обмена с внешней памятью. Размер страницы фиксирован для базы данных (Oracle) или устанавливается при создании БД.
Размер блока оказывает большое влияние на производительность базы данных — при больших размерах скорость операций чтения/записи растет, однако возрастают накладные расходы на хранение (база увеличивается) и снижается эффективность индексных просмотров. Меньший размер блока позволяет более экономно расходовать память, но вместе с тем относительно дорог. Длинные блоки (16, 32 или 64 Кбайт) лучше использовать для больших объектов данных: полнотекстовые фрагменты, мультимедиа-объекты, длинные строки и т.п. Короткие блоки (2 или 4 Кбайт) лучше подходят для значений числовых типов, недлинных строк, значений даты и времени

отведенным администратором, СУБД управляет с помощью экстентов (extent) или областей,

т.е. непрерывных последовательностей блоков (страниц). Экстенты представляют собой единицу выделения памяти для таблиц и индексов.
На управление экстентами (выделение пространства, освобождение, слияние) тратятся определенные ресурсы, поэтому для достижения эффективности нужно правильно определять их параметры. СУБД от Oracle, IBM, Informix позволяют определять параметры этих структур, а в Sybase экстенты имеет постоянный размер, равный 8 страницам.
В Informix существует еще одна единица физического хранения, промежуточная между файлом (или разделом диска) и экстентом, — это «чанк» (от английского chunk, что дословно переводится как «емкость»). Чанк позволяет более гибко управлять очень большими массивами внешней памяти. В одном разделе диска или файле администратор может создать несколько чанков.

данные на одной странице являются однородными, т. е. страница может

содержать только данные или только индексы.
 Заголовок страницы содержит системную информацию: идентификатор объекта данных, которому принадлежит страница; логический номер страницы; логические номера следующей и предыдущей страниц в цепочке; номер следующей свободной строки на странице. В конце страницы располагается таблица смещения строк.
Местоположение строки на странице определяется таблицей смещения строк (Row offset table). Таблица располагается в самом конце страницы и забирает дополнительно по 2 байта на каждую строку данных. Чтобы найти строку с заданным номером, SQL Server считывает из соответствующей ячейки смещение, которое и является адресом требуемой строки. Ячейка таблицы однозначно связана с определенным номером строки.
Страницы данных, относящиеся к одной таблице, объединяются в двунаправленный список и организуют цепочки.
Данные хранятся на страницах в виде строк (кортежей). Каждая строка данных кроме собственно данных хранит дополнительную форматирующую информацию. Длина строки зависит от определения полей таблицы и конкретных данных в ней.

механизмы, позволяющие решать проблемы, которые возникают при модификации данных в

БД, например:
Удаление записей может быть логическим или физическим. В первом случае запись помечается как удаленная, но фактически она остаётся на прежнем месте. Фактическое удаление этой записи будет произведено либо при реорганизации БД, либо специальной сервисной программой, инициируемой администратором БД.
При физическом удалении ранее занятый участок освобождается и становится доступным для повторного использования. Система автоматически управляет свободным пространством памяти на страницах. Как правило, это обеспечивается либо ведением списков свободных участков, либо динамической реорганизацией страниц.
При динамической реорганизации страниц записи БД плотно размещаются вслед за заголовком страницы, а после них расположен свободный участок. Смещение начала свободного участка хранится в заголовке страницы. При удалении записи оставшиеся записи переписываются подряд в начало страницы и изменяется смещение начала свободного участка.

данных
Единицей хранения данных в БД является хранимая запись. Она может представлять

как полную запись концептуального уровня, так и некоторую её часть. Если запись разбивается на части, то её фрагменты представляются экземплярами хранимых записей каких-либо типов. Все части записи связываются указателями (ссылками).
Хранимые записи одного типа состоят из фиксированной совокупности полей и могут иметь формат фиксированной или переменной длины.
Хранимая запись состоит из двух частей:
1. Служебная часть. Используется для идентификации записи, задания её типа, хранения признака логического удаления, для кодирования значений элементов записи, для установления структурных ассоциаций между записями. Никакие пользовательские программы не имеют доступа к служебной части хранимой записи.
2. Информационная часть. Содержит значения элементов данных.
Каждой записи БД система присваивает внутренний идентификатор, называемый (по стандарту CODASYL) ключом базы данных (КБД). Значение КБД формируется системой при размещении записи и содержит информацию, позволяющую однозначно определить место размещения записи (её адрес). В качестве КБД может выступать, например, последовательный номер записи в файле или совокупность адреса страницы и смещения от начала страницы.

к БД
Опишем последовательность действий при доступе к БД (см. рис):
Сначала

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

ДД – диспетчер дисков
Схема

доступа к БД

запрос хранимых записей

запрос хранимых страниц

дисковые операции ввода/
вывода

набора обладает уникальным идентификационным номером страницы. Соответствие физических адресов на

диске и номера станицы достигается с помощью ДД.
Преимущества страничной организации - все компоненты высокого уровня не зависят от конкретного диска.
Диск – это набор хранимых файлов. Файл – хранимый набор однотипных записей. В общем случае хранимый файл может храниться в памяти различными способами:
на одном томе памяти (диске);
на нескольких томах;
физически упорядоченным в соответствии со значением некоторого хранимого поля;
упорядоченным с помощью одного или нескольких индексов;
упорядоченным с помощью цепочек указателей;
к нему может быть обеспечен доступ методом хэш-адресации;
хранимые записи могут быть объединены в блоки (несколько логических записей в одной физической записи).
Набор страниц может содержать несколько хранимых файлов. Каждый хранимый файл имеет имя или идентификационный номер (file ID), уникальный в данном наборе страниц. А каждая хранимая (логическая) запись обладает идентификационным номером (record ID).

следующие операции с файлами:
извлечь хранимую запись r из хранимого файла

f;
заменить хранимую запись r в хранимом файле f;
удалить хранимую запись r из хранимого файла f;
добавить новую хранимую запись r в хранимый файл f;
создать новый хранимый файл f;
удалить хранимый файл f.
В одних СУБД ДФ – компонент ОС, а в других – СУБД.
Все страницы диска делятся на несвязанные наборы. Один из наборов, набор пустых страниц, - свободное пространство на диске.
Операции, выполняемые ДД с наборами страниц:
извлечь страницу P из набора S;
заменить страницу P в наборе S;
добавить новую страницу в набор S (извлечь ее из набора пустых страниц и добавить в набор S);
удалить страницу P из набора S (поместить ее в набор пустых страниц).

(Р1, Р2, Р3, Р4, Р5); ДЕТАЛИ (Д1, Д2, Д3, Д4,

Д5, Д6); ПОСТАВКИ (РД1, РД2, РД3, РД4, РД5, РД6). Для размещения БД будет создан набор страниц:

с номером 0 хранится информация о структуре БД:
количестве записей

в таблицах;
их распределении по страницам;
о номерах и количестве пустых страниц.
Выполним действия по модификации БД.
Добавить запись о поставщике Р6.
Для этого ДФ вставляет новую хранимую запись,
а ДД ищет первую пустую страницу (18),
а затем добавляет ее к набору страниц поставщиков.
Удалить запись о поставщике Р2.
ДФ удаляет запись,
а ДД возвращает страницу 2 в набор пустых страниц.
Добавить новую запись о детали Д7.
Для этого ДФ вставляет новую хранимую запись,
а ДД ищет первую пустую страницу (2),
а затем добавляет ее к набору страниц о деталях.

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

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

документальных моделей.
Какие компоненты входят в структуру логической (даталогической) модели?
Назовите структуры

данных иерархических моделей.
Что включает в себя физическая модель данных?
Чем характеризуется последовательный доступ к данным?
Чем характеризуется прямой (произвольный) доступ к данным?
Какие методы адресации используются для ускорения доступа к данным?
Дайте характеристику методу хеширования.
Опишите алгоритм адресации с использованием индексно-последовательного файла?
Что такое страница данных? Опишите ее структуру.
Укажите последовательность действий доступа к данным.
Как связаны страницы данных в наборе?
Укажите последовательность действий по добавлению записи о поставках РД7 (пример 1).
Укажите последовательность действий по удалению записи о детали Д1 (пример 1).