Введение в Базы данных

Предисловие


Некоторое время тому назад мы с Громом обсудили ряд интересных, на наш взгляд, направлений информатики, которые почему-то до сих пор не получили освещения на форуме. Одно из таких направлений Системы Управления Базами Данных (СУБД).
Поскольку открывать пустую тему не хотелось бы, начать решили со статей, проливающих свет на этот предмет. Первая из них (и, надеюсь, не последняя) предлагается на суд читателей.
По поводу стиля изложения замечу следующее. Я не ставил перед собой задачу сделать мгновенный снимок текущего состояния СУБД. Вместо этого была предпринята попытка показать краткую предысторию развития методов и средств обработки данных, которая в результате привела к появлению СУБД. Зачастую понять, почему предмет именно таков, намного проще, проследив его эволюцию. Поэтому в начале приведен небольшой исторический обзор событий, каждое из которых, на мой взгляд, сыграло свою роль, пусть и косвенно, в появлении СУБД. Во-первых, на мой взгляд, это просто интересно. Во-вторых, СУБД возникли не на пустом месте. Их появление неизбежный результат решения задач, которые менялись вместе с вычислительными машинами.
Заранее прошу прощения у тех, кто сочтет статью утомительной и малоинформативной. В мои планы не входило написание краткой энциклопедической статьи (полагаю, в них и так нет недостатка). Скорее это обобщение процесса, часть которого протекала на моих глазах.
Часть изложенного материала основана на моем личном опыте и почерпнутых из этого опыта суждениях (думаю, далеко не безупречных). Поэтому буду рад любой конструктивной критике, дополнениям и исправлениям (по существу вопроса).

Alf

Введение


С древних времен перед человечеством стояли задачи, требовавшие все возрастающих объемов вычислений. Естественно, со временем большинство из них находило решения. Еще в античные времена некоторые области математики были настолько развиты, что образованный человек тех лет по уровню знаний вряд ли уступал нынешнему выпускнику школы.
Появление собственности на землю потребовало определения способов вычисления площади участков, что привело к зарождению геометрии. Достижения Евклида, Пифагора и других греческих ученых в этом направлении общеизвестны.
Развитие торговли также ставило все новые задачи. Помимо учета товаров и денежных сумм, появились и более сложные проблемы. Купцам приходилось предпринимать все более дальние путешествия, а для этого потребовались средства навигации. Астрономы древности на удивление искусно справлялись и с этой задачей. Естественно, все в конечном итоге сводилось к расчетам, и чем точнее они были, тем успешнее решались насущные задачи.
Не секрет, что вычислительные способности большинства из нас весьма ограничены. Даже сложить в уме стоимость нескольких мелких покупок и подсчитать сумму сдачи не так уж просто, а уж о расчете орбиты планеты или координат звезды и говорить не приходится. Поэтому наряду с развитием теории лучшие умы бились и над проблемой автоматизации вычислений. Но тут, к сожалению, прогресс шел гораздо медленнее.
Больше тысячи лет единственным помощником человека в вычислениях были различные разновидности счет. Мало изменившись, дошли они и до нашего времени.
Гениальные Паскаль, Лейбниц, Бэббидж и другие пытались построить автоматические машины для вычислений. К сожалению, техника того времени позволяла строить только механические устройства. Механические счетные машины были слишком медленны, дороги и ненадежны для массового применения, поэтому особого распространения не получили. Исключением, пожалуй, стал старый добрый арифмометр по прозвищу Железный Феликс, который не так давно еще верой и правдой служил конторским служащим. Но и он стал доступен относительно недавно (промышленное производство арифмометров было начато в 1822 г.).
Попытки использовать электрические узлы в счетных машинах сделали их совершеннее, и специализированные электромеханические устройства имели успех в некоторых приложениях (например, табуляторы Холлерита для обработки статистических данных весьма успешно применялись при переписи населения США).
Но все же действительно универсальные автоматические вычислительные устройства компьютеры удалось создать только на основе электронных узлов. Для их появления требовались два основных условия: наличие соответствующей элементной базы и концепция хранимой программы. И то, и другое появилось только в 40-х годах XX века.


Первые применения первых компьютеров.


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


Появление коммерческих компьютеров.


Важнейшим событием, повлиявшим на дальнейшее развитие компьютеров, явилось изобретение оперативной памяти на ферритовых сердечниках. Такая память была достаточно компактна и надежна при невысокой стоимости. Довольно долго она использовалась в компьютерах, пока ее не вытеснила более практичная полупроводниковая память.
Эта и ряд других находок позволили существенно снизить себестоимость компьютеров и поставить их производство на серийную основу. Компьютеры начали выходить из стен университетских и военных лабораторий. Соответственно постепенно менялся круг решаемых ими задач.
Примерно в это же время появляются магнитные диски, в которых информация записывалась концентрическими кольцами дорожками. Магнитные головки могли произвольно позиционироваться на любую дорожку специальным приводом, причем за сравнительно небольшое время (десятки миллисекунд). При этом емкость дисков достаточно быстро выросла с единиц до сотен мегабайт.
Параллельно шло развитие операционных систем. От простейших загрузчиков и редакторов связей они выросли до сложных многозадачных многопользовательских систем, от пакетных систем к диалоговым.
Все это создало предпосылки для применения компьютеров в задачах управления и информационных системах, которые не сводились только к вычислениям.
В одном из широко известных в свое время писем, адресованных коллегам с фирмы Burroughs, Как быть, если правда колет глаза? Дейкстра писал: Научно-технические расчеты - простейшее применение вычислительной техники. К сожалению, точная дата написания письма мне неизвестна, но опубликовано оно было в сборнике статей Дейкстры в 1982 г. Так что по крайней мере к этому моменту данная истина уже была осознана.


Организация данных на внешних носителях.


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


Плоские файлы.


Простейшим способом хранения информации, пожалуй, являются плоские файлы. Практически любая из ныне используемых операционных систем поддерживает плоские файлы, за исключением, возможно, некоторых специализированных ОС для встраиваемых контроллеров.
Плоский файл это именованный набор данных на внешнем носителе. Сама ОС никакой структурой плоский файл не наделяет и трактует его просто как набор байт. Задача разделения последовательности байт на записи и выделения полей в них ложится целиком на прикладную программу.
Основные операции доступа к плоским файлам открытие на чтение/запись, закрытие, позиционирование на начало файла/конец файла/заданный байт, чтение/запись заданного количества байт с текущей позиции.
Пожалуй, самая примитивная файловая система, с которой доводилось иметь дело автору, была в ОС RT-11 для миникомпьютеров семейства PDP-11. Носитель в ней имеет одноуровневую структуру, без столь привычных ныне подкаталогов. Файлы представляют собой последовательность секторов, фрагментирование не поддерживается. Это делает необходимым периодическую сборку мусора, т.е. дефрагментацию свободного пространства.
Другие ОС, например, семейства UNIX или MS Windows NT, предоставляют намного более развитые средства для доступа к файлам. Тем не менее, все они имеют общие недостатки:

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

Эти недостатки попытались преодолеть поддержкой индексно-последовательных файлов.


Индексно-последовательные файлы


С данной разновидностью файлов автору доводилось работать в среде ОС VMS для VAX-11. Поддерживаются они и некоторыми другими ОС, например, OS/370, но на практике с ними иметь дело не пришлось.
Если читатель имеет представление о простейших СУБД, работающих с .DBF-подобными файлами, то можно сказать, что И-П файлы отдаленно напоминают .DBF..
При создании И-П файла создается так называемый индекс, который служит для быстрого доступа к записям по значению ключевого поля. Следует обратить внимание на то, что делит файл на записи и поддерживает индекс сама ОС, а не исполняющая система, скомпонованная с прикладной программой
Как следует из самого названия, с И-П файлами можно работать двояко. Во-первых, можно считывать записи последовательно, одну за другой. Во-вторых, можно сразу находить нужную запись по значению ключевого поля, при этом ОС использует индекс для ускорения поиска.
И-П файлы большой шаг вперед по сравнению с плоскими файлами. Тем не менее, и они не лишены недостатков:

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



Системы управления базами данных (СУБД)


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


Иерархические СУБД


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


Сетевые СУБД


Подобно иерархической, сетевую модель также можно представить себе в виде ориентированного графа. Но в этом случае граф может содержать циклы, т.е. вершина может иметь несколько родительских.
Такая структура намного гибче и выразительнее предыдущей и пригодна для моделирования гораздо более широкого класса задач. В этой модели вершины представляют собой сущности, а соединяющие их ребра отношения между ними.
Сетевые СУБД имели гораздо больший успех и долго господствовали на рынке СУБД. В немалой степени их успеху способствовала энергичная деятельность Data Base Task Group (DBTG) Комитета по языкам программирования Conference on Data Systems Languages (CODASYL). Эта организация тщательно проработала спецификации сетевой модели и ее архитектуру, что позволило создать ряд успешных коммерческих продуктов, не последнее место среди которых занимал некогда весьма популярный COBOL.
70-е годы XX века фактически стали эпохой расцвета сетевой модели. Сетевые СУБД весьма прочно укрепились на рынке, и реляционной модели пришлось с боем завоевывать свое место под солнцем. В истории информатики навечно останется Великий Спор, который на самом деле явился решающим сражением сетевой и реляционной моделей. В рядах сторонников сетевой архитектуры был сам великий Чарльз Бахман, и только гений Эдгара Кодда позволил реляционной модели одержать победу. (Интересующиеся деталями этого, безусловно, интереснейшего события могут найти краткий обзор по адресу: http://www.citforum.ru/database/articles/codd_1.shtml , там же имеется ссылка на оригинал статьи).


Реляционные СУБД


Реляционные СУБД являются в настоящий момент самыми распространенными. Их реализации существуют на всех мало-мальски пригодных для этого платформах (от персональных компьютеров до мэйнфреймов), для всех операционных систем и для всех применений от простейших продуктов, предназначенных для ведения картотек индивидуального пользования, до сложнейших распределенных многопользовательских систем.
Несмотря на такое пестрое разнообразие, все эти СУБД имеют в основе общую основу реляционную модель данных, разработанную Коддом в 70-х годах XX столетия. С виду эта модель довольно проста: база данных выглядит как простой набор взаимосвязанных таблиц. Но за внешней простотой кроется мощный и вместе с тем изящный математический аппарат реляционной алгебры, которая в свою очередь базируется на целом ряде математических дисциплин, среди которых логика, исчисление предикатов, теория множеств
Немалую роль в успехе реляционных СУБД играет также язык SQL, разработанный специально для запросов к реляционным БД. Это достаточно простой и в то же время выразительный язык, при помощи которого можно выполнять достаточно изощренные запросы к базе.

Разумеется, предшествующие СУБД также имели языки описания данных (ЯОД) и языки манипулирования данными (ЯМД). SQL объединил в себе обе эти функции. Но самой привлекательной его особенностью, особенно для пользователей-непрофессионалов в программировании, является то, что можно строить запросы на основе непроцедурного подмножества SQL. Это означает, что в формулировке запроса указывается, что должно содержаться в результате, а не как его получить. Имеются, правда, и процедурные элементы языка, например, операторы организации ветвления и циклов, но их применения зачастую удается избежать. При работе же с сетевыми БД программист был вынужден использовать навигационные процедуры, отвлекаясь при этом от решения самой задачи.

Эпилог


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