Главная » SQL, Базы данных » РЕАЛИЗАЦИЯ РЕЛЯЦИОННЫХ ОПЕРАТОРОВ TransRelational

0

В данном разделе кратко описано, какие следствия связаны с применением модели TR для реализации некоторых реляционных операторов. Соответствующие примеры основаны на  переменных отношения S и SPJ из базы данных поставщиков, деталей и проектов (примеры значений показаны на рис. А. 19). Полученная после слияния и сжатия таблица значений полей  приведена на рис. А.20, а "предпочтительные" таблицы реконструкции записей — на рис. А.21.

Рис. А. 19. Переменные отношения S и SPJ (примеры значений)

Рис. А.20. Слившаяся таблица значений полей для поставщиков и отгрузок

Сокращение

Рассмотрим следующий запрос на выполнение операции сокращения6.

SPJ WHERE QTY = 200

Для реализации этого запроса необходимо выполнить бинарный поиск в столбце QTY таблицы значений полей (см. рис. А.20) и найти ячейку, содержащую значение 200; следует отметить, что такая ячейка должна быть уникальной (если она вообще существует), поскольку данный столбец — сжатый. Если поиск оканчивается неудачей, это позволяет сразу же определить, что результат запроса пуст. Но в

6  В качестве основы для всех остальных примеров в этом приложении используется язык Tutorial D, a нe SQL.

Приложение А. Модель Trans Relationalm                                             1193 рассматриваемом случае поиск приводит к обнаружению ячейки [2,7] , которая, кроме заданного значения QTY, содержит диапазон строки [ 3 :6 ]. На основании этого можно сразу же сделать вывод, что ячейки [ 3 , 7 ] , [4,7], [ 5 , 7 ] и [6,7] таблицы реконструкции

записей поставок соответствуют описанным ниже требованиям.

а)   Содержат номера строк для ячеек таблицы значений полей, содержащих значение QTY,

равное 200

(и, безусловно, все они включают номер строки 2).

б)   Содержат номера строк для "следующей" ячейки в таблице реконструкции записей поставок.

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

Рис. А.21. Таблицы реконструкции записей для поставщиков и отгрузок

[ 3 ,7 ] ,   [ 1 , 1 ],   [2,5] ,    [ 2 , 6 ]

[4,7] ,   [ 3 , 1 ],   [3,5] ,    [ 3 , 6 ]

[ 5 , 7 ],   [ 8 , 1 ],   [7,5] ,    [ 4 , 6 ]

[ 6 ,7 ] ,   [ 9 , 1 ],   [9,5] ,    [ 6 , 6 ]

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

В качестве второго примера рассмотрим запрос, в котором используется сокращение с помощью оператора "<", а не с помощью оператора "=".

SPJ WHERE QTY < 150

Вполне очевидно, что этот запрос также может быть выполнен очень просто, но на этот раз с помощью описанной ниже процедуры.

а)   Выполнить последовательный поиск в столбце QTY таблицы значений полей.

б)   Реконструировать все  соответствующие  записи,  следовательно,  кортежи  пользовательского уровня для каждой ячейки, обнаруженной в процессе этого поиска.

в)    Остановиться, как только в столбце QTY таблицы значений полей будет найдена ячейка, содер жащая значение QTY, большее или равное 150.

Теперь рассмотрим следующий пример.

При этом будет получен следующий результат.

SPJ WHERE S# = S# (‘S3′) AND QTY = 100

Выполняя поиск в столбцах S# и QTY таблицы значений полей, можно обнаружить из соответствующих диапазонов строк, что есть четыре поставки с номером поставщика S3, но только две с количеством 100. Поэтому наилучшая  стратегия  состоит  в  использовании зигзагов, связанных с количеством 100, и проверке в процессе реконструкции записи для определения   того,   является   ли    номер   поставщика   равным   S3   (и   прекращении реконструкции рассматриваемой записи, если она не соответствует этому условию). При этом будет получен следующий результат.

Наконец, рассмотрим, что произойдет, если операция AND будет заменена операцией OR. SPJ WHERE S# = S# (‘S3′) OR QTY = 100

Этот запрос можно реализовать, во-первых, отыскав все кортежи для поставщика S3 и, во-вторых,  отыскав  все  кортежи,  еще  не  найденные  на  первом  этапе,  которые  имеют значение QTY, равное 100 (можно также выполнить эти действия  в  обратном порядке). Приняв  достаточно  обоснованное  предположение,  будто  эти  два  описанных  выше  этапа выполняются    таким    образом,    что    происходит     определенное    упорядочение    двух вырабатываемых результатов (скажем, в порядке возрастания значений S#), можно сделать вывод о том, что их слияние позволяет получить общий желаемый результат.

Проекция

Чтобы вычислить (скажем) проекцию SPJ{S#, P#, J#}, достаточно пройти просто через обычный процесс реконструкции для поставок, но пропустить этап реконструкции атрибута QTY в каждой записи. Но чтобы вычислить (скажем) проекцию SPJ{S#, P#}, которая, в отличие от предыдущего примера, требует устранения некоторых дубликатов, желательно    обработать    таблицу    реконструкции    записей    для    поставок    в    такой последовательности, которая позволяет получать кортежи в соответствии с упорядочением от основной детали к  дополнительной "S#, затем Р#" (или "Р#, затем S#"); при таком упорядочении  дубликаты станут смежными и поэтому могут быть легко удалены. Здесь подробные сведения об этом не приведены, но отметим лишь то, что "предпочтительные" таблицы реконструкции записей являются таковыми именно потому, что они поддерживают указанные варианты упорядочения.

Агрегирование

Рассмотрим следующий запрос.

SUMMARIZE SPJ PER S { S# } ADD COUNT AS SHIP_COUNT

Поэтому должно быть очевидно, что желаемый результат может быть непосредственно и немедленно

Ниже приведен полученный при этом результат.

Итак, столбец S# таблицы значений полей выглядит следующим образом (см. рис. А.20).

получен из данных о диапазонах строк в этом столбце.

Ниже приведен еще один пример (обратите внимание на то, что здесь используется вариант  BY

оператора SUMMARIZE).

SUMMARIZE SPJ BY { S# } ADD MIN ( QTY ) AS MNQ

Для того чтобы определить, как может быть реализован этот запрос, рассмотрим данные о  поставшике S2. Из диапазона строк [3 :5 ]  для этого поставщика в таблице значений полей  (см. рис. А.20) можно определить, что строками таблицы реконструкции записей поставок,  которые относятся к этому поставщику, являются строки 3, 4 и 5 (это означает, что применимыми ячейками этой таблицы являются, соответственно, [ 3 , 1 ] ,  [ 4 , 1 ]  и [5 , 1 ].  Проходя по зигзагам к  соответствующим ячейкам QTY в этой таблице, можно определить, что эти ячейки,  соответственно, содержат указатели на строки 2, 3 и 3 таблицы значений полей. Поскольку  столбец QTY (как и все столбцы) в этой таблице отсортирован в порядке возрастания, становится сразу же очевидно, что минимальным значением QTY для поставщика S2 является значение, находящееся в строке 2 таблицы значений полей, а именно значение QTY, равное 200.

Соединение

В предыдущих разделах уже было показано, что требуется для реализации соединений. Поэтому ниже просто указано несколько дополнительных требований.

■     Поскольку в модели TR всегда выполняется соединение по методу сортировки—слияния, а операции сортировки и слияния выполняются заблаговременно, то на этапе прогона затраты на выполнение операции соединения имеют аддитивный (линейный), а не мультипликативный характер. В [АЛ] приведен пример, который предусматривает выполнения соединения пяти отношений. В этом примере в реализации TR на выполнение этой операции потребовалось 5 с, а в реализации с последовательным просмотром (см. главу 18) потребовалось бы свыше 3 млрд. лет, или время, превышающее примерно в 200 раз возраст Вселенной (!).

■     Чем больше отношений участвуют в операции соединения, тем больше выигрыш.  Иными словами, чем сложнее запрос, тем более значительными становятся преимущества системы, основанной на модели TR, над системами с непосредственным отображением.

■     Поскольку все соединения реализуются одинаковым способом, нет необходимости выполнять сложный процесс выбора пути доступа, который является обязательным в системах с непосред ственным отображением.

■     Более  того,  указанный  процесс  выбора  пути  доступа,  который  приходится  выполнять  в системах с непосредственным доступом, в любом случае имеет  сомнительную точность (кроме всего прочего) из-за сложности оценки размеров промежуточных результатов.

Объединение, пересечение и разность

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

Теперь рассмотрим операцию в следующей форме.

X   {   CITY   }   op   Y   {   CITY   }

Здесь X — переменная отношения S или Р, Y — другая из этих двух переменных отношения, а ор — операция UNION, INTERSECT или MINUS. Метод использования слившегося столбца CITY  в таблице значений полей при реализации таких операций должен быть очевидным. По сути,  он должен быть таким, как описано ниже.

■     UNION. Каждое конкретное название города появляется в результате тогда и только тогда, когда имеется непустой диапазон строк для поставщиков или деталей, или тех и других. Иными словами, объединение — это просто множество всех названий городов в слившемся столбце.

■     INTERSECT. Каждое конкретное название города появляется в результате тогда и только тогда,

когда имеется непустой диапазон строк и для поставщиков, и для деталей.

■     MINUS. Если переменной отношения X является S, то каждое конкретное название города появляется в результате тогда и только тогда, когда имеется непустой  диапазон строк для

поставщиков и пустой— для деталей. Аналогичным образом, если переменной отношения X

‘    является Р, то каждое конкретное название города появляется в результате тогда и только тогда,

когда имеется непустой диапазон строк для деталей и пустой — для поставщиков.

Очевидно, что все эти операции могут быть реализованы за один проход по столбцу CITY слившейся таблицы значений полей.

Заключительные замечания

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

■     В реализациях с непосредственным отображением иногда возникает необходимость материали зовать промежуточные результирующие отношения. Такая же необходимость возникает и при использовании  модели  TR,   но  при   этом  указанная   материализация,    во-первых,   обычно требуется менее часто и, во-вторых, является более эффективной в случае ее вынужденного выполнения (в основном благодаря всей предварительной сортировке).

■     В модели TR могут быть очень эффективно реализованы ограничения потенциального ключа (уникальности) и внешнего ключа (ссылочной целостности) благодаря тому, что таблицы значений полей обычно являются одновременно и сжатыми, и слившимися.

■     Ниже приведена цитата из самой первой статьи Кодда, посвященной реляционной модели [6.1].

Зная о том, что существует определенное отношение,  пользователь будет рассчитыватъ  на то, что у него есть возможность эксплуатировать это отношение  с использованием любой комбинации его атрибутов как "известного", а оставшихся атрибутов как  "неизвестного", поскольку информация, даже если она не видна, все равно присутствует в этом отношении  (как не исчезает и Эверест, даже если его нельзя разглядеть за облаками). В этом и состоит одно из свойств реляционной системы (отсутствующее во многих других современных информационных системах), которое мы в дальнейшем будем называть (вполне обоснованно) симметричной эксплуатацией отношений. Но, вполне естественно, нельзя рассчитывать на то, что такая же симметрия будет наблюдаться и в части производительности.

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

РЕЗЮМЕ

В этой главе кратко описана модель TR, представляющая собой принципиально новый подход к  реализации реляционных СУБД. Модель TR представляет собой конкретное приложение более общей технологии, известной под названием метода преобразования Тарена, который предназначен для использования в качестве технологии реализации систем хранения и выборки данных многих типов (а не только СУБД). Метод преобразования Тарена является объектом действия патента США [А.2] и интеллектуальной собственностью  компании Required Technologies, Inc. (http: /

/www. requiredtech. com).

В данной главе было показано применение модели TR для баз данных, предназначенных только для чтения и находящихся в оперативной памяти. Хотя приведенное здесь описание, к сожалению, не могло не оказаться весьма поверхностным, автор надеется, что оно было достаточным для того, чтобы показать, насколько значительно модель TR отличается от обычной технологии с непосредственным отображением. Вместе с тем, автор не сомневается в том, что у читателя возникло много вопросов. Ниже приведены наиболее характерные вопросы, на которые нельзя найти ответ в данном приложении.

■     Можно ли обеспечить эффективное сопровождение таблиц значений полей и реконструкции записей в условиях применения к базе данных произвольных операций обновления?

■     Поскольку таблица реконструкции записей изоморфна первоначальному файлу (по  сути, первоначальному отношению), но в каждой ячейке вместо значения данных содержит указатель, разве модель TR не потребует гораздо больше памяти по сравнению с той обычной реализацией, в которой применяется непосредственное отображение?

■     Разве не следует ожидать, что в системе с хранимой на диске информацией зигзагообразное обращение к таблицам потребует большого количества операций произвольного доступа и повлечет за собой резкое снижение производительности? И можно ли добиться эффективного осуществления бинарного поиска на диске?

Подобные вопросы, безусловно, являются очень серьезными, но (к сожалению) в данной книге не предусмотрен дополнительный объем для их освещения; достаточно сказать, что они могли быть и были успешно решены, а эти решения реализованы. Дополнительная информация приведена в [АЛ] и [А.2].

СПИСОК ЛИТЕРАТУРЫ

АЛ.                                        Date С. J. Go Faster! The TransRelational™ Approach to DBMS Implementation // Готовится к выходу.

Настоящее приложение в значительной степени основано на данной книге, но в ней приведено намного больше подробностей и описаны многие дополнительные темы. В частности, в ней рассматриваются операции обновления и базы данных, хранимые на диске, а также приведены  ответы на вопросы, которые были подняты в разделе А.7.

А.2.                                        U.S. Patent and Trademark Office: Value-lnstance-Connectivity ComputerImplemented Database. U.S. Patent No. 6,009,432. December 28, 1999.

Это — оригинальный патент по методу преобразования Тарена; данный  метод является интеллектуальной собственностью компании Required  Technologies, Inc.   (http:   //www.   requiredtech.com).   Но   следует    отметить,   что   метод преобразования   Тарена   в   значительной   степени   расширен,   и   вышел  за пределы того, что было описано в этом оригинальном патенте. В частности, он теперь  охватывает  целый  ряд  методов  обновления  и  способов  организации работы  с  базами  данных   на  диске  (см.  [А.1]).  Кроме  того,  заслуживает внимания   само    название   этого   источника:   оригинальный    патент    был сформулирован  в  терминах  (кроме  всего  прочего)  того,  что  в  нем   было названо   хранилищами   значений,  хранилищами  экземпляров  и   хранилищами связности.   В   отличие   от   этого,   в   настоящем    приложении   и   в   [АЛ) используются   такие   термины,   как   таблицы   значений   полей   и   таблицы реконструкции записей, в надежде на то, что эти последние термины являются более удобными для пользователя в определенных аспектах и лучше передают суть происходящих действий.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии