Reminiscences on Influential Papers
Richard Snodgrass, editor
Я попросил нескольких известных и представительных людей из сообщества баз данных выбрать одну статью, которая оказала основное влияние на их исследования, и описать, что в этой статье понравилось и как она на них подействовала. Некоторые из перечисленных здесь статей действительно изменили направление карьеры читателей. Большинству из упоминаемых статей около двадцати лет от роду, но две из них были опубликованы в последние пять лет.
Laura Haas, IBM Almaden Research Center,
[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,
[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,
[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,
[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,
[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,
[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,
[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,
[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]
В этой статье дается математическая формулировка проблемы добывания ассоциативных правил. Эта проблема состоит в идентификации набора элементов, часто появляющихся вместе в одной транзакции. Проблема декомпозируется на две подпроблемы. Первая состоит в генерации больших наборов элементов на основе поддержки; вторая - в порождении из больших наборов элементов ассоциативных правил на основе доверия.Эта пионерская работа обеспечила элегантную формулировку проблемы, которая преобразует ее из абстрактной в алгоритмическую. Работа открыла новую область для будущих исследований. В дополнение к потенциальным возможностям исследований более быстрых алгоритмов добывания и расширений моделей, я был очень заинтересован вопросами статистической значимости правил на основе мер, отличных от поддержки и доверия, таких как совместная сила, являющаяся мерой корреляционного типа, а также оперативной интерактивной генерации правил, предоставляющей пользователям больший контроль в отношение того, какие правила следует генерировать и как специфицировать параметры.
