Воспоминания о влиятельных статьях

Richard Snodgrass, editor
ACM SIGMOD Records, No. 3, September 1999

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

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

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

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

---

Rakesh Agrawal. IBM Almaden Research Center, ragrawal@almaden.ibm.com

[A.V. Aho and J.D. Ullman. "The Universality of Data Retrieval Languages", inProceedings of Symposium on Principles of Programming Languages, pp. 110-117, 1979]

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

for t in R do <statement>

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

Philip Berrstein, Microsoft Research, philbe@microsoft.com

[R.H. Thomas, "A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases", ACM TODS 4 (2), pp. 1800-209, June, 1979]

В 1976 г. люди только начали размышлять о том, как можно было бы добавить распределенные транзакции и репликацию к возможностям системы баз данных. Я уверен, что первая хорошая статья - и до сих пор одна из лучших - была написана Бобом Томасом. Первый раз она была опубликована в 1976 г. в виде технического отчета Bolt Baranek and Newman и широко распространилась в этой форме. В статье были выдвинуты две очень важные идеи, которые активно используются сегодня. Во-первых, был определен консенсус большинства как способ определения возможности использования процессов при условии коммуникационных сбоев. Впоследствии эта идея была расширена Дейвом Гиффордом (Dave Gifford) в виде взвешенного большинства, или кворума. В большинстве современных алгоритмов распознавания сбоев используется этот метод. Во-вторых, в статье была введена возможность использования временных меток для пометки транзакций, изменений и элементов данных. Правило, основанное на временных метках, позволяют изменениям распространяться в любом порядке, хотя все реплики элемента данных в конце концов принимают одно и то же значение. Сегодня этот метод применяется в большинстве справочных сервисов мирового уровня, а также в некоторых интегрированных алгоритмах репликации в системах баз данных.

Статья очень сильно повлияла на начальные работы в области распределенных транзакций и репликации, в особенности на мои работы. Подход временных меток обосновал нашу работу над распределенной СУБД SDD-1 в Computer Corporation of America (iрошло, но не забыто). Перед нами стояла трудная задача разработать теорию сериализации при учете аспектов репликации и консенсуса большинства. Эти проблемы мотивировали некоторые ранние работы Лезли Лампорт (Leslie Lamport) в области надежных распределенных вычислений. Более того, многие интегрированные алгоритмы репликации основываются на векторах временных меток и непосредственных потомках этого алгоритма. Высокая концентрация новых идей и влияние как исследовательских работ, так и продуктов позволяют мне считать эту статью любимой в литературе о транзакциях.

Don Chamberlin, IBM Almaden Research Center, chamberlin@almaden.ibm.com

[E.F.Codd. "A Relational Model of Data for Large Shared Data Banks", Communications of the ACM, 13 (6): 377-387, June, 1970]

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

Jim Gray, Microsoft Research, gray@microsoft.com

[D. Bitton, D.J. DeWitt, and C.Turbifill. "Bechmarking Database Systems: A Systematical Approach". In Proceedings of the International Conference on Very Large Data Bases, M. Schkolnick and C. Thanos, eds, Florence, Italy, Morgan Kaufmann, October, 1983]

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

Я любил и ненавидел эту статью. Мне нравился тот факт, что это настоящая наука. Статья была посвящена хорошо документированным и воспроизводимым экспериментам и интересным и удивляющим результатам. Предложенный тестовый набор стал стандартной составляющей моих инструментальных средств измерения производительности. Но мне ужасно не нравилось то, для сканов и соединений использовались неявно определенные базы данных. Эта модель казалась слишком далекой от реально используемых баз данных (в моем мире). В ней отчетливо проявлялась дихотомия DSS и OLTP. Я создавал системы обработки транзакций и чувствовал себя брошенным. Поэтому я организовал неформальную группу исследователей и практиков (включая авторов этой статьи) для определения тестового набора для режима оперативной обработки транзакций (DebitCredit, Copy, Sort). Результаты этой работы были отражены в статье в Datamation ("A Measure of Transaction Processing Performance", Anon. et al., Datamation, 31 (7), pp. 112-118, April 1985) и в результате привели к TPC-A.

Don Haderle, IBM Santa Teresa Lab, haderle@us.ibm.com

[T. Haerder and A. Reuter. "Principles of Transaction-Oriented Database Recovery". In ACM Computing Surveys, 15 (4), pp. 287-318, December, 1983]

Много лет я занимался в IBM разработкой коммерческих операционных систем реального времени и систем управления данными. В 1976 г. я прочитал мартовский номер ACM Computing Survey, посвященный системам управления базами данных. Я был взволнован. При том, что я работал над основами программного обеспечения, другие люди говорили о работе с данными простым и дисциплинированным способом. Меня удивило, что за углом от меня толпятся исследователи System/R. В течение года я вошел в зарождающуюся группу, целью которой было создание менеджера баз данных следующего поколения, из которого вышла DB2.

Несколько лет я занимался разработкой компонентов DB2. Статья Хейрдера и Рейтера дала ясную абстракцию управления базами данных и основные требуемые свойства: атомарность, согласованность, изолированность и надежность. Эта статья предоставила мне основу к рассмотрению управления базами данных с точки зрения пользователя, а не производителя. При наличии четких определений свойств проще развивать возможности системы с целью решения проблем заказчика.

Won Kim, Cyber Database Solutions, Inc., won.kim@cyberdb.com

[T. Atwood, "An Object-Oriented DBMS for Design Support Applications", In Proceedings of the IEEE CompInt Conference, Montreal, Canada, Septemper, 1985]

За последние двадцать лет около дюжины статей помогло формированию моих собственных идей в области исследований баз данных Однако при том, что десять лет я связан с направлением объектно-ориентированных и объектно-реляционных баз данных, я должен отметить, что наибольшее влияние на меня оказала статья Тома Этвуда (в статье тома описывались планируемые возможности объектно-ориентированной системы баз данных, основанной на Vbase C++, которую позже стали называть Ontos; соответствующий доклад был признан лучшим на конференции).

Летом 1985 г., когда я работал в MCC, меня попросили переориентировать свой проект по базам данных для CAD в сторону объектно-ориентированных баз данных, поскольку в MCC программы CAD, Human Interface и AI все разрабатывались с использованием CommonLISP на LISP-машинах Flavors и Symbolics, и от них поступил запрос к программе Database, к которой относился я, разработать объектно-ориентированную базу данных, если люди из программы Database рассчитывают на то, что разрабатываемая ими технология будет встроена в другие технологии MCC.

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

Когда я выслушал доклад Тома Этвуда, а потом во время банкета, сидя рядом с ним, услышал его рассказ про язык определения типов, экземпляры типов, вложенные транзакции, я неожиданно понял, что нужно делать. Описанная Томом Этвудом система, конечно, была системой баз данных, но в первых выпусках Vbase отсутствовали разные возможности традиционных баз данных, а упор делался на поддержку долговременного хранения объектов Си++, что приводило к путанице на рынке. В любом случае в течение примерно года после этого дня я вместе со своей группой по разработке объектно-ориентированной базы данных ORION занимался систематическим переосмыслением всех архитектурных аспектов систем баз данных и старался понять, как влияют на архитектуру системы баз данных такие понятия как наследования, типы, ссылки и т.д.

Bruce Lindsay, IBM Almaden Research Center, bruce@almaden.ibm.com

[C. Nyberg, T. Barclay, Z. Cvtanovic, J. Gray, and D. Lomet. "AlphaSort: A RISC Machine Sort". In Proceedings of the ACM SIGMOD International Conference on Management of Data, R. Snodgrass and M. Winslett, eds, pp. 233-242, June, 1994]

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

C. Mohan, IBM Almaden Research Center, mohan@almaden.ibm.com

[R. A. Crus. "Data Recovery in IBM Database 2". IBM Systems Journal, 23(2) : 178-188, 1984]

В середине 80-х в контексте проекта Starburst в Almaden Research Center я решил вернуться к некоторым оставшимся открытыми со времени System R проблемам в области управления согласованностью и восстановления (Concurrency Control and Recovery - CC&R). Я пытался понять, как устроены CC&R в существующих СУБД, и наткнулся на статью Дика Краса. Статья предоставила мне очень хорошее введение в то, как были реализованы различные виды восстановления в раннем выпуске DB2. Без использования необходимых терминов в статье обсуждались такие понятия как журнализация с упреждающей записью, компенсационные журнальные записи и восстановление на основе журнальных последовательных номеров (Log Sequence Numbers - LSN). Эти описания дали мне возможность понять, чем эти базовые понятия стратегии восстановления в DB2/MVS отличаются от соответствующего подхода в System R. Статья также сделала явными для меня сложные проблемы (например, проблемы частичной записи страницы на диск), которые должны решаться в реальной системе и которым ранее не посвящались исследовательские публикации. Хотя в статье не разъяснялись обоснования принятия того или иного проектного решения, я взял на себя задачу выработки таких обоснований, а потом началась серия исследований, которая в конце концов привела к созданию семейства алгоритмов CC&R ARIES и появлению многочисленных статей, как моих собственных, так и статей соразработчиков из IBM. Хотя немного людей в сообществе исследователей читало статью Дика, на меня она оказала очень большое влияние. В то время, когда среди разработчиков коммерческих СУБД не было принято писать подробные технические статьи, Дик опубликовал статью с необычным числом деталей про внутреннюю организацию СУБД DB2/MVS для мейнфреймов.

Ron Morrison, University of St. Andrews, ron@st-and.ac.uk

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

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

Raymond Reiter, Department of Computer Science, University of Toronto, reiter@ai.toronto.edu

[J. McCarthy. "Programs with Common Sense", in Proceedings of the Teggington Conference on the Mechanization of Thought Processes, December, 1958. Available at

http://www-formal.stanford.edu/jms/mcc59.html]

Мне следует начать с небольшого замечания. Хотя я опубликовал несколько работ в "основной" литературе баз данных, я не рассматриваю их как непосредственно относящиеся к базам данных. И я не отношу себя к исследователям баз данных. Мои интересы всегда относились к проблематике представления знаний о мире и к методам использования этого представления. С этих позиций аспекты представления в теории баз данных, искусственном интеллекте, высокоуровневой роботехнике, естественных языках и даже некоторых языках программирования очень близки. Разделение этих сообществ в computer science является неудачным и вредным.

Все это привело меня к статье 1958 года МакКарти, в которой, по-видимому, впервые была предложена математическая логика как язык представления знаний для искусственного интеллекта. В этой статье МакКарти отчетливо обосновал преимущества декларативных предложений для представления знаний и предложил свою систему-"советчика", которая "инструктирует" по поводу предложений исчисления предикатов и использует дедукцию для определения того, как это впоследствии подействует на поведение системы. Фактически все мои исследования и те, которые делались во многих подкомитетах по искусственному интеллекту и базам данных, основывались на этой очень ранней работе МакКарти.

Carlo Zaniolo, Computer Science Department, UCLA, zaniolo@cs.ucla.edu

[J.M. Smith and D.C.P. Smith. "Database Abstractions: Aggregation and Generalization". TODS 2(2), pp. 105-133, June, 1977]

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

Многие из этих идей в настоящее время пересмотрены и применяются при разработке объектно-реляционных баз данных и ориентированных на них расширениях SQL: И в этом выражается признание значимости статью Джона и Дианы Смит.

C. Zaniolo. "The Database Language GEM", in Proceedings of the ACM SIGMOD International Conference on Management of Data. D.J. DeWitt and G. Gardarin, eds, pp. 207-218, 1983.

S. Tsur and C. Zaniolo. "An Implementation of GEM-Supporting a Semantic Data Model on a Relational Back-End", in Proceedings of the SIGMOD International Conference on Management of Data, B. Yormark, edd, pp. 286-295, 1984.

Ошибки

В информации о статье, обсуждавшейся Патриком Вальдурезом (Patrick Valduriez) в мартовском выпуске 1999, была допущена неверная ссылка. Вот правильный вариант:

M.M. Zloof. "Query-By-Example: Operations on the Transitive Closure", IBM Research Report RC 5526, Yorktown Heights, New York, October, 1976.