· ограничения целостности - механизм поддержания соответствия данных предметной области на основе формально описанных правил.
В процессе исторического развития в СУБД использовалось следующие модели представления данных:
· иерархическая: строится по принципу иерархии типов объектов, Т.е. один тип объекта является главным, а остальные, находящиеся на низших уровнях иерархии, подчиненными(взаимосвязь «один ко многим»))
· сетевая: понятия главного и подчиненного несколько расширены; любой объект может быть и главным и подчиненным; означает, что каждый объект может участвовать в любом числе взаимосвязей.
· реляционная: объекты и взаимосвязи между ними представляются с помощью таблиц.
В настоящее время наибольшую популярность приобрели реляционные модели данных, т.к их применение по ряду причин было выбрано программистами-разработчиками наиболее удобным. Как выяснилось, практически все СУБД сейчас ориентированы именно на такое представление данных. Реляционная модель была предложена в 1970-х гг. Тедом Коддом, работавшим тогда в IВM.
Реляционную модель можно представить как особый метод рассмотрения данных, содержащий и собственно данные (в виде таблиц), и способы работы и манипуляции с ними (в виде связей).
В последнее время все большее значение приобретает объектно-ориентированный подход к представлению данных.
Физическая организация баз данных
Физическая организация данных определяет собой способ непосредственного размещения данных на машинном носителе. В современных прикладных программных средствах этот уровень организации обеспечивается автоматически без вмешательства пользователя. Пользователь, как правило, оперирует в прикладных программах и универсальных программных средствах представлениями о логической организации данных.
Организация данных во внешней памяти
Каждая БД, как известно, состоит из файлов. Файлы состоят из логических записей. Данные хранятся во внешней памяти на соответствующих носителях (магнитные ленты, диски, "винчестеры" и др.). Каждый файл представляется в виде одного или нескольких блоков (страниц) данных. В одном блоке может быть одна логическая запись, несколько записей (блокированные записи), часть ее (сегмент). В последнем случае сегменты одной записи хранятся в разных блоках. Адресные ссылки между сегментами позволяют выбрать запись целиком в оперативную память.
Обмен данными между внешней и оперативной памятью выполняется блоками, т.е. блок - минимальная единица обмена между оперативной памятью и внешним носителем. При чтении с внешнего носителя блок данных размещается в буферный участок памяти. Несколько буферов образуют буферный пул. Каждый байт в блоке пронумерован (0, 1, 2,...). Номер байта блока, с которого начинается запись, определяет относительный адрес записи файла в блоке.
В качестве адресов записей файла во внешней памяти используют: машинный адрес, относительный адрес, ключ записи. В качестве относительного адреса записи файла используют ее номер по порядку (внутрисистемный номер) в файле, либо комбинацию номера блока и относительного адреса в блоке, либо номер блока и значение ключа. Во многих системах при вводе записи ей присваивается уникальный системный идентификатор - ключ базы данных. Ключ БД не следует отождествлять с ключом записи. Последний задается и используется пользователем (прикладной программой).
Данные, которые присутствуют в физической БД, но отсутствуют в логической БД, называют прозрачными. Такие данные никогда не представляются пользователю (например, адресные ссылки, ключ БД, различные счетчики в т.п.). Данные, которые присутствуют в логической БД, но отсутствуют в физической БД, называются виртуальными (например, возраст).
Каждая физическая запись, соответствующая логической, состоит обычно из двух частей - служебной и информационной. Поля служебной (прозрачной) части используются СУБД для идентификации записи, задания ее типа, хранения признака логического удаления, для кодирования значений элементов, для установления структурных связей между записями. Никакие пользовательские программы не имеют доступа к служебной части записи.
Поля информационной части содержат значения элементов данных логической записи. При этом существует два основных способа размещения значений элементов в физической записи:
1. Размещение с заранее предписанных позиций предполагает, что значение элемента в каждом экземпляре записи появляется с одной и той же позиций, определенной в описании БД.
2. Размещение с разделителями позволяет не хранить в памяти незначащие символы. Здесь элементы отделяются друг от друга разделителями (специальными кодами, часто со смысловой нагрузкой, например, с указанием длины размещенного за ним значения). Если длина элементов варьируется, то память расходуется более экономно, но требуются дополнительные затраты времени м рас кодировку записи. Записи могут быть фиксированной и переменной длины.
Записи обычно размещаются в блоках плотно, без промежутков, последовательно одна за другой. В блоке часть памяти отводится также для служебной информации о блоке: относительные адреса свободных участков памяти, указатели на следующий блок и т.д.
Обычно блоки заполняются не полностью. Оставшаяся часть блока остается некоторое время незаполненной (зарезервированной). В дальнейшем эта область заполняется при увеличении (расширении) записей, хранящихся в блоке, или при поступлении в систему новых записей, которые в соответствии со значениями их ключей (или по другим условиям) надо поместить в одном блоке с уже хранящимися записями. По истечении некоторого времени блок заполняется полностью. Для хранения новых поступающих данных, которые должны были бы попасть в этот блок, выделяется дополнительный блок памяти в области переполнения. Записи, которые должны были размещаться в одном блоке, связываются специальными указателями в одну цепь. Файл периодически реорганизуется: при необходимости файлу добавляется требуемое количество блоков в основной внешней памяти и выполняется требуемая перекомпоновка записей, с целью освобождения области переполнения внешней памяти.
Методы доступа к данным
Как уже неоднократно упоминалось, простой пользователь не имеет дело с самой базой данных, а работает в прикладных программах. Следовательно появляется задача организации доступа к БД.
Вопросы представления данных тесно связаны с операциями, при помощи которых эти данные обрабатываются. К числу таких операций относятся: выборка, изменение, включение и исключение данных. В основе всех перечисленных операций лежит операция доступа, которую нельзя рассматривать независимо от способа представления.
В задачах поиска предполагается, что все данные хранятся в памяти с определенной идентификацией и, говоря о доступе, имеют в виду прежде всего доступ к данным (называемым ключами), однозначно идентифицирующим связанные с ними совокупности данных.
Пусть нам необходимо организовать доступ к файлу, содержащему набор одинаковых записей, каждая из которых имеет уникальное значение ключевого поля. Самый простой способ поиска - последовательно просматривать каждую запись в файле до тех пор, пока не будет найдена та, значение ключа которой удовлетворяет критерию поиска. Очевидно, этот способ весьма неэффективен, поскольку записи в файле не упорядочены по значению ключевого поля. Сортировка записей в файле также неприменима, поскольку требует еще больших затрат времени и должна выполняться после каждого добавления записи. Поэтому, поступают следующим образом - ключи вместе с указателями на соответствующие записи в файле копируют в другую структуру, которая позволяет быстро выполнять операции сортировки и поиска. При доступе к данным вначале в этой структуре находят соответствующее значение ключа, а затем по хранящемуся вместе с ним указателю получают запись из файла.
Существуют два класса методов, реализующих доступ к данным по ключу:
· методы поиска по дереву
· методы хеширования.
Методы поиска по дереву
Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:
· между узлами имеет место отношение типа "исходный-порожденный";
· есть только один узел, не имеющий исходного. Он называется корнем;
· все узлы за исключением корня имеют только один исходный;
· каждый узел может иметь несколько порожденных;
· отношение "исходный-порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.
Число порожденных отдельного узла (число поддеревьев данного корня) называется его степенью. Узел с нулевой степенью называют листом или концевым узлом. Максимальное значение степени всех узлов данного дерева называется степенью дерева.
Если в дереве между порожденными узлами, имеющими общий исходный, считается существенным их порядок, то дерево называется упорядоченным. В задачах поиска почти всегда рассматриваются упорядоченные деревья.
Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказвается меньше ключа, поиск продолжается в левом поддереве, а в случае когда больше ключа - в правом поддереве. Увеличив уровень на 1 повторяют сравнение, считая текущий узел корнем.
Пример: Пусть дан список студентов, содержащий их фамили и средний бал успеваемости (см. таблицу 1.1). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычислятся как ([номер_записи] -1 ) * [длина_записи]. Пусть аргумент поиска "Петров". На рисунке 1.2 показаны одно из возможных для этого набора данных бинарных деревьев поиска и путь поиска.