egorius: (Default)

Не в силах вынести искажения исторической действительности, задал Кайту вопрос:

Tom,
you said that the first Oracle version was written in Fortran.
In “The 1995 SQL Reunion” paper I found the following words of Roger Bamford: Version 2 had been written in assembly language for PDP-11.
I'm sure you have access to information about early days of Oracle. Could you please clarify this point?

Через пару дней пришел ответ:

I went back and checked some notes....
....While much of the system was written in PDP-11 assembler language, parts were developed in the emerging new language C....
so, I’ve updated my slide—it was pdp-11 assember and C and was from there ported to VAX.
thanks for the followup on that detail!

Я считаю, это большой успех отечественной археологии.

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: История SQL. 9. System R, Phase Two.

На протяжении всей серии я вольно обращался с темой «история SQL», то и дело отвлекаясь на соседние, интересные мне темы. Отвлекусь и сейчас, потому что история Оракла занятно переплетается с историей System R.

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

В 1977 году Ларри Эллисон, имевший опыт работы над навигационной базой данных (для ЦРУ, проект назывался ORACL), прочитал статью Кодда и проникся реляционной идеей. Он основал компанию Software Development Laboratories вместе с Эдом Оатсом и Бобом Майнером, а вскоре к ним еще присоединился Брюс Скотт. Прочитав статьи про System R и язык Sequel (вспомним, что в статьях было все, вплоть до БНФ-синтаксиса), коллеги решили, что смогут достаточно быстро сделать свою реализацию реляционной СУБД. Ларри хотел сделать это раньше, чем IBM выпустит свою коммерческую реализацию, но при этом быть совместимым. Вспоминает Дон Чемберлин:

Он узнал о System R и хотел, чтобы его продукт был полностью совместим, вплоть до кодов ошибок. Мы спросили Франка [Кинга]: «Можем ли мы дать коды ошибок этому Эллисону?», но он сказал: «Нет, это конфиденциальная информация».

Тут я нарушу ход истории своим изысканием. Задумывались ли вы когда-нибудь, почему в Оракле исключение no_data_found имеет код +100, в то время, как остальным исключениям присвоен отрицательный номер? Фейерштейн пишет, что это, дескать, ANSI standard error number, но первый стандарт появился только в 1986 году! А теперь посмотрим внимательно на упоминавшийся ранее отчет «Support for Repetitive Transactions and Ad-hoc Query in System R» 1979 года. В нем промелькнул следующий фрагмент кода:

$SELECT DESCRIP,QOH,QOO INTO $DESCRIP,$QOH,$QOO
     FROM PARTS WHERE PARTNO=$PARTNO;
IF SYR_CODE = 0 THEN
     Write DESCRIP, QOH, QOO on terminal;
ELSE IF SYR_CODE = 100 THEN
     Write 'THERE IS NO SUCH PART' on terminal;
ELSE CALL TROUBLE('SELECT');

Полагаю, что дело было так. Ларри, очевидно, читал все материалы по System R и видел этот фрагмент. Пусть ему не удалось получить все коды System R, но +100 ему ничего не могло помешать использовать. А уже потом стандарт «узаконил» получившуюся странность. В одном документе есть фрагмент диалога о трудностях стандартизации между Доном Чемберлином от IBM и Кеном Якобсом от Оракл (оба входили в комитет ANSI):

Чемберлин: — У нас также были проблемы с кодами ошибок.
Якобс: — Стало быть, они были не только у Оракла?

Кстати, вот такое определение кодам ошибок дается в ANSI SQL-1992 (на Аде):

type SQLCODE-TYPE is range bsc .. tsc;
subtype SQL_ERROR is SQLCODE-TYPE range SQL-TYPE'FIRST .. -1;
subtype NOT_FOUND is SQLCODE-TYPE range 100 .. 100;

В тему будет привести слова Роджера Бэмфорда, участнику команды System R, перешедшему затем в Оракл:

Насчет влияния System R на Оракл: некоторые идеи пришли из Esvel, некоторые из System R. Но исходный код выглядел так, словно они прочитали статью, описывавшую язык, сели за компьютер и начали программировать. И было понятно, как писали код: все структуры данных напрямую отображали язык в аппаратуру безо всяких промежуточных слоев. «Так, вот у нас блок запроса, вот у него часть select, а вот то-то и то-то».

Однако возвратимся к повествованию. Спустя два года, в 1979-м, фирма изменила название на Relational Software, Inc и выпустила первый релиз системы. Он получил название Oracle version 2, поскольку Ларри полагал, что первую версию никто не купит. Система была написана на ассемблере DEC PDP-11 и занимала порядка 100 КБ оперативной памяти (из 128).

В 1982 году компания переименовалась в Oracle Systems Corporation, и с тех пор, несмотря на последующие изменения названия, слово Oracle уже не покидало ее имя.

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

Когда я пришел, они были на третьей версии, практически завершенной парнем по имени Брюс Скотт... Он переписал ее и создал действительно красивый, компактный и хорошо структурированный код; многое из этого кода сохранилось и сейчас.

Кстати, Роджер — не единственный из System R, кого Ларри звал в свою команду (Дон Слац не принял предложения, а Франко Путцолу присоединился позже).

Система во времена версии 3 была нестабильной. Снова Роджер:

В то время использовать Оракл можно было единственным образом: каждый день экспортировать все данные, ждать, пока база накроется, и загружать данные обратно. И все были довольны. То есть, конечно заказчики были не в восторге, но не придавали этому большого значения, потому что СУБД не использовалась как транзакционная система.

Примерно тогда же был написан командный интерпретатор, который не долго думая назвали так же, как в System R: UFI — User Friendly Interface. Позже его переименовали в SQL*Plus.

Уйдя из Оракла, Брюс довольно оригинально увековечил память о себе: все знают аккаунт scott/tiger (правда, не все догадываются, что это тот самый Брюс Скотт).

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

Пятую пропустим (заметив в скобках, что в 1987 году в Оракле началась работа над Applications, ныне OEBS), зато остановимся на шестой, увидевшей свет в 1988 году. Ее ведущим архитектором был Роджер Бэмфорд и в этом релизе была переписана часть, отвечавшая за доступ к данным, а это грубо говоря половина всей системы. Был полностью изменен низкоуровневый формат данных и механизм согласованный чтений, появились журнализация, восстановление, блокировки уровня строк:

Строки в версиях 3, 4, 5 были просто конкатенированы в блоках, байт за байтом, безо всяких индексов или указателей. Если вам надо было попасть на строку 12, вы начинали с начала блока и сканировали столбцы, строки... и да, со временем попадали именно туда, куда вам было нужно. А как изменять строку, если значение в столбце увеличивается? Ну, вы брали и сдвигали остаток блока вправо. Поэтому в версии 6 мы все это поменяли. ... С тех пор оно и работает без кардинальных изменений.

До этого Оракл обеспечивал согласованные чтения без механизма мультиверсионности, сохраняя при изменениях образ всего блока (past image). Интересно, что похожая техника используется сейчас для Flashback Database.

Еще версия 6 интересна тем, что в ней впервые появился процедурный язык поверх SQL. PL/SQL основан на синтаксисе языка Ада. Ада была современным языком на пике популярности и к тому же поддерживалась на государственном уровне, так что в целом выбор выглядит логичным, вот только мне не удалось найти никакой достоверной информации о том, как принималось это решение. По-видимому, для PL/SQL был разработан свой собственный компилятор, хотя и в строгом соответствии с имевшимися опубликованными наработками (так же, как было и с SQL). К этому заключению приводят две мысли. Во-первых, многие идеи, заложенные в Аду, в PL/SQL не попали, хотя специально выбрасывать их поддержку было бы странно (особенно это коснулось типизации данных). Во-вторых, от Ады все-таки был унаследован не только синтаксис, но и внутреннее устройство компилятора. Вот что сообщает нам PL/SQL User’s Guide and Reference:

PL/SQL is based on the programming language Ada. As a result, PL/SQL uses a variant of Descriptive Intermediate Attributed Notation for Ada (DIANA), a tree-structured intermediate language. It is defined using a meta-notation called Interface Definition Language (IDL). DIANA is used internally by compilers and other tools.
At compile time, PL/SQL source code is translated into machine-readable m-code. Both the DIANA and m-code for a procedure or package are stored in the database. At run time, they are loaded into the shared memory pool. The DIANA is used to compile dependent procedures; the m-code is simply executed.

То есть, код PL/SQL компилируется в то же внутреннее представление, что и Ада (DIANA), а затем в m-код, исполняемый PL/SQL-машиной. DIANA представляет собой атрибутированное дерево разбора и записывается в виде IDL (в базе это представление можно увидеть в таблицах sys.idl_%$).

Ну что ж, на этом археология уступает место новейшей истории, а мой рассказ заканчиваются.

Почитать и посмотреть:

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: История SQL. 8. System R, Phase One (RDS).

Несмотря на то, что System R была исследовательским проектом, она использовалась и в реальной работе. Этот период эксплуатации системы — Фаза 2 — продолжался с 1978 по примерно 1979 год.

Первая установка системы произошла в Pratt & Whitney Aircraft. Для производства реактивных двигателей компании требовалась система учета деталей и поставок. Затем систему установили в Upjoin Pharmaceuticals для хранения результатов клинических испытаний медикаментов. Несколько позже система стала применяться в Boeing Aircraft. Кроме внешних заказчиков, System R весьма активно использовалась и внутри IBM для самых разных нужд.

По воспоминаниям участников, основная польза таких внедрений была не столько в отзывах пользователей (к завершению проекта накопилось 160 пожеланий, практически ни одно из которых не было реализовано), сколько в демонстрации IBM важности исследований в области реляционных баз данных. Здесь необходимо кое-что пояснить. Деятельность в IBM разделялась на промышленную (приносящую прибыль) и исследовательскую. Исследовательским проектам всегда было тяжело обратить на себя внимание и пробиться в промышленное производство. В то время, о котором мы говорим, флагманским продуктом IBM была иерархическая СУБД IMS, а основные силы разработки были брошены на очередной грандиозный проект, который должен был стать преемником IMS (имена его часто менялись: сначала VSS, потом DS/1, затем Eagle и, наконец, Ampersand). Попытки System R обратить на себя внимание привели лишь к тому, что поддержку реляционных баз данных добавили в спецификацию новой системы.

Помимо трудностей выхода на рынок, исследовательским проектам часто приходилось конкурировать и друг с другом. В этой связи интересно вспомнить эпизод, известный как «перестрелка в O.K. Corral». Одновременно с System R в IBM была другая команда, которая под руководством Мойше Злуфа также занималась реляционными базами. Они разработали визуальный язык запросов Query-by-Example, в котором пользователь показывал пример того, что он хочет получить, а система производила выборку данных по аналогии (те, кто знаком с Oracle Forms, имеют об этом некоторое представление, хотя QBE был существенно богаче). Периодически возникал вопрос, зачем нужны две группы, и в итоге было решено провести сравнение двух систем на производительность. На одной машине установили и System R, и QBE, затем одновременно запустили один и тот же запрос. Через некоторое время System R выдала результат, а QBE упала с ошибкой; это и решило исход перестрелки. А на дверь терминального зала повесили табличку «The O.K. Corral» в честь популярного в то время вестерна. Конечно, состязание было не вполне честным: System R изначально проектировалась для производительной многопользовательской работы, в то время как QBE был силен не этим, а своим графическим интерфейсом. Кроме того, на QBE было легко написать простой запрос, но сформулировать сложный запрос было практически невозможно.

Однако реляционная база данных была востребована заказчиками IBM. Причем многие были не готовы покупать самое передовое (и дорогое) оборудование, и были не готовы ждать появления новой реинкарнации IMS. Их вполне устроила бы «небольшая» реляционная СУБД, работающая на мейнфремах средней ценовой категории. Дальше события развивались так. В подразделении IBM в Эндикотте образовалась свободная группа разработчиков, которая не была знакома с базами данных, но — надо же чем-то заниматься — взялась реализовать СУБД. После некоторых колебаний было решено не начинать с нуля, а взять код System R и довести его до промышленного уровня. Вот, например, что вспоминает Брюс Линдсей: Они переписали RDS на PL/S и переименовали модули в соответствии со своими правилами... Помнится, я работал над кодом авторизации на PL/1 и PL/S. C PL/S приходилось тяжеловато, потому что они использовали мнемонические имена — как минимум три символа на мнемонику — и решили, что подходящими будут 01, 02, 03, 04. Хоть они и не добрались до 10, но... В те времена правила именования в IBM были те еще.

Сделаю небольшое отступление о PL/1. В шестидесятых годах число доступных языков программирования уже подбиралось к сотне, причем обычно они были приспособлены для решения задач в какой-то конкретной области. Многим тогда верилось в то, что можно придумать всеобъемлющий универсальный язык, на котором будет удобно решать любые задачи. И вот в 1964 году — угадайте где? конечно же, в IBM! — был придуман и стал активно продвигаться язык PL/1, сплав Фортрана, Кобола и Алгола. Он включал в себя препроцессор, обработчики исключений (например, перед чтением из файла можно сказать ON ENDFILE GO TO ...), множество умолчаний. Неудивительно, что PL/1 получился не только громоздким, но и сложным для понимания, так что со временем универсальный по задумке язык распался на отдельные предметно-ориентированные подмножества. PL/S как раз одно из них, предназначенное для системного программирования.

В программном отношении, при всех ее богатых возможностях, System R не была большой. Компонент RSS был написан на PL/1 и имел размер порядка 35000 строк; RDS состоял из 38000 строк кода на PL/1 и 9000 строк ассемблера. Замечу, что и команда разработчиков состояла в среднем всего из 15 человек, а о качестве их работы говорит хотя бы то, что за все время в системе была обнаружена только 251 ошибка. System R могла работать на IBM System/370 Model 145 с одним мегабайтом оперативной памяти (одна из средних моделей линейки 370).

Итак, компоненты RSS и RDS были взяты командой в Эндикотте практически без функциональных изменений. Получившийся продукт получил имя SQL/DS и был выпущен IBM в 1981 году. Он работал на операционных системах DOS/VSE и VM/CMS и обеспечивал поддержку базы данных размером примерно до гигабайта.

А что же преемник IMS? Как и практически все грандиозные начинания, его ждала неудача. Слово Джону Науману, одному из менеджеров проекта: Мы работали в Санта-Терезе примерно год и регулярно собирались для обсуждения спецификации. На самом деле мы работали над ней еще в Пало-Альто, так что прошло даже больше года. И собрания обычно проходили в обсуждении висячих строк. Вот была тема для разговоров: «На этой странице осталась висячая строка, надо бы поправить». Тут я и подумал, что так дело не пойдет, что проект обречен.

Стоит заметить, что в 1978 году System R заинтересовался Ларри Эллисон, благо все исследовательские материалы свободно публиковались и были доступны, а в следующем году уже был выпущен Оракл — первая коммерческая реализация реляционной СУБД. Майкл Блазген увидел Оракл на какой-то конференции и Ларри устроил для него небольшую демонстрацию: Оно работало быстро. Он загрузил базу данных, выполнил запрос, затем обновление, все за несколько секунд. Там было строк пятьсот, и база загружалась мгновенно... Больше всего меня поразило, что это работало на маленькой PDP-11 размером с картонную коробку. System R в то время работала на IBM 168. Сейчас-то 486DX2 сравнится с ней по мощности, а тогда это была огромная машина, занимавшая большую комнату... И я подумал: «Просто, быстро, дешево. Люди будут это покупать».

Такой интерес к реляционным технологиям подтолкнул IBM к действиям. Было принято решение выбросить все иерархическое наследие и заняться исключительно реляционной базой данных, но крупного масштаба, в отличие от среднеуровневой SQL/DS. На этот раз код был переписан с нуля, но вдохновение разработчики из Санта-Терезы черпали снова в System R. Если бы мы не имели код System R, я думаю, мы бы не выпустили DB2 Release 1 — вспоминает Жозефина Ченг. Первые заказчики увидели DB2 в 1982 году, а официальный релиз был объявлен в 1983. SQL/DS некоторое время существовал параллельно с DB2, а в 90-х годах был переименован в DB2 для платформ VSE и VM.

Таким образом, только код System R превратился в один продукт и оказал огромное влияние на другой, а уж на сколько СУБД оказали влияние идеи System R, наверное, никто не скажет.

Продолжение следует: 10. Oracle.

Почитать и посмотреть:

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: История SQL. 7. System R, Phase One (RSS).

Теперь поговорим о том, что происходило в Фазе 1 с высокоуровневой компонентой System R — Relational Data System.

SEQUEL продолжал развиваться под руководством Дона Чемберлина. Правда, в какой-то момент (1977 или 78 год) имя пришлось изменить, поскольку оно оказалось уже кем-то зарегистрированным. Недолго думая, из имени выбросили гласные; так и получился SQL. Но и сейчас это имя частенько произносят по-старому — «сиквел», — отдавая дань уважения System R.

Среди прочих изменений обрела свой современный вид фраза GROUP BY HAVING, появился привычный синтаксис табличных алиасов, была введена (нереляционная, но полезная) конструкция ORDER BY.

В язык были введены представления (view). С точки зрения реляционной теории все отношения равноправны вне зависимости от того, хранятся ли данные физически или отношение определяется выражением над другими отношениями. Представления являются попыткой приблизиться к этому идеалу, хотя на практике возникают трудности с изменением данных. Разработчикам это было понятно и в System R представления делились на обновляемые и необновляемые. С другой стороны, представления оказались удобным механизмом разграничения доступа. System R позволяла выдавать пользователям права (grant) на различные объекты, в том числе и на представления. Таким образом, вместо доступа к базовой таблице можно было разрешить пользователю обращаться только к ограничивающему представлению.

В Оракле все перечисленное сохранилось в первозданном виде.

Ограничения целостности в System R были представлены весьма широко, и коммерческие системы далеко не сразу смогли предоставить аналогичные возможности. Во-первых, были реализованы утверждения (assert). Таблицы можно было снабжать произвольными предикатами SQL; нарушение истинности предиката считалось нарушением целостности. Предикаты проверялись в конце каждой транзакции либо по специальной команде ENFORSE INTERGITY.

ASSERT ON UPDATE TO EMP:
  NEW SAL >= OLD SAL

Аналогом Оракла с некоторой натяжкой можно считать ограничение check (обратите внимание на слова old и new).

Во-вторых, имелся более общий и мощный механизм триггеров, перенятый Ораклом (в версии 7 в 1992 году) с небольшими синтаксическими изменениями. Вот пример:

DEFINE TRIGGER EMPINS
  ON INSERTION OF EMP:
    (UPDATE DEPT
     SET    NEMPS = NEMPS + 1
     WHERE  DNO = NEW EMP.DNO)

Интересно посмотреть на программный интерфейс курсоров, предоставляемый RSS, с точки зрения вызывающей стороны. Вот как могла бы выглядеть программа на PL/I, обращающаяся к БД:

CALL BIND('X',ADDR(X));
CALL BIND('Y',ADDR(Y));
CALL SEQUEL(C, 'SELECT NAME:X FROM EMP WHERE JOB=Y');
CALL FETCH(C);
CALL CLOSE(C);

Имелась также команда DESCRIBE, позволяющая получить описание возвращаемых полей. Есть ли сомнения, откуда растут ноги у Oracle Call Interface?

Однако использовать в программе команды RSS не слишком удобно, поэтому несколько позже был сделан препроцессор, заменявший более высокоуровневые команды на соответствующие низкоуровневые вызовы. Команды предварялись знаком доллара — этот символ выбрали, поскольку он не мог встречаться первым в командах PL/I и COBOL:

$LET C BE
  SELECT NAME INTO $X
  FROM EMP
  WHERE JOB = $Y;
$OPEN C;
$FETCH C;
$CLOSE C;

Кстати, в Оракл перекочевал и специальный предикат CURRENT TUPLE OF для ссылки на текущую позицию открытого курсора (только слово tuple подверглось чистке — наверное, как слишком академическое).

Выполнение запросов. Для каждой команды SQL выполнялся разбор (синтаксический и семантический — проверка используемых таблиц). Затем выполнялась оптимизация: выбирался порядок соединения, пути доступа и способы соединения так, чтобы минимизировать стоимость выполнения. Результатом работы оптимизатора являлся план выполнения на специальном «деревянном» языке Access Definition Language. План передавался генератору кода, который транслировал дерево плана в исполняемый (!) код с обращениями к RSS.

Идея компиляции принадлежит Раймонду Лори, который убедил команду, что такой подход позволит ускорить выполнение запросов. Пришлось переписать часть уже готового кода, но ведь одной из задач проекта было показать, что реляционная СУБД может сравниться в скорости с «традиционной». Для генерации использовался сравнительно небольшой (около 100 элементов) набор шаблонов в машинном коде IBM 370.

Общий принцип состоял в том, что подготовительная работа должна выполняться как можно раньше. Например, для конструкции LET CURSOR BE разбор, оптимизация и генерация кода производились еще на этапе компиляции. Сгенерированный модуль доступа сохранялся в базе данных и в дальнейшем использовался для выполнения запроса. При этом RDS автоматически отслеживала зависимости и инвалидировала подготовленный код при изменении структуры таблиц или путей доступа. В этом случае при обращении к запросу оптимизация производилась заново уже во время выполнения программы (прозрачно для приложения). Если же запрос не мог быть обработан заранее (например, во время компиляции могла отсутствовать таблица или сам запрос мог формироваться динамически с помощью команд PREPARE и EXECUTE), то разбор, оптимизация и генерация кода изначально откладывались на время выполнения.

Как видим, общая схема разбора запроса, включая механизм library cache, полностью унаследована Ораклом. Конечно, со временем в ней произошли изменения, но в целом процесс устроен точно так же. Мне даже кажется, что этап «Code Generation» System R проливает свет на происхождение туманного «Row Source Generation» Оракла (интересно, во что сейчас компилируют план?).

Оптимизатор — безусловно, наиболее интересный компонент RDS, поскольку в System R была придумана и реализована стоимостная оптимизация.

В прототипе Фазы 0 стоимость измерялась в обращениях к строкам данных. Но XRM не хранил кортежи как единый фрагмент данных; вместо этого отдельно хранились значения атрибутов и отдельно — объединяющие их ссылки. За счет этого экономилось место (можно было ставить ссылки на один раз записанное значение), но для считывания всего кортежа могло потребоваться много обращений к диску.

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

Оптимизатор имел дело с тремя составляющими пространства перебора:

  • Способ доступа к данным — либо полное сканирование сегмента, либо доступ по индексу.
  • Способ соединения таблиц — либо метод nested loops (так он и назывался), либо merging scans (аналог в Оракле — sort merge join). Хэш-соединение не было реализовано: при упоре на индексный доступ оно не давало особых преимуществ перед сортировкой-слиянием, которое эффективно использовало отсортированность данных, полученных по индексу.
  • Порядок соединения таблиц — уменьшение числа вариантов для перебора достигалось за счет эвристики, исключающей из рассмотрения декартово произведение, пока есть другие варианты.

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

Формулы были основаны на тех же предположениях, что и сейчас в Оракле: на равномерности распределения данных (гистограмм в System R не было) и на некоррелированности предикатов. Сами формулы, конечно, отличаются, отражая разное внутреннее представление данных и упор System R на индексный доступ — пытливый ум может сам сравнить книгу Льюиса и статью Гриффитс. Тем не менее общность подхода налицо.

В System R в стоимости запроса дополнительно были учтены и затраты времени на вычисления. Они измерялись в количестве необходимых низкоуровневых вызовов RSS и пересчитывались в эквивалентное количество чтений страниц данных с помощью настраиваемого коэффициента.

И вновь обращу внимание на то, что современный Оракл пошел по тому же пути. Идеи System R заимствованы вплоть до того, что стоимость запроса в Оракле также выражается в количестве одноблочных чтений и процессорное время пересчитывается в эти единицы. Удивительно только, что в стоимостной оптимизатор в этой системе появился лишь в версии 7 в 1992 году, а учет времени — в версии 9i в 2001 году. А ведь все это работало в System R еще в конце 70-х.

Пришла пора сделать какие-то выводы из проведенного сравнения. Лично меня поражает то, как более 30 лет назад в ходе исследовательского проекта, когда ни у кого еще не было понимания, как надо строить реляционные СУБД, были нащупаны пути и решения, которые продолжают отлично работать в современных системах. Все, чем богат Оракл, так или иначе опирается на идеи System R. Единственное радикальное изменение заключается в механизме мультиверсионности; все остальное не заменило решения System R, а эволюционно улучшило их.

Продолжение следует: 9. System R, Phase Two.

Почитать и посмотреть )

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: История SQL. 6. System R, Phase Zero.

На следующей фазе проекта, названной Фазой 1 (условно с 1976 по 1977 год), код протопита был выброшен в соответствии с заветами Брукса и полнофункциональную систему переделали с нуля, уже лучше понимая, что нужно:

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

Интересно посмотреть на возможности, реализованные в System R и проследить их судьбу в современной базе данных — в моем случае, в Оракле. Сначала посмотрим на низкоуровневый компонент доступа к данным RSS — Research Storage System.

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

На этапе Фазы 0 в XRM отдельно хранились значения атрибутов и отдельно — объединяющие их ссылки. За счет этого экономилось место (можно ставить много ссылок на единожды записанное значение), но для считывания всей строки могло потребоваться много обращений к диску. Приоритеты оптимизации пересмотрели: стало понятно, что вместо подсчета строк надо считать ввод-вывод. Поэтому в новом механизме RSS большое внимание было уделено кластеризации. Строки стали хранить целиком, чтобы считывать их полностью за одно обращение к диску. Более того, один сегмент мог быть выделен сразу под несколько таблиц — это позволило еще больше увеличить кластеризацию, если таблицы часто использовались совместно.

Были предусмотрены и другие типы сегментов, например, сегмент журнала, временные сегменты.

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

Чтение данных по любому пути доступа осуществлялось с помощью команды RSS open_scan и последовательного вызова next для получения данных строка за строкой. Дополнительно могло указываться выражение (называемое search argument или SARG), которому должны были удовлетворять прочитанные данные. У разработчиков System R даже родилось прилагательное, приводившее непосвященных в замешательство: sargable predicate, то есть предикат SEQUEL, который может напрямую использоваться RSS. В Оракле sargable predicates называются предикатами доступа (access), а те условия, которые в System R проверялись уже на уровне RDS, называются предикатами фильтрации (filter). Но аналогия эта не вполне корректная, поскольку исторически в Оракле не было четко разделенных компонент, аналогичных RSS и RDS.

Точечные обращения к данным организованы в System R на основе уникальных идентификаторов строк TID (tuple id; в Оракле это rowid), составленных из указания сегмента, страницы и смещения внутри страницы. С помощью TID над строками таблиц строились вспомогательные структуры данных (например, индексы). Отсюда следует, что TID должен быть неизменным, а это приводит к проблеме миграции строк: если при изменении данных строка перестает помещаться в своей странице, то ее приходится переносить в другую и для сохранения TID устраивать косвенную адресацию. Ровно то же видим и в Оракле.

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

Во-вторых, RSS предоставлял ссылки (links), связывающие строки, принадлежащие одной или разным таблицам. С помощью ссылок можно было связать «родительскую» строку с «дочерними» строками другой таблицы. При этом актуальность и упорядоченность ссылок нужно было поддерживать явно с помощью операций connect и disconnect. Сканирование данных по ссылкам позволяло перебирать дочерние строки или переходить от дочерней строки к ее родителю.

Пытливый ум немедленно узнает в ссылках наследие навигационных СУБД в духе CODASYL. Что они делают в реляционной базе данных? Дело в том, что у авторов RSS была идея построить универсальный механизм, на котором можно было бы реализовать любую СУБД, хоть реляционную, хоть сетевую. По воспоминаниям Франко Путцолу, он потратил массу времени, отображая все конструкции СУБД IMS в команды RSS. Идея, по-видимому, была обусловлена тем, что в то время активно развивался гигантский — в духе IBM — проект FS (Future System), частью которого была поддержка всевозможных типов баз данных. FS со временем рухнул под тяжестью собственной сложности; этот проект считается самым дорогим провалом в истории IBM. А ссылки в итоге убрали и из System R.

Транзакции в System R были реализованы в полной мере даже по сегодняшним меркам. RSS начинал транзакцию по команде start_transaction и либо фиксировал изменения по end_transaction, либо откатывал их по restore_transaction. Откатывались как изменения в данных и установленные блокировки, так и (в отличие от Оракла) операции создания новых таблиц или индексов. Интересно, что в статьях того времени термин commit употребляется редко, а вместо rollback используется backout или просто undo.

Откат мог происходить не только к началу транзакции, но и к установленной с помощью save_transaction точке сохранения. Внутренне точки сохранения использовались, чтобы обеспечить атомарность команд SQL, отображаемых на множество команд RSS. Но в SEQUEL точек сохранения не было, поэтому извне эта возможность была недоступна.

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

Журнал был организован как циклический буфер (на диске). Старые данные, не относящиеся к активным транзакциям, переносились в архивные журналы (на ленту) — в этом плане журнал Оракла организован точно также. Замечу, что именно в System R впервые применили журнализацию на жесткий диск. До этого журналы писали сразу на магнитную ленту; конечно, при этом журнал невозможно использовать для отката транзакций.

Многопользовательский режим и поддержка согласованности данных в System R обеспечивались блокировками, что само по себе вполне очевидно. Интересный вопрос состоял в том, на каком уровне их устанавливать. В проекте был период, когда казалось, что лучший вариант — это идея Раймонда Лори о блокировке предикатов. Например, если транзакция изменяет данные, то имеется предикат, описывающий диапазон изменений, который и логично было бы заблокировать. Сложности с этим подходом возникают, когда надо определить, конфликтуют ли блокировки, то есть пересекаются ли диапазоны, определенные двумя предикатами. В общем случае это вообще алгоритмически неразрешимая задача; в итоге разработчики не решились даже на реализацию для предикатов простого вида. Вместо этого было решено блокировать такие объекты, как строки, таблицы, страницы, сегменты.

Все необходимые блокировки RSS ставил сам. Это было сознательное решение, позволившее существенно упростить RDS, на долю которого оставалась возможность при желании явно выставить блокировку, если это зачем-то было нужно. RSS имел также механизм обнаружения взаимных блокировок: одна из транзакций откатывалась, чтобы другая могла продолжить работу.

При блокировках неизбежно приходится искать компромисс между изолированностью транзакций друг от друга и масштабируемостью системы. Поддерживались три уровня изоляции:

  1. Транзакция видит незафиксированные изменения других транзакции. В этом режиме блокируются только изменяемые данные, а при чтении блокировки не нужны. В Оракле такого режима нет в принципе.
  2. Транзакция видит только зафиксированные изменения, но последовательные чтения могут вернуть разные данные. Здесь при чтении ставится блокировка на время выполнения запроса. В Оракле аналогом является стандартный режим read committed, но за счет механизма мультиверсионности он обходится без блокировок (если верить Кайту, он появился в 1983 году в третьей версии).
  3. Транзакция видит только зафиксированные изменения и в пределах транзакции чтения дают одинаковый результат. Для этого при чтении ставится блокировка на время всей транзакции. В Оракле аналогом является режим serialized.
По опыту разработчиков, в реальной работе в основном использовался третий уровень.

В System R так и не была решена проблема фантомных записей. Даже на третьем уровне изоляции транзакция могла увидеть новые данные, вставленные в таблицу другой транзакцией, ведь несуществующие строки невозможно заблокировать (замечу, что в случае предикатных блокировок такой проблемы просто не возникает).

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

Таким образом, при «мягком» сбое (отказ оперативной памяти) достаточно откатиться к последней контрольной точке (приравнять текущий список теневому и освободить ненужные страницы) и позаботиться о согласованности данных с помощью журнала (повторить завершенные с момента контрольной точки транзакции и откатить незавершенные). Журнал записывался как минимум в конце транзакции и обязательно перед записью самих данных (для надежности обычно на два диска). Собственно, признаком зафиксированной транзакции считается запись об этом в журнале. Аналогичный write ahead log использует и Оракл. При «жестких» сбоях (отказ диска) информация и журнал восстановливаются из бэкапа (инкрементального, с магнитной ленты), после чего выполняется обычная процедура «мягкого» восстановления.

Пытливый ум может заметить, что Оракл, используя ту же технику восстановления, основанную на журнале, обходится без механизма теневых страниц. К этому же выводу пришли в конце концов и авторы System R. Теневые страницы появились в качестве «исторического наследия» XRM. Они, безусловно, ускоряют процедуру восстановления, но дорогой ценой: необходимо поддерживать два длинных списка страниц для каждого сегмента, а это и дополнительный ввод-вывод, и время процессора. В итоге при больших объемах данных недостатки начинают перевешивать достоинства. Но когда это стало понятно, менять механизм было уже слишком поздно.

Любопытно взглянуть на абсолютные цифры, относящиеся к восстановлению. Типичными для инсталляций System R на 1981 год являются такие показатели:

  • общая производительность — транзакция в секунду;
  • откат транзакции — несколько раз в минуту (занимает миллисекунды);
  • мягкий сбой — несколько раз в месяц (восстановление занимает около минуты);
  • жесткий сбой — раз-два в год (около часа).

Продолжение: 8. System R, Phase One (RDS).

Почитать и посмотреть )

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: 5. Что же выбрать?.

Идеи Кодда далеко не сразу получили признание, и на то было как минимум две причины. Во-первых, запись в терминах реляционной алгебры или исчисления была привычна академическим кругам, но совершенно непонятна заказчикам. Требовался более простой, ориентированный на неподготовленного пользователя язык. Во-вторых, разработчики ПО сильно сомневались в возможности эффективной реализации реляционной СУБД. Как отмечал Дон Чемберлин, ситуация напоминала период первых языков высокого уровня. Когда Джон Бэкус придумал Фортран и заявил, что программист не должен тратить свое время на возню с регистрами процессора, а вместо этого может просто написать формулу, эта идея была воспринята в штыки профессионалами, привыкшими оптимизировать свой код на низком уровне. Чтобы преодолеть сопротивление, Бэкусу пришлось написать эффективный компилятор. (Кстати, необычный оператор IF (выражение) L1, L2, L3 — переход на метки в случае, когда выражение меньше, равно или больше нуля — появился в Фортране именно потому, что позволял эффективнее задействовать возможности аппаратуры.)

С аналогичной целью в 1973 году в исследовательском центре IBM в Сан-Хосе был начат проект System R. Его задачей было построение прототипа реляционной СУБД, на практике демонстрирующего осуществимость идей Кодда. Требовалось придумать язык, на котором пользователи — без математического образования и без опыта программирования — смогли бы формулировать запросы, и реализовать оптимизирующий компилятор этих запросов в низкоуровневые операции с данными.

Конечно, проект возник не на пустом месте. В начале 1970-х в IBM происходило много активностей, связанных с базами данных даже помимо флагманского продукта — иерерхической СУБД IMS. В частности, в Йорктауне в 1972 году работала исследовательская группа, изучавшая возможные пути развития систем управления базами данных. В нее входил и Дон Чемберлин, который в то время изучал стандарт CODASYL.

В 1973 году Тед Кодд организовал в Йорктауне симпозиум с целью понять, что происходит в компании в области его интереса — реляционных баз данных. Там он провел семинар, на котором рассказал про реляционную модель и свой язык запросов. «Это было откровение: Кодд называл довольно сложные запросы и, поскольку я занимался CODASYL, я мог себе представить, как это будет выглядеть — программы на пять страниц, пробирающиеся через лабиринт указателей. Кодд же записывал эти запросы в одну строчку» — вспоминал Чемберлин.

Под влиянием идей Кодда Дон Чемберлин вместе с недавно принятым на работу Реем Бойсом стали размышлять о нотации для записи реляционных выражений: они придумывали запросы и пытались нащупать для них простой нематематический синтаксис. Так родился язык SQUARE (Specifying Queries as Relational Expressions), на котором запрос формулировался как отображения множеств значений в другие множества.

Например, запрос «найти поставщиков, поставляющих деталь 15» выглядит на SQUARE так:

       VENDORS    (15)
vendor#       part#

Значением этого отображения является множество значений столбца vendor# из тех строк таблицы vendors, для которых столбец part# соотвествует аргументу 15.

Отображения могут комбинироваться так, что результат одного отображения является аргументом другого. Например, запрос «Найти номера деталей, имеющихся у поставщика по имени IBM» запишется так:

     SUPPLIES        °        VENDORS           ('IBM')
part#        vendor#   vendor#       vendor_name

Это можно прочитать следующим образом: взять part# из supplies, где vendor# соответствует некому условию, которое определяется множеством vendor# из vendors, для которых vendor_name соотвествует IBM.

Спустя несколько месяцев Йорктаунская команда переехала в Сан-Хосе и объединилась там с командой Кодда для работы над прототипом. Впрочем, сам Кодд занялся другими делами и не принимал большого участия в работе проекта, выступая в роли гуру: с ним советовались по ключевым вопросам, но в детали он не вникал.

В результате обсуждений команда разделилась на две группы. Группа верхнего уровня (несколько позже названная RDS — Relational Data System) занялась разработкой языка запросов, группа нижнего уровня — системой управления данными (RSS — Research Storage System).

На первое время, чтобы было над чем строить язык запросов, группа RSS решила использовать не вполне подходящее, зато уже имеющееся решение XRM (Extended n-ary Relational Memory), разработанное в Кембриджском научном центре IBM одним из членов команды Раймондом Лори. XRM предоставлял низкоуровневый однопользовательский доступ к данным, расширяя возможности системы RM (она поддерживала только бинарные отношения). А группа в это время собиралась заняться разработкой полнофункционального механизма с поддержкой многопользовательского доступа, авторизации, транзакций, блокировок, журнализации и т. п.

Группа RDS тоже имела наработки в виде SQUARE и планировала развивать их дальше. Для начала язык видоизменили, чтобы программы можно было вводить с клавиатуры и «разбавили» его английскими ключевыми словами. Так появился SEQUEL — Structured English Query Language. На самом деле, если посмотреть первую статью о SEQUEL, она вся написана в терминах SQUARE, так что SEQUEL можно считать в прямом смысле сиквелом SQUARE.

Основной идеей, занимавшей в то время группу RDS, было дать доступ к данным непосредственно конечным пользователям, поэтому очень большое внимание уделялось простоте языка. В группе даже имелась лингвист Филлипс Райзнер, которая исследовала этот вопрос, организовав в местном университете обучение группы студентов. Как мы теперь понимаем, эта цель оказалась недостижимой: бухгалтеры и сейчас не обращаются к базам данных напрямую.

Постепенно Дон Чемберлин и Рэй Бойс расширяли SEQUEL новыми полезными возможностями. Например, в SQUARE было трудно связать строку выборки с данными других строк; для этого приходилось вводить переменные. Запрос «вывести всех поставщиков, поставляющих более 10 деталей» формулировался так:

X        ∈ SUPPLIES : COUNT (     SUPPLIES       (X       ) ) > 10
 vendor#                     part#        vendor#  vendor#

Здесь переменная x принимает значения строк таблицы supplies. Выбираются строки x, отвечающие условию: число деталей из supplies, где vendor# соответствует vendor# строки x, больше 10.

Поскольку подобные конструкции встречались достаточно часто, в SEQUEL добавили group by:

SELECT vendor#
FROM   supplies GROUP BY vendor#
WHERE  COUNT (part#) > 10

(Именно так; having появился позже.)

К сожалению, Рэймонд Бойс недолго проработал над базами данных и System R: в июне 1974 года его не стало. Но и за отпущенное время он успел многое: его имя носит нормальная форма Бойса-Кодда, мы ценим его вклад в SEQUEL.

Еще одной любопытной, ныне постоянно употребляемой конструкцией является select *. Брюс Линдсей (работал в группе RSS, ныне IBM Fellow) полагает ее одной из наибольших ошибок в SEQUEL. Во-первых, столбцы приходится упорядочивать, а это еще одно отступление от реляционной теории, которая имеет дело со множеством атрибутов, порядок в котором не определен. Во-вторых, непонятно, как должно вести себя представление, созданное на основе такого запроса: должны ли в нем появляться столбцы, если они добавлены в таблицу?

Кстати, Брюс Линдсей и Джим Грей (также работал в группе RSS, лауреат премии Тьюринга 1998 года) славны, помимо прочего, изобретением термина «гейзенбаг».

Интерпретатор SEQUEL был написан на PL/I. Он транслировал запросы в низкоуровневые вызовы XRM, оптимизируя число чтений строк за счет выбора доступа к таблице (полный перебор или использование индекса). Для взаимодействия с пользователем была написана утилита UFI (User Friendly Interface), позволявшая вводить запросы и просматривать результаты.

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

Этот этап проекта длился примерно с 1973 по 1974 год и получил название Фазы Ноль. Фактически, за это время был создан простой однопользовательский прототип СУБД с поддержкой подмножества SEQUEL, на котором обкатывали возникающие идеи.

Истории была бы неполной без упоминания о «великом споре» между апологетами навигационной и реляционной моделей — Чарльзом Бахманом и Тэдом Коддом. Дебаты между ними состоялись на конференции ACM в Мичиганском университете в 1974 году и результатом их, как утверждает Чемберлин, стал перелом в отношении профессионалов к реляционным СУБД («Победили хорошие парни» — Крис Дейт). Оставались вопросы с производительностью, но потенциальные преимущества реляционного подхода стали всем очевидны.

От себя замечу, что полагаю этот факт спорным. Недавно, листая найденные на дальней полке книги по базам данных, я был удивлен. В американской книге 1980 года Шаку Атре из 300 страниц уделяет реляционной модели где-то 25, остальное посвящено навигационным СУБД. В книге японцев Нагао, Катаяма и Уэмура 1983 года соотношение примерно равное. А в отечественной книге Замулина 1990 года то и другое вообще упоминается вскользь. Так что не всем и не сразу.

Продолжение: 7. System R, Phase One (RSS).

Почитать и посмотреть )

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: 4. Реляционное исчисление.

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

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

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

Более того, Кодд даже придумал на основе исчисления свой реляционный язык Alpha, оказавший сильное влияние на QUEL (query language) — язык одной из первых реляционных СУБД Ingres, разработанной в Беркли. QUEL строго следовал реляционной модели; рискну предположить, что это внесло свой вклад в то, что в итоге победил SQL. SQL изначально был основан на алгебре, но с самого начала отступил от стройной теории (вспомним про мультимножества и трехзначную логику), за что до сих пор порицаем ортодоксами. Тем не менее он оказался более практичным (наверное, и более везучим), чем его академический собрат.

Это, конечно, не означает, что алгебра таки «лучше» исчисления. SQL и сам изрядно обогатился ее арсеналом, а кроме того, существуют и другие языки, построенные на фундаменте матлогики и реляционного исчисления. Самым известным из них является Пролог. Он появился во Франции в начале 1970-х — как раз в то время, о котором мы ведем речь, — но совершенно вне контекста баз данных, а именно в связи с исследованиями по обработке естественных языков.

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

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

  • Номер поставщика, поставляющего хоть что-нибудь:

    supply_something(X) :-                select distinct vendor#
       supply(X,_).                       from   S
    

    supply_something(X) верно, если поставщик X поставляет деталь с неважно каким именем.

  • Имя поставщика, не поставляющего ни одной детали:

    supply_nothing(VN) :-                 select vendor_name
      vendor(V,VN), \+(supply(V,_)).      from   V
                                          where  not exists
                                                (select vendor#
                                                 from   S
                                                 where  S.vendor# = V.vendor#)
    

    supply_nothing(VN) верно, если существует поставщик V с именем VN, и не верно, что поставщик V поставляет произвольную деталь.

  • Номер поставщика, поставляющего деталь 15:

    supply_15(X) :-                       select vendor#
      supply(X,15).                       from   S
                                          where  S.part# = 15
    

    supply_15(X) верно, если поставщик X поставляет деталь 15.

  • Номер поставщика, поставляющего все детали:

    missing(V,P) :-                       select vendor# 
      vendor(V,_), part(P),               from   V 
      \+(supply(V,P)).                    where  not exists
    supply_all(V) :-                            (select part#
      vendor(V,_), \+(missing(V,P)).             from   P
                                                 where  not exists
                                                       (select part#
                                                        from   S
                                                        where  S.part# = P.part# and S.vendor# = V.vendor#) )
    

    Разобьем на две части. missing(V,P) верно, если существует поставщик V с любым именем, существует деталь P, и не верно, что V поставляет P. Говоря неформально, missing(V,P) означает «поставщик V не поставляет P».

    supply_all(V) верно, если существует поставщик V с любым именем, и не верно, что для любой детали P «поставщик V не поставляет P».

Как видим, Пролог справляется с примерами из мира СУБД. Поглядим еще на классическую рекурсивную задачу из мира Пролога. Пусть имеются факты о том, кто кому приходится родителем. Нужно определить, кто кому приходится предком (родителем, прародителем и т. п.).

Сначала определим несколько фактов о непосредственных родителях:

parent('Abraham','Isaac').
parent('Isaac','Jacob').
parent('Jacob','Judas').

Теперь можно определить понятие предка:

ancestor(B,A) :- parent(B,A).
ancestor(Z,A) :- parent(B,A), ancestor(Z,B).

Это либо непосредственный родитель (первое правило), либо существует какой-то непосредственный родитель, в свою очередь являющийся предком (второе правило).

Теперь Прологу можно задать вопрос: покажи все возможные пары людей и их предков.

| ?- ancestor(X,Y).

X = 'Abraham'
Y = 'Isaac' ? ;

X = 'Isaac'
Y = 'Jacob' ? ;

X = 'Jacob'
Y = 'Judas' ? ;

X = 'Abraham'
Y = 'Jacob' ? ;

X = 'Isaac'
Y = 'Judas' ? ;

X = 'Abraham'
Y = 'Judas' ? ;

no

Пролог перечислит по очереди все найденные пары и остановится с сообщением no (больше нет).

Оказывается, и такую задачу можно практически один в один перевести на SQL, использую иерархический запрос:

with people(parent_name,name) as (         -- факты о родителях
        select 'Abraham', 'Isaac' from dual
        union
        select 'Isaac',   'Jacob' from dual
        union
        select 'Jacob',   'Judas' from dual
     ),
     ancestor(ancestor_name,name) as (     -- предок - это...
        select p.parent_name,              -- ...непосредственный родитель...
               p.name
        from   people p
        union all
        select a.ancestor_name,            -- ...или предок родителя
               p.name
        from   people p,
               ancestor a
        where  p.parent_name = a.name
     )
select *
from   ancestor;
 
ANCESTOR NAME
-------- -----
Abraham  Isaac
Isaac    Jacob
Jacob    Judas
Abraham  Jacob
Isaac    Judas
Abraham  Judas
 
6 rows selected

В Оракле такой синтаксис работает, начиная с версии 11.2.

Безусловно, между Прологом и SQL масса различий: и в синтаксисе, и в сфере применения. Но общий математический фундамент тем не менее налицо.

Продолжение следует: 6. System R, Phase Zero

Почитать и посмотреть )

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: 3. Реляционная алгебра.

Если реляционная алгебра более или менее привычна (что не удивительно, поскольку SQL в основном базируется именно на ней), то с исчислением дело обстоит хуже. Реляционное исчисление основано не на теории множеств, а на другом формализме — логике предикатов первого порядка. Впервые Кодд подробно описал его в работе 1972 года, хотя и упоминал с самой первой статьи.

Логика предикатов корнями уходит в труды Аристотеля (а это IV век до н. э), который пытался свести рассуждения об истинности любого предположения к формальным правилам вывода новых фактов из имеющихся (силлогизмы Аристотеля).

В нынешнем понимании, логика предикатов имеет дело со следующими объектами. Во-первых, с константами и переменными. Во-вторых, с предикатами, под которыми понимаются булевские (т. е. принимающие истинное или ложное значение) функции, аргументами которых могут выступать константы и переменные. В-третьих, предикаты объединяются в выражения с помощью логических связок: и (∧), или (∨), не (¬).

Предикаты связаны с отношениями вот как. Возьмем какое-нибудь отношение, допустим, V. Неформальный смысл этого отношения можно определить так: «vendor# — поставщик с именем vendor_name». Но чтобы точно задать отношение, мы должны явно перечислить всех поставщиков и их имена. Можно считать, что отношение содержит множество истинных утверждений-кортежей: если (x, y) входит в отношение, то x — поставщик с именем y. Что, если (x, y) не входит в отношение? Тогда мы принимаем предположение о замкнутости мира и считаем, что такого поставщика нет в природе. Предикат, соответствующий отношению, показывает истинность утверждения («является ли vendor# поставщиком с именем vendor_name?»): он принимает истинное значение тогда и только тогда, когда его единственный параметр-кортеж входит в соответствующее отношение.

Предикаты-отношения я для удобства буду обозначать той же буквой, что и само отношение. Например, V(x) означает, что переменная x принимает значение из множества кортежей отношения V.

Кроме предикатов-отношений Кодд включил в реляционное исчисление и обычные бинарные предикаты сравнения (равно, больше и т. п.) для использования с атрибутами кортежей. К атрибутам можно обратиться, используя индекс: x[1] обозначает первый атрибут V.

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

  • существования — ∃x (P) означает «найдется такой x, что верно P»,
  • всеобщности — ∀x (P) означает «для любого x верно P».

Теперь можно сказать о том, почему эта логика называется логикой первого порядка. Это значит, что аргументами предикатов могут быть только переменные (кортежи), но не сами предикаты (отношения). Например, в рамках логики первого порядка нельзя сказать: «для любого отношения S верно ...». Тем не менее, как показывает практика, ее выразительной мощности вполне достаточно (интересно, что в самой первой статье Кодд предполагал необходимость использования логики второго порядка).

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

Напомню схему нашей тестовой БД и рассмотрим на ней те же самые примеры, что и для реляционной алгебры (для удобства сравнения я также приведу рядом и выражения алгебры).

  • Номер поставщика, поставляющего хоть что-нибудь:

    s[1]: S(s)                            select distinct vendor#
                                          from   S
    
    S[1]                                  select distinct vendor#
                                          from   S
    
  • Имя поставщика, не поставляющего ни одной детали:

    v[2]: V(v) ∧ ¬∃s( S(s) ∧ s[1]=v[1] )  select vendor_name
                                          from   V
                                          where  not exists
                                                (select vendor#
                                                 from   S
                                                 where  S.vendor# = V.vendor#)
    
    (V[1=1](V[1]-S[1]))[2]                select vendor_name
                                          from   V,
                                                (select vendor# from V
                                                 minus
                                                 select vendor# from S) V2
                                          where  V.vendor# = V2.vendor#
    
  • Номер поставщика, поставляющего деталь 15:

    s[1]: S(s) ∧ s[2]=15                  select vendor#
                                          from   S
                                          where  S.part# = 15
    

    За счет использования обычных логических условий запрос получается тривиальным по сравнению с алгеброй.

    (S[2=1]{15})[1]                       select vendor#
                                          from   S,
                                                (select 15 part# from dual) P
                                          where  S.part# = P.part#
    
  • Номер поставщика, поставляющего все детали:

    v[1]: V(v) ∧ ∀p( P(p) ∧ ∃s( S(s) ∧    select vendor# 
      ∧ s[2]=p[1] ∧ s[1]=v[1] ) )         from   V 
                                          where  not exists
                                                (select part#
                                                 from   P
                                                 where  not exists
                                                       (select part#
                                                        from   S
                                                        where  S.part# = P.part# and S.vendor# = V.vendor#) )
    
    

    В SQL нет аналога квантора всеобщности, но при принятом предположении о замкнутости мира верно ∀x (P) = ¬∃x (¬P).

    S[1]-((S[1]⊗P[1])-S)[1]               select vendor# 
                                          from   S 
                                          minus
                                          select vendor#
                                          from  (select S.vendor#, P.part# from S, P
                                                 minus
                                                 select S.vendor#, S.part# from S)
    

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

Продолжение следует: 5. Что же выбрать?

Почитать и посмотреть )

egorius: (Default)

Начало: 1. Необходимая предыстория, назад: 2. Программист-навигатор.

Итак, к концу 1960-х рынок СУБД (а рынок как таковой только начал формироваться: до этого продавали аппаратуру, а не программы) был представлен сетевой системой IDS Бахмана (General Electric), иерархической IMS (IBM) и некоторыми другими, менее известными. Несмотря на то, что сейчас мы говорим «сетевая модель» и «иерархическая модель», эти продукты разрабатывались без какой-либо четкой математической концепции; во главу угла была поставлена эффективность кода.

Примерно в этот момент (1968 год) базами данных заинтересовался Эдгар Кодд, работавший в IBM. Его идея была в том, что привлечь новых заказчиков можно только простым и понятным способом извлечения информации из баз данных, а такой способ должен опираться на стройную модель. Будучи математиком, он заметил связь между хранимыми в БД данными и логическими высказываниями. Через год работы появился внутренний отчет IBM, а в начале 1970 — знаменитая статья в Communications of ACM.

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

Центральным понятием реляционной теории является отношение (relation) — то, что обычно мы называем таблицей (иногда ошибочно полагают, что под отношением имеется в виду связь между двумя таблицами, путая, возможно, с entity-relationship diagram). Отношение является множеством кортежей (tuple), состоящих из атрибутов (attribute). Для каждого атрибута определен тип данных; количество атрибутов определяет степень (или арность) отношения. В обычной терминологии кортеж отношения — это строка таблицы, а атрибут — столбец.

Однако несмотря на внешнее сходство отношений и таблиц, надо понимать, что отношения, будучи множествами, обладают важными свойствами, не всегда верными для таблиц SQL:

  • В отношении нет повторяющихся кортежей (а в SQL мы, как правило, работаем с мультимножествами и при необходимости должны устранять дубликаты явно, например, с помощью DISTINCT). Как следствие, в отношении всегда существует первичный ключ (в SQL это необязательно).
  • Кортежи не упорядочены (следовательно, конструкция ORDER BY немедленно выводит нас за рамки реляционной теории).

Конечно, проводя параллели с SQL, я буду невольно забегать вперед, потому что во время, о котором мы говорим, никакого SQL еще не было.

Кодд предложил два способа работы с отношениями. Первый — реляционная алгебра — использует тот факт, что отношения являются множествами (хоть и специального вида), а, значит, к ним применимы такие традиционные теоретико-множественные операции, как объединение (∪), пересечение (∩) и разность (−). Единственная тонкость в том, что для этих операций отношения должны иметь одинаковый набор атрибутов — иначе результат будет множеством, но перестанет быть отношением.

На SQL эти операции обозначаются UNION (но не UNION ALL!), INTERSECT и MINUS.

Кроме того, Кодд ввел несколько дополнительных операций над отношениями. Тут я буду придерживаться нотации, которую Кодд использует в статье 1972 года. Также вслед за ним я буду обозначать атрибуты номерами, хотя Кодд и сам говорил, что в реальных системах имена будут удобнее. С тех пор теория сильно шагнула вперед, и в работах Дейта нотация уже совсем иная.

Проекция оставляет из всего набора атрибутов некоторое их подмножество. Например, проекция отношения A на 2 и 5 атрибуты обозначается A[2,5].

В SQL эта операция обеспечиваются фразой SELECT DISTINCT (т. к. в отношении, в том числе результирующем, не может быть дубликатов).

Соединение двух отношений по условию равенства общих атрибутов порождает новое отношение, кортежи которого являются конкатенациями всевозможных пар кортежей исходных отношений, для которых выполняется это условие. Например, если у отношений A и B общими считаются атрибуты A[1] и B[3], то соединение обозначается A[1=3]B.

Такое соединение называют еще эквисоединением. Частный его случай, когда два отношения не имеют общих атрибутов, называется расширенным декартовым произведением: A⊗B.

В SQL соединения формулируются во фразе FROM. Особенно отчетливо это видно в ANSI-синтаксисе, где условия соединения выписываются явно, а в традиционном синтаксисе условия переходят во фразу WHERE.

Ограничение оставляет лишь те кортежи, которые удовлетворяют определенному условию на атрибуты. Например, ограничение отношения A по условию, что атрибут 1 больше, чем атрибут 2: A[1 > 2].

Ограничения в SQL записываются во фразе WHERE.

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

Рассмотрим несколько запросов на следующем, почти классическом, примере: имеются поставщики (V — VENDORS) и детали (P — PARTS), связаные многие-ко-многим поставками (S — SUPPLIES).

Рядом с выражением реляционной алгебры для пущей ясности приводится непосредственный аналог на SQL.

  • Номер поставщика, поставляющего хоть что-нибудь:

    S[1]                            select distinct vendor#
                                    from   S
    
  • Имя поставщика, не поставляющего ни одной детали:

    (V[1=1](V[1]-S[1]))[2]          select vendor_name
                                    from   V,
                                          (select vendor# from V
                                           minus
                                           select vendor# from S) V2
                                    where  V.vendor# = V2.vendor#
    

    Для того, чтобы получить имя поставщика, пришлось выполнить дополнительное соединение.

  • Номер поставщика, поставляющего деталь 15:

    (S[2=1]{15})[1]                 select vendor#
                                    from   S,
                                          (select 15 part# from dual) P
                                    where  S.part# = P.part#
    

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

  • Номер поставщика, поставляющего все детали:

    S[1]-((S[1]⊗P[1])-S)[1]         select vendor# 
                                    from   S 
                                    minus
                                    select vendor#
                                    from  (select S.vendor#, P.part# from S, P
                                           minus
                                           select S.vendor#, S.part# from S)
    

    Такую операцию Кодд даже рассмотрел отдельно, введя для нее имя реляционного деления.

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

Продолжение следует: 4. Реляционное исчисление.

Почитать и посмотреть )

egorius: (Default)

Начало: 1. Необходимая предыстория.

Сетевые базы данных интересно рассмотреть подробнее, потому что обычно они опускаются как пережиток былого. Вместе с иерархическими базами данных (например, Information Management System, разработанная IBM) cетевые БД принадлежат к классу навигационных баз данных.

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

Рассмотрим простую вариацию на тему bill of materials (ведомость материалов; кстати, довольно типичный пример использования ранних СУБД). Есть ассортимент деталей, каждая из которых принадлежит определенному классу. При этом некоторые детали могут собираться из других деталей. Традиционная ныне ER-диаграмма выглядит следующим образом:

А вот как аналогичная БД выглядит на диаграмме Бахмана:

Прямоугольниками обозначены таблицы, содержащие данные. Стрелки — это наборы (sets), представляющие отношение один-ко-многим: стрелка направлена от родительской записи к дочерним (сейчас на ER-диаграммах стрелку если и рисуют, то в другую сторону).

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

Например, найдем первую запись о классе, входящую в набор всех классов:

FIND FIRST CLASS WITHIN ALL_CLASSES

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

GET

Набор устроен так, что можно перебирать (обычно в цикле) в определенном порядке дочерние записи, входящие в этот набор (FETCH — это FIND и сразу GET):

FETCH NEXT CLASS WITHIN ALL_CLASSES

От текущей записи можно по стрелке «провалиться» к дочерней:

FETCH NEXT PART WITHIN CLASS_PART

А можно от дочерней записи подняться к родительской:

FETCH OWNER WITHIN CLASS_PART

Вот практически и готов отчет, по заданному классу выводящий все детали этого класса. Для того, чтобы лучше прочувствовать работу с навигационной БД, интересно посмотреть на фрагмент этой программы на Коболе, а заодно прочувствовать развитие языков программирования за прошедшие полсотни лет.

...
SET DONE TO FAILURE.
DISPLAY "Class number: >" NO ADVANCING.
ACCEPT CLASS_ID.
FETCH FIRST CLASS WITHIN ALL_CLASSES USING CLASS_ID
AT END
    DISPLAY "Class not found"
    SET DONE TO SUCCESS.
IF DONE IS FAILURE
    DISPLAY "Parts for class number ", CLASS_ID, ":".
PERFORM UNTIL DONE IS SUCCESS
    FETCH NEXT PART WITHIN CLASS_PART
    AT END
        SET DONE TO SUCCESS
    END-FIND
    IF DONE IS FAILURE
        DISPLAY PART_ID
    END-IF
END-PERFORM.
...

По каким-то не очень понятным соображениям сетевые СУБД не поддерживают наборы, в который один и тот же тип записей входит два раза. Поэтому для реализации иерархии деталей приходится использовать вспомогательную таблицу COMPONENT. Ее связывают с PART два набора: PART_USES определяет компоненты, из которых состоит деталь, а PART_USED_ON показывает деталь, соответствующую компоненте.

Приведу еще один фрагмент программы, выводящей список деталей, непосредственно используемых для сборки данной. В отличие от предыдущего, он написан в традиционной для того времени манере с оператором GO TO (против которой в 1968 году выступил Эдсгер Дейкстра в своей статье Go To Statement Considered Harmful).

...
    DISPLAY "Part number: >" NO ADVANCING.
    ACCEPT PART_ID.
    FETCH FIRST PART WITHIN ALL_PARTS USING PART_ID
    AT END
        DISPLAY "Part not found"
        GO TO ALL-DONE.
    DISPLAY "Parts used on part number ", PART_ID, ":".
COMPONENT-LOOP.    
    FIND NEXT COMPONENT WITHIN PART_USES
    AT END
        GO TO ALL-DONE.
    FETCH OWNER WITHIN PART_USED_ON RETAINING PART_USES.
    DISPLAY PART_ID.
    GO TO COMPONENT-LOOP.
ALL-DONE.
...

В этом примере фраза RETAINING говорит о том, что при выполнении операции набор PART_USES не должен изменить запись, которую он считает текущей. Таким образом, для записи PART мы перебираем дочерние записи COMPONENT по набору PART_USES, временно приподнимаясь к родителю PART уже по другому набору PART_USED_ON, не нарушая порядок итерации первого набора.

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

Подведем некоторые итоги:

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

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

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

Кстати, навигационные СУБД живы до сих пор и неплохо себя чувствуют в своей нише (достаточно посмотреть сайт IBM о СУБД IMS). Так же, как жив и Кобол.

Продолжение следует: 3. Реляционная алгебра.

Почитать и посмотреть )

egorius: (Default)

Говоря о истории языка SQL, на первый взгляд кажется логичным начать с 1969 года, в конце которого Эдгар Фред Кодд, работавший в исследовательском отделении IBM в Сан-Хосе, написал свой отчет, положивший начало реляционной теории, а вместе с ней и реляционным базам данных.

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

История развития вычислительной техники начиная с изобретения абака — это так или иначе история автоматизации вычислений. Даже само слово «вычислительная» говорит об этом (и в английском языке тоже: «computer», «calculator» — вычислитель).

Важная переломная точка приходится на XIX век. Типичной задачей того времени, требовавшей большого объема вычислений, был расчет различных таблиц (например, логарифмических или тригонометрических). Работа над устройствами, способными автоматически справляться с вычислениями, привела Чарльза Бэббиджа к его знаменитой ныне Аналитической машине. Другие устройства того времени были спроектированы для решения какой-либо одной конкретной задачи, Аналитическая же машина была по задумке Бэббиджа программируема.

Она состояла из блоков, присутствующих теперь в любой ЭВМ: арифметическое устройство, запоминающее устройство, управляющее устройство, периферия (ввод программы и данных с жаккаровских перфокарт и вывод результатов на печать). К сожалению, Аналитическая машина никогда не была построена, хотя это и неудивительно: за неимением лучшего в середине XIX века, Бэббидж спроектировал свою машину на механической элементной базе (то есть в прямом смысле на рычагах и шестеренках).

Однако заложенные в машину принципы оказались настолько удачными, что они во многом определили дальнейшее развитие вычислительной техники. Говард Эйкен, создавший в 1943 году (при участии IBM — так уж получилось, что эта корпорация будет встречаться нам постоянно) первую реально работавшую программируемую машину Automatic Sequence Controlled Calculator (для краткости названную Mark I), признался: «Живи Бэббидж на 75 лет позже, я остался бы безработным». Фактически Mark I повторял архитектуру Аналитической машины, но на более современной элементной базе (Эйкен использовал как механические элементы, как и электромеханические реле).

Аналитическая машина, к слову говоря, оказала влияние и на программирование. Благодаря как самому Бэббиджу, так и Аде Лавлейс (дочери «того самого» лорда Байрона) мы получили такие понятия, как цикл, условный переход и библиотека подпрограмм.

Некоторое время после появления ЭВМ их продолжали использовать только для вычислительных задач (в основном с военной спецификой: расчет баллистических таблиц, вычисления для создания водородной бомбы, криптография). Но уже к концу 1940-х появилось понимание, что наряду с чисто математическими задачами, программируемый компьютер может решать и задачи бизнеса. Первыми ласточками стали великобританский EDSAC (1949) и построенные в начале 1950-х на его основе коммерческая система LEO (применялась для расчета зарплаты, складского учета, планирования производства — практически ERP), а также американский UNIVAC (1951), созданный для хранения, обработки и печати большого объема данных (в качестве внешней памяти использовалась магнитная лента емкостью порядка миллиона символов, лентопротяжное устройство обеспечивало скорость 12500 символов в минуту).

Более широкому применению ЭВМ в бизнесе мешало отсутствие запоминающего устройства большой емкости с произвольным доступом: магнитная лента по своей сути последовательна, а магнитные барабаны имели небольшую емкость и использовались в основном как дополнительное «медленное» ОЗУ. Ситуация изменилась в 1956 году с изобретением IBM жестких магнитных дисков и появлением первого НЖМД IBM 350 Disk File (устройство имело емкость 5 миллионов символов и состояло из 50 дисков, вращающихся со скоростью 1200 оборотов в минуту).

«Появление запоминающих устройств прямого доступа стало причиной переворота в мышлении... Направления, обозначаемые словами в и из, поменялись на обратные. Если директива ввод в мире последовательного доступа к файлам означала с ленты в вычислительную машину, то новая директива ввод означает в базу данных» — писал Чарльз Бахман, создатель первой СУБД.

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

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

Решать эти задачи каждый раз заново в каждом приложении, работающем с базой данных, совершенно неинтересно. Поэтому уже в 1961-64 годах появилась первая система управления базами данных, IDS (Integrated Data Store), спроектированная упоминавшимся выше Чарльзом Бахманом. Идеологию этой СУБД Бахман принес с собой и в комитет CODASYL (Conference on Data System Languages).

Первоначальной задачей комитета, объединившего в 1959 году представителей многих компаний, связанных с обработкой данных, являлась разработка универсального языка программирования для решения задач, ориентированных на бизнес. К началу 1960-х уже существовал ряд языков высокого уровня, из которых стоит упомянуть Фортран (разработан Джоном Бэкусом для решения вычислительных задач в 1954 году в исследовательском отделении IBM в Сан-Хосе), Алгол (разработан в 1958 году комитетом европейских и американских ученых, включая и Бэкуса; имел академическую направленность), Лисп (первый функциональный язык; создан в 1958 году Джоном Маккарти из MIT).

Результатом работы CODASYL явился новый язык Кобол (COBOL, Common Business-Oriented Language). Позднее, в 1965 году, в составе CODASYL при участии Бахмана выделилась группа по базам данных, которая выработала сетевую модель баз данных. Команды для работы с БД интегрировали в Кобол — аналогичным образом 20 лет спустя Oracle интегрирует SQL в PL/SQL.

За работу по созданию первой СУБД и за участие в работе CODASYL, Бахман в 1973 году стал лауреатом премии Тьюринга, вручаемой ежегодно с 1966 года ассоциацией ACM «исследователю, выбранному за полезные сообществу программистов и пользователей достижения технического характера».

Продолжение: 2. Программист-навигатор.

Почитать и посмотреть )

Profile

egorius: (Default)
egorius

September 2017

M T W T F S S
     123
45678 910
1112131415 1617
18 19 202122 23 24
252627282930 

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 07:26 am
Powered by Dreamwidth Studios