Эволюция баз данных

Методы доступа к данным

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

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

При использовании индексно-произвольного метода индекс со-

держит ключ (уникальный идентификатор) записи и ссылку на ее физическое местоположение. Записи могут располагаться в файле в

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

6Физический адрес состоял из номера устройства, номера дорожки и номера «цилиндра» на диске или пакете дисков.

21

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

Рис. 11. Индексно-последовательный и индексно-произвольный методы доступа

Приведенное описание методов доступа иллюстрирует лишь базовые идеи, получившие сегодня дальнейшее развитие. Так, развитием прямого метода доступа является хеширование, состоящее в поиске функции, однозначно преобразующей ключ записи в ее физический адрес. Развитием последовательного доступа является бинарный поиск и В-деревья. Индексная организация также существенно усложнилась – сегодня используются многоуровневые, вторичные и другие индексы.

2.2. Базы данных на «плоских» файлах

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

Табельный номер, Фамилия, Имя, Отчество… Ширину каждого

22

столбца мы подберем исходя из самого длинного элемента. Каждая строка этой таблицы будет описывать одного конкретного человека. А сама таблица будет называться РАБОТНИК 7.

Теперь сопоставим понятия: таблица – файл, строка таблицы – запись файла. Содержимое строки может заноситься в запись двумя способами (рис. 12):

1)в виде простого списка, элементы которого отделяются друг от друга каким-либо специальным символом, например, точкой с запятой;

2)запись разбивается на поля фиксированной длины, равной ширине соответствующих столбцов таблицы; после чего элементы информации заносятся в соответствующие поля.

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

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

стых или «плоских» файлов (flat file, англ.).

Рис. 12. Представление данных в виде плоских файлов с разделителями и полями фиксированной длины

Однако было бы слишком большим упрощением считать, что в один прекрасный день обычные структурированные файлы стали называть базами данных. В обычной файловой системе не были ре-

7Здесь и далее в примерах прописными буквами записывается название объекта, строчными с первой прописной – название свойства объекта, курсивом – значения свойств, полужирным шрифтом – название связи

23

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

Несмотря на почтенный возраст идея плоских файлов эксплуатируется до сих пор (табл. 1). Безусловное преимущество этой модели физической организации данных состоит в ее простоте.

		Таблица 1
	СУБД, основанные на плоских файлах
СУБД	Производитель	История и характеристика
GNU	Фонд свободно распро-	Запись содержит произвольное ко-
Recutils	страняемого ПО (Free	личество именованных полей
	Software Foundation)
BDB	University of California,	Начиная с 1994 г. вышли четыре
(Berkeley	Berkeley. В 2006 г. пра-	версии, в основном, для открытых
DB)	ва на производство	ОС, включая Linux. Первые версии
	перешли к Oracle	(до перехода в Oracle) не поддер-
		живали SQL
Borland	Analytica, купленная	Разработана в 1980-х гг. для DOS.
Reflex	затем компанией Bor-	Один из разработчиков Reflex пе-
	land	решел в Microsoft и основал там
		проект СУБД ACCESS

2.3. Базы данных с инвертированными списками

Одной из самых сложных задач в работе с плоскими файлами стал поиск и доступ к нужной записи. Наиболее эффективным решением этой задачи являлось и до сих пор является индексирование записей по первичному ключу. Предположим, в базе данных (плоском файле) хранятся записи о работниках предприятия, включающие в себя следующие поля (табл. 2): РАБОТНИК (Табельный номер, Фамилия И.О., Дата рождения, Пол, Отдел, Должность).

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

24

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

Поиск по вторичным ключам существенно облегчится, если для каждого такого ключа создать свой индекс. В таблице 3 показаны такие индексы для полей Отдел и Пол. Эти индексы получили на-

звание инвертированных списков (inverted list, англ.)8.

		Список работников предприятия							Таблица 2
Табель-				Дата рож-
ный	Фамилия И.О.				Пол		Отдел		Должность
номер				дения
12	Петров С.В.			21.09.1978	М	Аналитический			Начальник
427	Иванова И.В.			18.07.1963	Ж	Аналитический			М.н.с.
732	Павлова В.Н.			23.01.1967	Ж	Моделирования			С.н.с.
925	Алексеев А.С.			21.07.1971	М	Моделирования			С.н.с.
1376	Сидоров А.Г.			13.05.1958	М	Аналитический			Аналитик
									Таблица 3
	Инвертированные списки по отделу (слева) и полу (справа)
Отдел		Список табельных				Пол		Список табельных
			номеров					номеров
Аналитический		12, 427, 1376				Ж		427, 732
Моделирования		732, 925				М		12, 925, 1376

На инвертированных списках и файлах были построены одни из первых промышленных СУБД, получивших в начале 1970-х гг. широкое распространение (табл. 4).

2.4. Иерархические базы данных

Как правило, любая предметная область содержит не один, а несколько объектов, о которых нужно хранить информацию. Очевидно, что для каждого из таких объектов может быть создан свой файл. Является ли совокупность этих файлов базой данных? И да, и нет. Такой же вопрос можно задать себе, пользуясь бумажной картотекой в библиотеке. Да, безусловно, это база данных, к тому же

8Другие названия – инвертированный индекс, инвертированная таблица,

инвертированный файл (inverted index, postings file, inverted file, англ.).

25

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

		Таблица 4
	СУБД, основанные на инвертированных списках
СУБД	Производитель	История и характеристика
ADABAS	Software AG (Германия)	1970 г. – первая версия ADABAS
		(Adaptable DAta BAse System) для
		IBM/360. Сегодня существует для
		широкого класса операционных
		систем, включая Windows, Unix,
		OpenVMS. Не поддерживает SQL
ДИСОД		Советский аналог ADABAS для ЕC
		ЭВМ
ТРИАДА		Советский аналог ADABAS для СМ
		ЭВМ
Datacom/	ADR (Applied Data Re-	Первая версия появилась в конце
DB	search) (США), в 1978 г.	1960-х гг. С переходом в Computer
	куплена компанией	Associates переименована в CA
	Computer Associates	Datacom
Model	CCA (Computer Corpo-	1972 г. – первая версия для
204	ration of America) (США)	IBM/360. Использует различные
	в 2010 г. куплена ком-	комбинации индексных списков,
	панией Rocket Software	включая собственные конструкции

Предположим, проектируя программу, мы решили найти книгу, где описаны основные алгоритмы поиска и сортировки данных. Подойдя к тематическому каталогу, находим ящик с надписью «Программирование» и начинаем поиск нужной книги, перебирая карточки. Наткнувшись на «Искусство программирования» Д. Кнута, вспоминаем о фразе, брошенной преподавателем на лекции, что Кнут – великий автор для тех, кто хочет научиться алгоритмически мыслить. Естественно, книгу нужно брать. А еще лучше посмотреть и другие книги Д. Кнута – вдруг в них есть более новая или более интересная информация. Идем к авторскому каталогу, находим ящик с буквой «К» и перебираем карточки, добравшись до фамилии Кнут. Казалось бы, задача решена! Однако наш поиск закончится успешно только в том случае, если в остальных книгах Кнут является единственным или первым автором. Если же его фа-

26

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

Итак, мы имеем хорошо структурированную и упорядоченную информацию. Однако проблемы остаются: нам приходится переходить от каталога к каталогу (от файла к файлу), держа в уме фамилию автора, к тому же мы не всегда можем быстро найти нужную карточку (запись). Очевидно, что современное поколение пользователей скажет: «Все просто, нужно установить связи, прописать гиперссылки и готово…». Действительно, связь – это ключевое слово, отличающее базу данных от простого файла или набора файлов. Но как представить эту связь в базе данных?

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

ляр сегмента. Экземпляр сегмента – это некоторая логическая за-

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

Схема иерархической базы данных представляет собой дерево, вершинами которого являются типы сегментов (рис. 15). Между типами сегментов установлены отношения «исходный-порожден- ный». Тип сегмента, у которого нет предка, называется корневым. На уровне экземпляров каждое такое отношение реализуется в виде связей между одним экземпляром сегмента-родителя и несколькими экземплярами сегмента-потомка. Таким образом, иерархическая база данных – это совокупность деревьев, корнями которых являются экземпляры корневого типа сегмента. Каждое такое дерево называется набором и образует физическую запись иерархической базы данных. Так, например, набор, принадлежащий отделу D1, представляет собой следующую последовательность экземпляров сегментов: {D1, E1, E2, E3, P1, T1, T2, T3, P2, T4, T5}, где D1 – эк-

27

земпляр сегмента ОТДЕЛ (Department), E1-E3 – экземпляры сегмента РАБОТНИК (Employee), P1, P2 – экземпляры сегмента ПРОЕКТ

(Project), T1-T5 – экземпляры сегмента ЗАДАЧА (Task).

Рис. 13. Схема иерархической базы данных

Рис. 14. Экземпляры сегментов иерархической базы данных

Рис. 15. Дерево типов (слева) и экземпляров (справа) сегментов

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

(HSAM, Hierarchical Sequential Access Method), иерархический пря-

мой (HDAM, Hierarchical Direct), иерархический индексно-последо-

28

вательный (HISAM, Hierarchical Indexed Sequential) и иерархический индексно-произвольный (Hierarchical Indexed Direct).

Первой и непревзойденной по сегодняшний день промышлен-

ной иерархической СУБД стала IMS (Information Management System, англ.), созданная корпорацией IBM в 1969-1970 гг. (табл. 5).

		Таблица 5
	Иерархические СУБД
СУБД	Производитель	История и характеристика
IMS	IBM (США)	1968 г. – первая версия IMS для
		IBM/360. Сегодня издана 12-я вер-
		сия с поддержкой Java, XML и др.
ИНЕС	ВНИИСИ и ИПУ АН	1976 г. – первая версия ИНЕС (ин-
	СССР (СССР)	формационная единая система)
		для ЕС ЭВМ
ОКА	Институт кибернетики	Советский аналог IMS
	АН УССР (СССР)

Наиболее известной и оригинальной отечественной разработкой является СУБД ИНЕС, созданная специалистами двух академических институтов – системного анализа и проблем управления. Вместе с ЕС ЭВМ ИНЕС развивалась вплоть до конца 1980-х гг.

2.5. Сетевые базы данных

Существенную роль в эволюции и стандартизации баз данных сыграла группа CODASYL (Conference on Data Systems Languages –

конференция по языкам систем обработки данных, англ.), которая была создана в 1959 г. для разработки стандартов по языкам программирования. В 1965 г. в рамках этой группы была сформирована рабочая группа по базам данных (DBTG, Data Base Task Group, англ.)9. Через два года ею была опубликована концепция сетевой базы данных, широко известной также под названием «модель дан-

ных CODASYL».

Идеологом сетевой модели был Чарлз Бахман (Charles Bachman) – один из выдающихся исследователей и практиков в области

9В СССР аналогичная рабочая группа по программному обеспечению банков данных (РГБД) была учреждена Государственным комитетом по науке и технике в 1974 г. и просуществовала до 1984 г. Параллельно, в 1978 г. в Академии наук СССР была учреждена Комиссия по банкам данных и ин- формационно-поисковым системам, функционировавшая до 1991 г. [9].

29

компьютерных наук, удостоенный в 1973 г. премии Тьюринга за вклад в развитие баз данных. Он родился в США в 1924 г., окончил университет штата Пенсильвания. Бахман предложил разделить логическое и физическое описание данных. Архитектура базы данных CODASYL стала прообразом современных архитектур и включала в себя

схему, отражающую полную логическую структуру данных;

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

кладных программ; описание физической структуры данных, т.е. физическую орга-

низацию полей, записей и связей между ними.

Для работы с такой базой данных были предложены два языка:

язык определения данных (ЯОД) (DDL, Data Definition Language,

англ.), позволяющий задавать структуру данных, и язык манипули-

рования данными (ЯМД) (DML, Data Manipulation Language), обес-

печивающий доступ и изменение данных. Операторы этих языков были «встроены» в два языка программирования того времени –

COBOL (Common Business-Oriented Language) и PL/1 (Programming Language One).

Элементарными единицами данных в модели CODASYL являются элемент и агрегат данных, совокупность которых образует запись (рис. 16) (более подробно модель CODASYL описана в [9]). Записи, имеющие одинаковую внутреннюю структуру и описывающие однородные объекты, объединяются в один тип записи. Между двумя типами записей можно устанавливать связь «один- ко-многим», называемую типом набора, при этом один тип записи объявляется владельцем типа набора, а другой – его членом (рис. 17). Каждая запись первого типа может быть владельцем своего набора, членами которого являются записи второго типа. Физически члены одного набора ссылаются друг на друга с помощью указателей трех видов: указатель на следующего члена набора, указатель на предыдущего члена набора и прямой указатель на владельца набора. По сути, такая модель напоминает современные навигационные структуры информации в Интернете10.

10 Из-за этого дореляционные СУБД называли также «навигационными».

30