Классика баз данных - статьи

       

a dynamic index structure for


Timos Sellis, National University of Athens,

[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,

[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 в качестве стандартной конструкции.



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