Database Programming & Design



         

Reminiscences on Influential Papers - часть 2


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 в Иерусалиме будет представлена статья, в которой прогонка применяется к весьма современной теме интеграции информации; сопредседатель этой конференции никто иной как Катриэл Бири.




Содержание  Назад  Вперед