egorius

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

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!

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

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

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

• Gunfight at the O.K. Corral — тот самый вестерн, основанный на реальных событиях 1881 года.
• «Query-by-Example: a data base language» — статья про QBE, имеется перевод.
• Терминал IBM 3270 — на таких разрабатывалась System R и DB2.
• System/370 Model 145 на сайте IBM. Там же есть и другие вещи, представляющие интерес для археологов.

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

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

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

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

Начало: 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. Реляционное исчисление.

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

Говоря о истории языка 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. Программист-навигатор.

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