Database Programming & Design



         

Reminiscences on Influential Papers - часть 3


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. (Алгоритм Бернстейна и Чью был органичен случаем наличия не более одного атрибута соединения между двумя отношениями, т.е. полусоединениями с одним доменом.) Это была моя первая аспирантская статья и стартовая точка моей исследовательской работы.


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