ACM SIGMOD Record

Volume 27, Number 1, March 1998
Volume 27, Number 3, September 1998

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

Richard Snodgrass, editor

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

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

Я попросил нескольких известных и представительных людей из сообщества баз данных выбрать одну статью (часто это весьма не просто!), которая оказала основное влияние на их исследования, и описать, что в этой статье понравилось и как она на них подействовала. Их ответы читаются с интересом и устраняют иногда непредсказуемое забывание хороших идей.

Elisa Bertino, University of Milan, bertino@dsi.unimi.it

[P.P. Griffits and B. Wade, "An Authorization Mechanism for a Relational Database System", ACM Transactions on Database Systems, 1(3):242-255, 1976.]

Мне было очень легко выделить статью, значительно повлиявшую на мои исследования. Это статья Пат Гриффитс и Боба Вейда про модель авторизации System R. Причина, по которой мне понравилась эта статья при первом чтении, состоит в том, что она посвящена реальной важной проблеме - проблеме контроля доступа в системах баз данных. В то же время статья обеспечивает надежную теоретическую базу для размышлений о моделях и механизмах контроля доступа. Описанный подход был использован в качестве основы механизмов контроля доступа в нескольких коммерческих СУБД. Когда, спустя годы, я решила выполнить исследовательскую работу по поводу механизмов контроля доступа к базам данных, я использовала подход, предложенный Пат и Бобом, в качестве отправной точки своих исследований. Вместе с некоторыми своими коллегами мы разработали несколько расширений модели контроля доступа, предложенной изначально для System R, включая нерекурсивные операции revoke, отрицательную авторизацию, темпоральную авторизацию. Наконец, эта статья может использоваться как руководство при обучении студентов механизмам контроля доступа в реляционных СУБД.

Mike Carey, IBM Almaden Research Center, carey@almaden.ibm.com

[C. Zaniolo, "The Database Language GEM", in Processing of the 1983 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 1983, D. Dewitt and G. Gardarin, eds, pp. 207-218.]

Это одна из моих любимых статей в области баз данных - я бы сильно рекомендовал ее каждому, кто работает над объектными расширениями реляционных систем баз данных. Коротко говоря, в статье расширяются реляционная модель и реляционный язык запросов (Quel) для обеспечения более строго типизированных таблиц, обобщения, ссылок, путевых выражений и атрибутов с множественными значениями. Жемчужиной (gem; намеренный каламбур!) эту статью делает то, что эти расширения являются удивительно понятными, простыми и естественными. Хотя некоторые "реляционные фанатики" даже сегодня утверждают, что отношения и объекты соотносятся примерно так же, как масло и вода, я полагаю, что почти 15 лет тому назад Заниоло в своем исследовании GEM многими способами доказал их неправоту. В число основных моментов статьи входят введение точечной нотации для путевых выражений, ясный подход к рассмотрению взаимодействия неопределенных значений и путевых выражений, уникальная система типов и подход к работе с множествами. Эта статья сильно повлияла на работу над объектно-ориентированными моделью данных и языком запросов, которую мы выполняли в контексте проекта EXODUS в Висконсине (Wisconsin). Статья продолжает оказывать воздействие на мое видение мира при выполнении моей текущей работы над объектно-реляционными расширениями для DB2 UDB (Universal DataBase) и SQL3.

Jim Gray, Microsoft Research, gray@MICROSOFT.com

[D. Bitton, D.J. DeWitt, C. Turbyfill, "Benchmarking Database Systems: A Systematic Approach", in Processing of the International Conference on Very Large Databases, October, 1983, Florence, Italy, M. Schkolnick and C. Thanos, eds., pp. 8-19.]

В начале 1970-х имелся большой энтузиазм по поводу машин баз данных, специальных аппаратных средств, которые должны были каким-то образом решить проблемы производительности, досаждавшие системы баз данных в то время. Идея заключалась в том, что если выдающиеся исследователи баз данных смогут обойти ограничения файловой и операционной системы, если они смогут работать на "голом металле", то можно получить в десять раз более быстрые продукты. Имея сердечную склонность к миру ОС, я был смущен тем, что эти ребята рассчитывали выполнять ввод/вывод лучше, чем это удавалось нам - похоже, что они не понимали сути прерываний. И не только это, похоже, что они не принимали во внимание все тонкости обработки ошибок, мультипрограммирования, мультипроцессирования, безопасности и т.д. В один из дней ко мне пришло озарение: я прочитал статью Биттона-ДеВитта-Турбифилла. Внезапно я осознал, что происходит: я работал над тем, что теперь назвали бы проблемами оперативной обработки транзакций, в то время как мои друзья из области машин баз данных работали над тем, что теперь назвали бы добычей данных (data mining). Они выполняли соединения, они сканировали целиком 4-х мегабайтную базу данных, в то время как я выполнял мелкие транзакции над гигантскими по тем временам базами данных (500 Мб). Я беспокоился о безопасности, асинхронности, восстанавливаемости, управляемости, в то время как их заботили последовательные сканирования, агрегаты и, в особенности, соединения.

Чтобы кристаллизовать эти различия, я написал заметку "A Measure of Transaction Processing", в которой описывалась OLTP-транзакция. В конце концов, это привело к возникновению Transaction Processing Performance Council и тестового набора TPC-A. В статье описывались мини-пакетная транзакция пользовательского уровня (копирование 1000 записей) и пакетная транзакция (сортировка миллиона записей). К сожалению, отсутствовала работа по копированию и восстановлению. Статья циркулировала в широких массах. Около 25 человек что-то добавили. Чтобы избежать необходимости получения согласия юристов из компаний ATT, DEC, Xerox, IBM и Tandem, мы опубликовали статью под псевдонимом Anon Et Al. Статья появилась в первоапрельском номере журнала Datamation в 1985 г. Теперь каждый год первого апреля вручается памятная награда SIGMOD системам и группам, получивших лучшие результаты на этом тестовом наборе. Как-то я получил письма на имя Dr. Anon (в Tandem знали секрет и получали удовольствие от этой шутки).

Ирония этой истории состоит в том, что Висконсинский тестовый набор (Wisconsin Benchmark) в результате породил тестовый набор TPC-D. TPC-D теперь находится в центре великих сражений за производительность СУБД.

Henry F. Korth, Bell Laboratories, Lucent Technologies Inc., hfk@lucent.com

[J.N. Gray, R.A. Lorie, G.R. Putzolu, and I.L. Traiger, "Granularity of Locks and Degrees of Consistency in a Shared Data Base", in Modelling in Data Base Management Systems (G.M. Nijssen, ed.), North Holland Publishing Co., 1976, pp. 365-395.]

Когда меня попросили написать короткую заметку про одну статью, оказавшую основное влияние на мои исследования, мой выбор был абсолютно ясен. Ключевым словом было влияние. Хотя я читал больше отличных статей, чем могу пересчитать (несмотря на то, что их число исчислимо!), очень немногие статьи оказали серьезное влияние на программу моих исследований и на мой способ решения исследовательских проблем. Статья Грея-Лури-Путцолу-Трейгера относительно гранулированности блокировок - это не только первая статья, оказавшая серьезное воздействие на мою работу, но и наиболее влиятельная.

Первый раз я прочитал эту статью в 1978 г. будучи аспирантом, специализирующимся на исследованиях баз данных, области о существовании которой я и не подозревал за год до этого. Джеф Ульман (Jeff Ullman), мой руководитель дал мне несколько довольно теоретических статей, имеющих отношение к управлению параллельным доступом к базам данных. Хотя эти статьи были действительно хорошими, у меня отсутствовало интуитивное понимание сути реальной проблемы управления тразнакциями в базах данных. Тогда Джеф указал мне на работы проекта System R, включая упоминавшуюся статью про гранулированность блокировок. Читая эти статьи и в особенности статью про гранулированность блокировок, я связал формальные понятия корректного параллельного выполнения с практическими требованиями дешевых протоколов с высокой степенью параллельности. Размышляя над идеями, введенными в статье, я решил выбрать темой своей диссертации управление параллельным доступом к базам данных (я представлял авторов статьи пожилыми людьми с короткими седыми волосами). Воздействие этой работы неизмеримо возросло, когда я провел следующее лето (1979 г.) с Джимом Греем, Пат Селинджер и группой System R (я был поражен несоответствием своих представлению реальному образу авторов и видом "бизнес"-офиса с креслом в форме мешка с фасолью). Глядя в прошлое, я считаю, что влияние на меня этой статьи частично связано с тем, что я познакомился с ней в нужное время, но я думаю, что основной источник ее влияния - это разумная смесь теории, текущих практических проблем и связи с существующими системами.

Betty Salzberg, Northeastern Univeresity, salzberg@ccs.neu.edu

[C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh and P. Schwarz, "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging", ACM Transactions on Database Systems, 17(1):94-162, March 1992.]

Для меня статья про ARIES была важной потому, что она позволила мне создать ясное представление о механизмах восстановления в системах баз данных. Например, я увидел как используются Log Sequence Numbers (LSNs) для поддержки протокола Write-Ahead-Logging (WAL). В этом протоколе говорится, что до записи на диск страницы, измененной незафиксированной транзакцией, (до изменения на диске предыдущей версии страницы) предыдущее состояние измененной записи должно уже находиться где-нибудь еще на диске. Но всегда важно понимать некоторый механизм, поддерживающий выполнение теоретического правила. Общеупотребительным механизмом поддержки WAL являются LSN. Проставленный в странице базы данных P LSN = L - это LSN записи в журнале по поводу самого последнего изменения страницы P. Журнальные записи содержат предыдущее состояние измененных записей, и журнальные записи пишутся последовательно в порядке возрастания LSN. Если LSN самой последней журнальной записи, помещенной на диск, меньше L, то WAL полагает, что страница P еще не записана на диск. Сначала на диск должна быть помещена часть журнала, содержащая журнальную запись с LSN = L. Это один из многих механизмов восстановления, которого я не знал, и я думаю, что его не знали многие другие исследователи баз данных, пока им не стали доступны статьи про ARIES.

Чтение статьи во-многом повлияло на мои следующие исследования. Например, в моих исследованиях методов параллельного доступа и восстановления для методов доступа типа B-деревьев (II-дерево и hB-II дерево) LSN использовались для определения того, изменялась ли индексная страница со времени последнего ее посещения. (Если она не изменялась, можно избежать нового поиска в дереве.) Аспекты сравнения механизмов защелок (latches) и блокировок и поддержки тонко гранулированных блокировок, освещенные в статье про ARIES, были существенны для II-дерева и hB-II дерева. В этой статье была разъяснена концепция странично-ориентированного восстановления в сравнении с логическим восстановлением, и она также использовалась в II-дереве и hB-II дереве. В моих исследованиях в областях транзакционных потоках работы (Transactional Workflow) и оперативной реорганизации использовался метод воспроизведения истории по журнальным записям (из ARIES) для воссоздания системных таблиц и/или восстановления состояния выполняемого приложения. Теперь я почти не в состоянии представить систему баз данных без механизма восстановления в стиле ARIES.

Dennis Shasha, New York University, shasha@shasha.cs.nyu.edu

[P.L. Lehman and S.B. Yao, "Efficient locking for concurrent operations on B-trees", ACM Transactions on Database Systems, 6(4):650-670, December 1981.]

Моими любимыми статьями всегда были такие, которые изменяли мои интеллектуальные предубеждения. Я прочитал статью Лехмана и Яо в 1981 г., когда старался найти тему для диссертации. Я изучал теорию управления параллельным доступом у Фила Бернштейна (Phil Berstein) и Ната Гудмана (Nat Goodman), когда оба они были в Гарварде, и был убежден в том, что конечной точкой является предупреждающая конфликты сериализуемость. В статье Лехмана и Яо были показаны исключения, очевидно, корректные, но не накрываемые этой моделью. На следующий год, пытаясь усилить модель, я понял, что требуется новая модель, и написал свою диссертацию об обобщенной модели параллельного доступа в индексных структурах.

Hector Garcia-Molina, Stanford University, hector@db.standford.edu

[K.P. Eswaran, J.N. Gray, R.A. Lorie, and I.L. Traiger, "The Notion of Consistency and Predicate Locks in a Database System", Communications of the ACM, 19(11):624-633, November 1976.]

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

Tomasz Imeilinski, Rutgers University, imelins@rutgers.edu

[R. Reiter, "On Closed World Databases", in Logic and Databases, H. Gallaire and J. Minker (eds), Symposium on Logic and Data Bases, Centre d'etudes et de recherches de Toulouse, 1977. Advances in Data Base Theory, Plenum Press, New York, 1978, pp. 55-76.]

Я выбрал статью, которая поразила меня и оказала влияния на меня и на большое число исследователей, работавших (подобно мне) или работающих сейчас над логическими основами баз данных. Эта и несколько других статей Рея Рейтера положили начало новому подходу к пониманию баз данных - с упором на точную логическую формулировку скрытых предположений относительно содержимого базы данных при выполнении запросов. В статье приводится простое, но фундаментальное наблюдение, касающееся того, что имеются два в равной степени разумных способа интерпретации содержимого базы данных: предположение о замкнутости мира (факты, не выводимые из базы данных, являются ложными) и предположение об открытости мира (в действительности мы не можем ничего сказать о фактах, которые не могут быть логически выведены из баз данных). Рейтер замечает, что запросы SQL интерпретируют базу данных в соответствии с предположением о замкнутости мира, и приводит "недостающие" аксиомы. Его образ мыслей оказал влияние на мои исследования при подготовки диссертации PhD и на последующую работу в области дедуктивных баз данных. Хотя статья Рейтера не привела к появлению каких-либо "продуктов", как часто бывает сегодня, она является примером фундаментальной статьи, влияющей на способ мышления людей, и даже 20 лет спустя она все еще представляет собой важный источник для любого, кто изучает базы данных и их логические основы.

Работа Рейтера способствовала последующим исследованиям немонотонных логик и различных форм отрицания путем отказа (negation by failure), она внесла значительный вклад не только в области баз данных, но также и в областях логического программирования и искусственного интеллекта.

David Maier, Oregon Graduate Institute, maier@cse.ogi.edu

[M.P. Atkinson, P.J. Bailey, K.J. Chisholm, P.W. Cockshott and R. Morrison, "An Approach to Persistent Programming", The Computer Journal, 26(4):360-365, November 1983.]

Я впервые столкнулся с Persistent Programming Group в Эдинбурге Скт-Эндрю в 1984 г. В это время я работал на компанию GemStone Systems (потом Servio Logic) в связи с проектом их машины баз данных и системы. В компании происходила фундаментальная переориентация от реализации модели данных с вложенными множествами на специализированной аппаратуре к созданию объектно-ориентированной системы баз данных, работающей на стандартных рабочих станциях. Я старался погрузиться в объектно-ориентированное программирование вообще и в Smalltalk в частности, чтобы понять проблемы и преимущества объектно-ориентированной модели данных. Питер Бьюнман (Peter Buneman) посетил группу в Шотландии и указал мне на их работу, услышав, что я работаю на GemStone.

Указанная статья является кратким введением в PS-algol, вариант S-algol с возможностями долговременного хранения. В статье раскрываются некоторые проектные решения для превращения языка программирования в язык баз данных (например, как указывать потребность долговременного хранения и как обеспечить эффективный доступ к крупным коллекциям данных) и приводится краткий обзор реализации. (Парная статья, опубликованная почти в то же время в журнале Software - Practice & Experience, содержит более детальную информацию о реализации.) Статья подействовала на мое мышление в нескольких направлениях. Во-первых, она заставила меня осознать, что попытка построить систему баз данных путем добавления к существующему языку программирования возможности долговременного хранения не является такой уж дурацкой идеей. Во-вторых, статья показала мне, какие аспекты GemStone связаны с его природой как языка программирования с долговременным хранением, а что определяется объектной ориентированностью. Например, в PS-algol свойство долговременного хранения было ортогонально системе типов, поэтому здесь объектная модель не при чем. С другой стороны, обеспечение логической независимости данных на основе наличия методов и расширяемость на основе подтипизации непосредственно связаны с наличием объектной модели. (Однако позже шотландская группа показала, добавив к PS-algol долговременно хранимые процедуры и компилятор времени выполнения, что существуют не объектно-ориентированные средства расширения типов.) В-третьих, статья помогла мне понять, что имеются общие проблемы в превращении языка программирования общего назначения в систему баз данных, такие как потребность в общей схеме и ассоциативных запросах, и что имеются такие варианты реализации, о которых я не думал, такие как перемешивание ссылок на объекты в памяти.

Pat Selinger, IBM Almaden Research Center, pgs@us.ibm.com

[B. Wegbreit, Studies in Extensible Programming Languages, Ph.D. Thesis, Harvard University, May 1970.]

Я присоединилась к группе баз данных IBM на раннем этапе создания System R, нашей первой попытки доказать, что на основе использования ориентированного на множества языка запросов реляционная система может иметь практическую реализацию с сохранением независимости данных, провозглашаемую реляционной моделью. Поэтому я предполагала выбрать знаменитую статью Кодда 1971 г. о реляционной модели данных, но это показалось мне слишком очевидным. Но на самом деле, у меня имелся более хороший выбор, с которым я скоро вас познакомлю. Я присоединилась к проекту System R потому, что там были умные люди, с которыми было интересно говорить. Я сделала свою диссертацию PhD на основе комбинации операционных систем и языков программирования и до поступления в IBM не знала буквально ничего о технологии баз данных. В IBM в первый же день мне вручили книгу Криса Дейта и сказали: "Читай это". Я думала, что имею небольшие шансы внести большой вклад в выполнение проекта. Оказалось, что я была не права. Технологии операционных систем и языков программирования в действительности имеют огромное отношение к системам баз данных: концепция компиляции, концепция изучения альтернатив при генерации кода и выборки оптимальной альтернативы, параллельность, мультипроцессирование ... и многое другое. При воплощении реляционной системы мы применяли то, что узнали в этих других областях, и адаптировали многие из этих концепций применительно к базам данных в этом первом поколении РСУБД.

Однако одно направление технологии языков программирования не получило тогда должного применения. Я прочитала диссертацию PhD Бена Вегбрейта в начале 1970-х (да, я знаю, что это было очень давно). Это было одно из первых исследований в области расширяемых языков программирования, перегрузка функций, определяемые пользователями типы и функции. Эта работа оказала глубокое влияние на мои представления о том, что можно было бы сделать с языками программирования; они могли бы быть живыми, активными созданиями, а не только изложенным в руководстве статическим синтаксисом, используемым для выполнения конкретной задачи. Читая эту статью и помогая применять многие другие концепции языков программирования в технологии баз данных, я очень заинтересовалась возможностью применения свойства расширяемости языков программирования в базах данных таким образом, чтобы не разрушить простоту реляционной модели. В середине 1980-х у нас была такая возможность. Когда закончился проект распределенной системы R*, мы искали идеи для нового проекта, включая возможность построения системы баз данных второго поколения, основанной с самого начала на расширяемом, активном, живом ядре управления базами данных. Эта концепция расширяемости вызвала у нас настолько большой интерес, что мы решили развить ее более глубоко. Родился проект Starburst, и то, что мы называли тогда расширяемыми базами данных, легло теперь в основу объектно-реляционных систем баз данных, которые сегодня являются продуктами, почти через 30 лет после того, как технология баз данных была впервые связана с технологией языков программирования.

Jeffrey Ullman, Stanford University, ullman@db.stanford.edu

[P.A. Bernstein, "Synthesizing Third Normal Form Relations from Functional Dependencies", ACM Transactions on Database Systems 1(4):277-298, March, 1976.]

В 1975 г. Катриел Бири (Catriel Beeri) получил преподавательский пост в Принстоне после того, как провел год в качестве стипендиата университета Торонто, работая с Деннисом Цикритзисом (Dennis Tsichritzis) и его студентом Филом Бернстайном в области теории баз данных. У Катриела был курс по реляционным системам баз данных, который я посещал вместе со своими студентами. Этот курс произвел огромное воздействие в области баз данных; например, по крайней мере пять студентов (плюс сам Катриел) впоследствии возглавляли основные конференции по базам данных. Одна из ведущих тем курса была тесно связана с указанной статьей, включая метод Фила проектирования схемы и его наблюдения о том, что ранние статьи о функциональных зависимостях, нормальных формах и ключах содержат существенные ошибки, которые он исправил путем тщательного анализа и доказательств. Эта работа убедила меня в том, что теория функциональных зависимостей обладает определенной глубиной и что стоит предпринять усилия для понимания ее тонкостей и следствий. Сегодня, когда конкретный алгоритм, представленный в статье, используется не так уж часто, основополагающие понятия, введенные Филом и Катриелом, являются основным элементом при обучении студентов Computer Science и настолько распространены, что уже не рассматриваются как "теория".