Воспоминания о наиболее влиятельных статьях (продолжение)

Уважаемые читатели!

Мы продолжаем знакомить вас с очень интересной колонкой Ричарда Снодграсса из журнала SIGMOD Record. Мне кажется, что это поучительный и полезный материал, особенно для тех, кто только входит в тематику баз данных. Лично мне особенно приятно, что многие из рассматриваемых статей (в частности, статьи Патриции Селинджер и Джима Грея) очень сильно повлияли и на меня.

До встреч, Сергей Кузнецов

---

ACM SIGMOD Record

Volume 28, Number 1, March 1999 (www.acm.org/sigmod/record/issues/9903/rem.ps)

Reminiscences on Influential Papers

Richard Snodgrass, editor

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

Serge Abitboul, INRIA, Serge.Abitboul@inria.fr

[A.K. Chandra and D. Harel, "Computable Queries for Relational Data Bases", Journal of Computer and System Sciences 21(2):156-178, 1980]

Статьи Чандры и Харела 1980-го и 1982-го годов являются очень важными. В то время у нас было очень ограниченное представление о языках запросов. Оно главным образом происходило от начальных статей Кодда. Кодд неявно наложил некоторые ограничения на языки запросов - "полноту запросов по Кодду". Поскольку его работа являлась математически обоснованной, имелось некоторое нежелание ее оспаривать. Та идея, что можно определить класс запросов независимо от конкретного языка, была чем-то новым. Выдвинув ее, Чандра и Харел открыли простор для большого числа работ по выразительности и сложности. Некоторые из введенных ими методов оказалось возможно применить в большом разнообразии контекстов.

Sophie Cluet, INRIA, Sophie.Cluet@inria.fr

[B.P. Jenq, D. Woelk, W.Kim and W-L. Lee, "Query Processing in Distributed ORION", in Proceedings of the Conference on Extending Data Base Technology, pp. 169-187, Venice, Italia, 1990

Некоторые люди говорят, что в модели ODMG не поддерживается декларативный язык запросов (но на самом деле поддерживает: OQL), в то время как в объектно-реляционном подходе такая поддержка имеется (будет иметься в будущем: SQL3). Другие распространяют слухи о том, что объектно-ориентированные запросы невозможно оптимизировать. В этой статье, явившейся поворотным пунктом, доказывается, что это утверждение истинно настолько же, что и то, которое часто приходилось слышать в 70-х про невозможность эффективной реализации SQL.

Дженк, Воулк, Ким и Ли были первыми, кто установил важный и часто игнорируемый факт: навигационные запросы и запросы с соединениями эквивалентны. Другими словами, методы реляционной оптимизации могут быть применены к OQL. В действительности, поддержка как ассоциативного, так и навигационного доступа - это источник дополнительной оптимизации. Объекты можно хранить на дисках многими разными способами. Если некоторые объекты кластеризованы вместе со своими компонентами, навигационные запросы наболее более эффективны, чем любые запросы с соединениями, которые можно было бы выполнить над двумя отношениями, хранящими ту же самую информацию. И наоборот, если они хранятся на разных страницах, то можно полагаться на соединения, чтобы получить та же эффективность, которой обладают реляционные системы. Следовательно, можно обладать лучшим из двух миров. Разве это не прекрасно?

Michael Franklin, University of Maryland, franklin@cs.umd.edu

[G. Copeland and D. Maier, "Making Smalltalk a Database System", In Processing of the ACM SIGMOD Conference on Management of Data, pp. 316-325, 1984]

Я впервые увидел эту статью в 1985-м или 1986-м году будучи студентом Wang Institute. Я тратил много времени на два прекрасных курса: Первый читался Филом Бернстайном (Phil Berstein) и посвящался обработки транзакций; курс основывался на только что завершенной книге, написанной совместно с Хадзилакосом (Hadzilacos) и Гудманом (Goodman). Вторым был семинар по объектно-ориентированным языкам программирования. В это время эти две темы казались совершенно несвязанными -- курс по базам данных ориентировался на пуленепробиваемые приложения в стиле COBOL, которые казалось более естественно писать ЗАГЛАВНЫМИ БУКВАМИ, в то время как у системы Smalltalk имелся удобный графический интерфейс и естественный способ моделирования данных, но можно было пропускать только игрушечные программы. Когда я впервые увидел статью Коупленда и Майера, я был поражен, обнаружив, что они пытаются соединить эти два мира. Однако в статье содержались убедительные аргументы в пользу того, что это естественное и важное дело. После окончания учебы я охотно принял предложение работать над развитием этих идей в MCC с Джорджем и группой Bubba.

Эта статья является одной из классических работ, которые побуждают многих людей переоценить свои базовые предположения. В добавлению к выявлению проблемы "потери соответствия" (impedance mismatch) между процедурными языками и системами баз данных и предложению устранить эту проблему в статье также описываются языковые конструкции и архитектура, позволяющие добиться этой цели. Результирующая система включала определяемые пользователем расширения типов с методами, иерархией типов, доступом к историческим данным, а также единообразный язык для запросов к базе данных, навигации и программирования в целом. Хотя имелись предшествовавшие работы по развитию реляционной модели и добавлению долговременного хранения (persistence) в языки программирования, эта статья была потрясающей основы в своей попытке гладко объединить идеи из баз данных, языков программирования и операционных систем таким способом, чтобы можно было поддерживать широкий спектр приложений. Сегодняшние системы баз данных, вообще говоря, не прошли весь путь к уменьшению потери соответствия, но идеи статьи явно повлияли на направление развития области исследований и индустрии. Статья напоминает, что для достижения прогресса мы должны постоянно иметь в виду ограничения, порождаемые текущими технологией и образом мышления.

Guy Lohman, IBM Almaden Research Center, lohman@almaden.ibm.com

[P.G. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price, "Access Path Selection in a Relational Database Management System", In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 23-34, Boston, 1979]

В этой статье обобщается то, как в System R оптимизировались SQL-запросы, и теперь это, вероятно, наиболее часто цитируемая статья в области оптимизации реляционных запросов. Поэтому не удивительно, что она оказала очень значительное влияние на мою карьеру, даже несмотря на то, что в то время я не работал в IBM и даже не начал заниматься оптимизацией запросов. Лично на меня громадное впечателение произвела презентация статьи, сделанная Пат (Патрицией Селинджер); наш диалог в результате привел к тому, что Пат стала моим менеджером, когда я включился в ее проект R* в IBM в 1982 г. Наше сотрудничество, уважение и дружба растут до сих пор.

Но важность этой статьи для всей области исследований существенно затмевает ее влияние на меня лично. В процессе тщательного изучения мой экземпляр истрепался и покрылся незначительными комментариями. После многократного перечитывания я продолжаю поражаться тому, как удалось поместить в эту статью глубокие и правильно обдуманные решения, как много идей, впервые отчетливо выраженных в статье, выдержало испытание временем и конкуренцией. Теперь у каждого крупного поставщика СУБД имеется оптимизатор запросов, в котором применяется большинство фундаментальных концепций, введенных в этой статье: использование статистической информации базы данных и моделирование стоимости выполнения -- а не упрощающих правил -- чтобы устранить большую часть стратегий доступа; избежание Декартовых произведений и применение динамического программирования и повторного использование подпланов для сокращения экспоненциального пространства поиска альтернативных порядков соединения; оценка мощности промежуточных результатов на основе вероятностных "показателей фильтрации"; распознавание планов, имеющих различные "интересные" порядки; выявление того, как предикаты могут быть применены наиболее эффективно (и создание памятного термина SARG; от "Search ARGument"); конвейеризация промежуточных результатов для избежания материализации; вычисление вложенных подзапросов; и много других деталей, которые невозможно здесь перечислить. Хотя за последние двадцать лет каждое из этих новшеств было усовершенствовано, выносливость исходных идей, по-моему мнению, является просто замечательной. Это поистине плодотворная работа.

David Lomet, Microsoft Research, lomet@microsoft.com

[J. Cray, "Notes on Database Operating Systems", IBM Technical Report RJ2188, 1978. Also published in Operating Systems: An Advanced Course. Springer-Verlag Lecture Notes in Computer Science. Vol. 60. New York.]

К концу 70-х - началу 80-х существовала горсточка успешных транзакционных систем баз данных - IMS, System R, Ingres, Oracle. Однако магика того, как в этих системах реализовывались транзакции, была, за исключением одной статьи, глубоко запрятана в недра реализаций систем. Этим исключением была статья "Notes", написанная Джимом Греем. Здесь впервые были собраны в одном месте протоколы фиксации, управление параллельным доступом и восстановление. Действительно, до этой статьи в литературе содержалось исключительно мало информации о восстановлении. По одной этой статье можно было образоваться по поводу журнализации с упреждающей записью, протокола журнализации DO-REDO-UNDO, установки контрольных точек для восстановления, рестартов, нескольких видов двухфазной фиксации, мультигранулированных блокировок, строгой двухфазной фиксации и т.д. Можно было также узнать про восстанавливаемые сообщения, управление записями и про множество системных деталей. В статье не только описывались решения трудных проблем, но объяснялось что и почему является важным.

Я жадно читал статью "Notes", когда она появилась (и, конечно, не один я) и возвращался потом к ней снова и снова. Сейчас статья немного устарела, ее частично потеснила статья про восстановление в System R, книга Бернстайна, Хадзилакоса и Гудмена и полностью затмила фундаментальная книга книга самого Джима (написанная совместно с Андеусом Рейтером [Andreas reuter]). Но статья "Notes", которая не появилась на конференции или в журнале, была единственной наиболее полезной статье в литературе по базам данных для целого поколения исследователей систем транзакций и разработчиков, среди которых и я. Действительно, мой интерес к проблемам восстановления зародился при чтении этой статьи, так что она продолжает влиять на направления моих исследований до сегодняшнего дня.

Gultekin Ozsoyoglu, Case Western Reverse University, tekin@ces.cwru.edu

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

Я читал статью Смита и Смита, когда искал тему своей диссертации на степень PhD в 1977 г. Эта статья производила исключительное впечатление своей глубиной, завершенностью и оригинальностью рассуждений при введении "иерархии абстракций агрегации и обобщения объектов" в моделировании данных. Хотя в статье эти иерархии применялись к реляционной модели и вводились "реляционные инварианты", на самом деле речь шла о семантическом моделировании данных на основе объектов, т.е. об объектно-ориентированных базах данных! Я помню, что тем летом читал статью несколько раз. В следующие годы я постоянно возвращался к этой статье, и в обязательном порядке заставлял читать ее студентов.

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

Raghu Ramakrishnan, University of Wisconsin, raghu@cs.wisc.edu

[F. Bancilhon, D. Maier, Y. Sagiv, J.D. Ullman, "Magic Sets and Other Strange Ways to Implement Logic Programs", In Proceedings of the ACM Principles of Database Systems Symposium, pp. 1-16, 1986]

Я присоединился к группе LDL компании MCC в Остине (Austin) в 1985 г., будучи студентом старших курсов UT-Austin. Конечно, я искал тему для дипломной работы и кое-что делал как в области баз данных, так и в области логического программирования. Поэтому я был подготовлен к восприятию идей этой изящной статьи. В статье показывалось, что распространение связывания, достигаемое в Прологе, может поддерживаться путем простых преобразований программ для некоторого класса программ и утверждалось, что методы реализации баз данных (например, методы эффективных соединений) могут быть применены для рекурсивных запросов.

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

Ken Ross, Columbia University, kar@cs.columbia.edu

[C. Nyberg, T. Barclay, Z. Cvetanovic. J. Gray, D. Lomet, "AlphaSort: A Cache Sensative Parallel External Sort", In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 603-627, 1994, and later in the VLDB Journal 4(4):603-627 (1995)]

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

Timos Sellis, National University of Athens, timos@dblab.ece.ntua.gr

[A. Guttman, "R-trees: a dynamic index structure for spatial searching", In Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 47-57, 1984]

Понятно, что в течение академической карьеры на каждого из нас оказывало влияние множество статей. Когда Рик попросил меня выделить только одну из них, я выбрал именно ту, которая повлияла на большую часть моих исследований, а именно, на мою работу в области методов пространственного доступа. Я имел счастье познакомиться с Антонином Гуттманом при подготовке моей диссертации PhD в Беркли, и у меня были хорошие возможности обсудить с ним свойства R-деревьев. Причиной того, что мне с первого чтения понравилась эта статья, состоит в том, что она посвящена очень важной и трудной проблеме - индексированию многомерных простанств, в которых невозможно определить очевидный порядок сортировки - и в ней предлагается изящный, понятный и элегантный метод решения проблемы. С моей точки зрения, эта работа открыла целую новую область исследований, которые привели к появлению известных удобных структур данных и алгоритмов, которые применяются даже в коммерческих системах. 15 лет спустя можно видеть, что продолжают появляться статьи, посвященные усовершествованиям и приложениям R-деревьев (в картинно-графических, пространственных, темпоральных базах данных, а также и более "экзотических" областях, таких, как хранилища данных), продолжая очень интересную линию исследований, начатую Антонином в его статье 1984-го г.

Patrick Valduriez, INRIA, Patrick.Valduriez@inria.fr

[M.M. Zloof, "Query-By-Example: Operations on the Transitive Closure", IBM Research Report RC 5526, Yorktown heights, New York, October, 1976, and in Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 47-57, 1984]

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