ACM SIGMOD Record

Volume 27, Number 4, December 1998

Reminiscences on Influential Papers

Richard Snodgrass, editor

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

Laura Haas, IBM Almaden Research Center, laura@almaden.ibm.com

[P. 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]

Почему эта статья настолько важна для меня? Во-первых, потому что именно эта статья привлекла меня к работе в области баз данных. Я ненавидела свой аспирантский курс по базам данных, который отставил меня в уверенности, что в этой области нет ничего, кроме скучных вопросов моделирования баз данных. Вместо этого я изучала распределенные алгоритмы и в конце концов сделала диссертацию про распознавание распределенных тупиковых ситуаций. Очевидно, что это имело отношение к базам данных, и благодаря этой связи - которую я почти не признавала, поскольку это означало работу в области баз данных -- мне удалось получить работу в IBM. Однако я согласилась и скоро поняла, что в этой области имеется намного больше, чем модели данных! Среди многих статей, прочитанных мной в IBM в течение первого года или около того, была и эта, и она впервые заставила меня понять, что в этой области имеются действительно интересные проблемы, и, возможно, в решении некоторых из них я смогу когда-нибудь помочь. Немного поработав, я уже знала, что большая часть моей карьеры будет посвящена вопросам обработки запросов в целом и будет сосредоточена на работе в области оптимизации. Конечно, при том, что я действительно теперь работаю в этой области, статья Пат (Патриции Селинджер) является моей Библией - не в том смысле, что я смотрю в нее каждый день, но в качестве набора руководящих принципов и базовых правил, которые определяют мои повседневные работу и исследования.

Alberto Mendelzon, Computer Science Department, University of Toronto, mendel@cs.toronto.edu

[A.V. Aho, C. Beeri, and J.D. Ullman, "The Theory of Joins in Relational Databases", ACM Transactions on Database Systems, 4(3) : 297-314, September 1979]

В последнем номере Record Джефф Ульман вспоминал курс по базам данных Катриэла Бири в Пристоне в районе 1977 г. Эта статья (представленная в TODS в марте 1978 г.) была одним из первых продуктов, полученных на основе фермента курса Катриэля. Обсуждался следующий вопрос: при каких условиях набор функциональных зависимостей гарантирует, что любое отношение, удовлетворяющее этому набору, может быть декомпозировано без потерь информации? Для специального случая декомпозиции одного отношения в два решение было получено годом раньше Делобелем (Delobel) и Кейзи (Casey), а также Риссаненом (Rissanen), и в рукописи распространялось некорректное обобщение этого результата, полученное известными исследователями.

Будучи аспирантом и читая ранний вариант того, что потом стало известно как статья ABU, я поражался несколькими фактами: теория баз данных была настолько тонкой, что даже хорошо известные исследователи могли делать ошибки; что загадочный феномен "ловушки связи" ("connection trap"), обсуждавшийся в то время, можно было точно формализовать и проанализировать; что допускался юмор, так что Теорема 2 называлась "Теоремой Микки Мауса" по причинам, которые становились очевидными при взгляде на соответствующий рисунок (к сожалению, это название не вошло в опубликованный вариант статьи).

Простой и элегантный алгоритм проверки отсутствия потерь, который Джефф и Ал Ахо называли "нисходящей прогонкой зависимостей", явился стартовой точкой для Шаки Сагива (Shuky Sagiv), Дейва Майера (Dave Maier) и меня, в то время аспирантов, в работе, которая стала называться методом прогонки, остающемся и сегодня важным теоретическим средством. На самом деле, почти в то же самое время, когда выйдет этот номер Record, на конференции ICDT'99 в Иерусалиме будет представлена статья, в которой прогонка применяется к весьма современной теме интеграции информации; сопредседатель этой конференции никто иной как Катриэл Бири.

Meral Ozsoyoglu, Department of Computer Engineering and Science, Case Western Reserve University, ozsoy@alpha.CES.CWRU.edu

[P.A. Bernstein and D-M. W. Chiu. "Using Semi-joins to Solve Relational Queries", Technical Report No. CCA-79-01, Computer Corporation of America, 1979. (Also in JACM 28(1) : 25-40, 1981)]

Эта статья оказала наибольшее влияние на мои исследования. Когда я первый раз читал статью Берстейна и Чью в виде технического отчета в 1979 г., я был аспирантом в университете Альберты, и мой руководитель переехал в Чикаго. В это время я старался найти тему диссертации из области оптимизации запросов и прочитал несколько статей по обработке запросов и распределенным базам данных. Я заметил, что обработка некоторых запросов по их природе обходится более дорого, чем обработка некоторых других запросов, но не мог это формализовать. В отличие от других статей, которые основывались на эвристике, Бернстейн и Чью использовали очень новый подход: они классифицировали запросы на древовидные и циклические, ввели операцию полусоединения и показали, что в то время как ответы на древовидные запросы всегда могут быть получены с помощью полусоединения, для циклических запросов это может быть не так. Они также представили алгоритм для определения того, является ли запрос древовидным. Я был поражен, когда увидел, что этот алгоритм не применим к некоторым примерным запросам, которые я раньше, когда пытался построить схему оптимизации запросов, считал "типичными". Это побудило меня начать работать над обобщенным алгоритмом распознавания древовидных запросов и завершилось созданием диссертации про оптимизацию распределенных запросов на основе полусоединений. Наш алгоритм (созданный в соавторстве с моим руководителем C. Yu) был опубликован в том же году на конференции IEEE COMPSAC'79. (Алгоритм Бернстейна и Чью был органичен случаем наличия не более одного атрибута соединения между двумя отношениями, т.е. полусоединениями с одним доменом.) Это была моя первая аспирантская статья и стартовая точка моей исследовательской работы. В литературе этот алгоритм распознавания древовидных запросов позже стали называть "GYO-редукцией" (GYO Reduction).

Новый подход Бернстейна и Чью к обработке запросов и редукции на основе полусоединений оказал влияние на мои исследования и исследования многих других в области оптимизации запросов. И полусоединения, и классификация запросов на древовидные и циклические и сегодня используются в оптимизации запросов, через двадцать лет после того, как были введены Бернстейном и Чью.

Jan Paredaens, Department of Mathematics and Computer Science, University of Antwerp, pareda@uia.ua.ac.be

[A.K. Chandra and D. Harel, "Computable Objects for Relational Data Bases", Journal of Computer and System Science, 21 : 156-178, 1980]

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

Krithi Ramamrithan, Department of Computer Science, University of Massachusetts, on leave at the Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, krithi@cse.iitb.ernet.in

[C.T. Davies, Jr., "Data Processing Spheres of Control", IBM Systems Journal, 17(2) : 179-199, 1978]

Девис (в сотрудничестве с L.J. Bjork) ввел единую абстрактную управляющую структуру, а именно "сферы управления" (Spheres of Control) для достижения гибкой семантики почти каждого аспекта выполнения транзакций: атомарности процессов (читай - транзакций), фиксируемости, зависимостей между транзакциями, управления многопользовательским доступом, согласованности и восстановления. В простых терминах сферу управления можно представлять как границу, в одностороннем порядке ликвидирующую или фиксирующую эффекты произвольного набора операций. Сферы могут быть вложенными, последовательными или параллельными. Читая эту статью сегодня, любой человек, работающий в области развитого управления конкурентным доступом и обработки транзакций, вынужден спросить "Ну и что же здесь нового?" "Новое" состоит в том, что работа, описанная в статье, выполнялась в середине 1970-х! Можно утверждать, что все "предложенное" с тех пор -- для использования семантики приложений и данных в целях улучшения управления конкурентным доступом и восстановлением -- основано на повторном изобретении идей, изложенных в этой статье, которые долго ждали своего повторного открытия. К сожалению, поскольку многие термины, использованные в статье, возникли до появления ACID и устарели, требуется значительная работа для перевода статьи на язык современной терминологии, чтобы оценить "скрытые" в ней концепции.

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

Nick Roussopoulos, Department of Computer Science, University of Maryland, nick@cs.umd.edu

[J. Gray, A. Bosworth, A. Layman and H. Pirahesh, "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals", in Proceedings of the IEEE International Conference on Data Engineering, pp. 152-159, New Orleans, February, 1996]

Я впервые услышал об операции "Data Cube" Грея и Ко. с горячего западного побережья в 1995 г. на сипмозиуме CIKM'95 в Балтиморе. Я немедленно послал Джиму e-mail с просьбой прислать статью и получил в ответ URL его набора статей на новом его работе в Microsoft. Я скачал статью и начал ее читать, но, к моему разочарованию, рисунки, которые в этом конкретном случае стоят больше тысяч слов, были перечеркнуты надписями с каким-то бормотанием Microsoft. Я полагаю, что Джим еще осваивал программное обеспечение Microsoft! Тем не менее, я смог извлечь основные идеи до Ново-Орлеанской конференции, где смог увидеть эти рисунки.

Для области OLAP и складов данных значимость статьи про Data Cube эквивалентна значимости статьи Теда Кодда 1970-го г. для реляционных баз данных. В ней формализуются понятия многомерных агрегатных представлений и иерархии между ними. Она также устанавливает исходные идеи о сложности инкрементальных алгоритмов поддержки различных агрегатных функций. Эта статья громадно повлияла на мои исследования организации хранения на основе кибердеревьев (cybertrees) и их массового обновления. В 1995 г. я работал над материализованными представлениями с агрегатами и другими функциональными абстракциями. Для этого было самое время. Спасибо Джиму, Адаму, Эндрью и Хамиду.

Jennifer Widom, Departament of Computer Science, Stanford University, widom@DB.Stanford.EDU

[Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie and Thomas G. Price, "Access Path Selection in a Relational Database Management System", in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 20-34, Boston, 1979]

Мне повезло быть одним из ранних участников этой серии "влиятельных статей", поскольку я предполагаю, что эта конкретная статья будет появляться снова и снова [редактор: я действительно получил этот материал раньше, чем опубликованный выше материал Лауры]. Я думаю, что эта статья повлияла на меня иначе, чем на большинство других людей -- для меня она имела большей частью педагогическое значение. Когда я думаю о статьях, которые наиболее повлияли на меня с исследовательской точки зрения, на память приходит полдюжены. Когда я думаю о тех статьях, которые наиболее повлияли на меня с преподавательской точки зрения, то это именно данная статья.

Все мои причины любить эту статью очень значительны: (1) Прошло двадцать лет, а мы все еще используем ее в качестве программных спецификаций - мы все еще делаем оптимизаторы в "стиле Селинджер". В Computer Science, особенно в системной части, этот уровень эта долговечность поразительна. Только по одной этой причине статью стоит изучать. (2) Поскольку я не был специалистом в области оптимизации, эта хорошо написанная статья облегчила мое проникновение в тему и убедила меня в том, что оптимизация запросов - это интересная и сравнительно мало освоенная область с массой занятных заслуживающих изучения укромных уголков и трещин. Возможна ли лучшая тема для обучения студентов построению и исследованию систем? (3) Эта статья, статьи, которые она побудила меня читать, люди, с которыми она побудила меня говорить, все это убедило меня в том, что оптимизации запросов следует включить в базовый curriculum по углубленному изучению баз данных, причем на гораздо более глубоком уровне, чем это было раньше. Оптимизатор запросов - это сердце СУБД, и статья Селинджер и др. заставила меня понять, что с точки зрения образования мы все должны понимать все существующие в этой области сложности.

Phillip Yu, IBM IAC, T.J. Watson Research Center, psyu@us.ibm.com

[R. Agrawal, T. Imielinski and A. Swami, "Mining Association Rules between Sets of Items in Large Databases", in Proceedings of the ACM International Conference on Management of Data, pp. 207-216, May 1993, Washington, DC]

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