История SQL. 6. System R, Phase Zero

Начало: 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).

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