Главная » SQL, Базы данных » ОСНОВНАЯ ИДЕЯ TransRelational

0

Наиболее важная мысль, лежащая в основе модели TR, может быть описана следующим образом. Допустим, что

r — запись некоторого файла на файловом уровне. В таком случае справедливо приведенное ниже утверждение.

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

Таблица значений полей

Итак, читатель, по-видимому, уже определил самостоятельно, как была получена  приведенная на рис. А.4 таблица значений полей из файла, который показан на рис. А.З:  фактически каждый столбец таблицы содержит значения из соответствующего поля файла, отсортированные в порядке возрастания. Поэтому следует сразу же отметить, что независимо от первоначального расположения записей в файле всегда формируется одна и та же таблица значений полей (в рассматриваемом примере на одну и ту же таблицу значений полей отображаются все 2880 версий файла). Кроме того, даже несмотря на то, что мы еще  не  имеем  возможности  описать,  как  используется  эта  таблица  (поскольку  вначале  требуется рассмотреть таблицу реконструкции записей), можно сразу же подчеркнуть несколько  приведенных ниже особенностей, позволяющих проще понять ее назначение.

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

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

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

■        Запросы, требующие поиска конкретного значения (например, запрос на получение номеров поставщиков из Лондона) может быть реализован с помощью эффективного бинарного поиска. И аналогичные замечания снова касаются каждого атрибута.

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

Таблица реконструкции записей

На рис. А.6 таблица значений полей (которая была показана на рис. А.4) находится  рядом с таблицей реконструкции записей, приведенной на рис. А.5. Следует отметить, что  эти  две таблицы являются изоморфными; в действительности, как вскоре будет показано,  существует непосредственное взаимно однозначное соответствие между ячейками этих двух таблиц (т.е. обе эти таблицы имеют такое же количество строк и столбцов, сколько записей и полей, соответственно, имеется в файле на рис. А.З). Заслуживает  также  внимания  следующее  —  как  указано  в  разделе  А.2,  данные  в  ячейках  таблицы реконструкции записей не  представляют  собой больше номера поставщиков, имена поставщиков (или другую фактическую  информацию); вместо этого они представляют собой номера строк, а эти номера строк  могут   рассматриваться  как  указатели  на  строки  таблицы  значений  полей  или  таблицы реконструкции записей или той и другой таблицы, в зависимости от контекста, в котором  указатели используются. (По этой причине фактически столбцы в таблице реконструкции записей не обязательно должны были обозначаться надписями S#, SNAME и т.д., как показано на этом  рисунке; тем не менее, применение таких надписей позволит проще следить за некоторыми дальнейшими описаниями.)

Прежде чем приступить к рассмотрению того, как формируется таблица реконструкции  записей,

кратко опишем, как она используется. Рассмотрим приведенную ниже последовательность операций.

Рис. А.6. Таблица значений полей, показанная на рис. А.4, и соответствующая таблица реконструкции записей

Шаг  1.  Перейти в  ячейку  [1,1]  таблицы  значений полей  и  считать хранящееся  здесь значение, а именно номер поставщика S1. Это значение является первым значением поля (т.е. значением поля S#) в некоторой записи с данными о поставщике в файле поставщиков.

Шаг 2. Перейти в ту же ячейку (т.е. в ячейку [1,1]) таблицы реконструкции  записей и считать  хранящееся  в  ней  значение,  а  именно  номер  строки  5.  Этот   номер  строки

интерпретируется как  означающий, что значение следующего поля (которое  представляет собой значение второго поля, или значение поля SNAME) в записи  поставщика, значение поля  S#  в  которой  равно  S1,  можно  найти  в  позиции   SNAME  пятой  строки  таблицы значений полей, иными словами, в ячейке [5,2]  таблицы значений полей. Перейти в эту ячейку и считать хранящееся там значение (имя поставщика Smith).

Шаг 3. Перейти в  соответствующую ячейку таблицы реконструкции записей [5,2 ]  и

считать хранящийся в ней номер строки (3). Значение следующего поля (третьего  поля,  или поля STATUS) в реконструируемой записи поставщика находится в позиции STATUS третьей строки таблицы значений полей, иными словами, в ячейке [3,3] .  Перейти в эту ячейку и считать хранящееся в ней значение (статус 20).

Шаг  4.  Перейти  в  соответствующую  ячейку  таблицы  реконструкции  записей  [3,3 ]  и считать  хранящееся  в  ней  значение  (которое  снова  равно  3).  Значение  следующего  поля

(четвертого  поля,  или  поля  CITY)  реконструируемой  записи  поставщика   находится  в позиции CITY третьей строки таблицы значений полей, иными  словами,  в ячейке [3,4] . Перейти в эту ячейку и считать хранящееся в ней значение (название города London).

Шаг  5.  Перейти  в  соответствующую  ячейку  таблицы  реконструкции  записей  [3,4 ]  и считать хранящееся в  ней  значение  (1).  Теперь  на  первый  взгляд  может  показаться, что значением  "следующего"  поля   в   реконструируемой  записи   поставщика  должно  быть

значение  пятого  столбца,  но  записи  поставщиков  имеют  только  четыре  поля,  поэтому "пятое" поле замыкает цикл и становится первым. Таким образом, значение  "следующего" поля  (первого  поля,  или  поля  S#)  в  реконструируемой  записи   поставщика  находится  в позиции S# первой строки таблицы значений полей, иными  словами, в ячейке [1,1 ]. Но с этого значения и началось считывание записи, поэтому весь процесс останавливается.

Безусловно,    что    приведенная    выше    последовательность    операций    приводит     к

реконструкции  одной  конкретной  записи  из  файла  поставщиков,  а  именно  той  записи,

которая показана под номером 4 на рис. А.З:

Кстати, следует отметить, что указатели номеров строк, по  которым мы  переходили в приведенном выше  примере,  образуют  кольцо,  а  фактически  образуют  два  изоморфных кольца  —  одно  из  них  находится  в  таблице  значений   полей,  а  другое  —  в  таблице реконструкции записей (рис. А.7).

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

Рис. А.7. Кольца указателей (примеры)

В качестве упражнения попытайтесь сами реконструировать еще одну запись с данными поставщика. Если вы начнете с ячейки [2,1] таблицы значений полей, то получите запись 3 файла, показанного на рис. А.З. Аналогичным образом, начав с ячейки [3, 1 ] , можно получить запись 5, начав с ячейки [4, 1 ] — запись 1, а начав с ячейки [5, 1 ] — запись 2. Здесь заслуживает внимания  то, в чем состоит суммарный эффект: если  обработка  всей  таблицы  значений  полей  осуществляется  в  последовательности номеров  поставщиков  путем  прохождения сверху  вниз  по  столбцу  S#  (т.е.  если  процесс  реконструкции записи выполняется  пять  раз,  начиная  последовательно  с  ячеек  [1,1],  [ 2 , 1 ] ,  [ 3 , 1 ],  [4, 1 ]  и  [5 , 1 ] ) ,  то происходит реконструкция  той версии всего файла поставщиков, в которой записи присутствуют в порядке возрастания номеров поставщиков. Иными словами, при этом реализуется следующий запрос SQL.

SELECT S.S#, S.SNAME, S.STATUS, S.CITY FROM S

ORDER BY St ;

Аналогичным образом, для реализации приведенного ниже запроса достаточно выполнить  обработку  столбца таблицы значений полей  с  номерами поставщиков в  обратном порядке  и  провести операции реконструкции, начиная с ячейки [5, 1 ] , затем [4, 1 ] и т.д.

SELECT S.S#, S.SNAME, S.STATUS, S.CITY FROM S

ORDER BY Sf DESC ;

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

Более того, именно в связи с тем, что указатели в таблице реконструкции записей образуют кольца,

можно входить в эти кольца в любой точке. Поэтому процесс применения алгоритма  реконструкции можно начинать с любой требуемой ячейки. Например, если начать с ячейки  [1, 3 ]  (т.е. с первой ячейки в столбце STATUS), то будет получена следующая запись.

(Точнее, будет получена та версия этой записи, в которой упорядочением полей слева  направо является STATUS, затем CITY, затем S#, затем SNAME.) Следуя вниз по столбцу  STATUS (т.е. последовательно продолжая процесс реконструкции с применением ячеек [ 2 ,3 ] ,  [3 ,3 ],  [ 4 , 3 ]  и [5, 3 ] ) можно в конечном итоге получить весь файл поставщиков в порядке возрастания статуса.

SELECT S.STATUS, S.CITY, S.S#, S.SNAME FROM S

ORDER BY STATUS ;

Аналогичным образом, обработка таблицы реконструкции записей в порядке значений указателей в столбце SNAME позволяет получить файл поставщиков, отсортированный по  возрастанию лексикографических значений имен поставщиков, а обработка этой таблицы в  порядке значений указателей в столбце CITY — файл, отсортированный  по  возрастанию лексикографических значений  названий

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

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

SELECT S.S#, S.SNAME, S.STATUS, S.CITY FROM S

WHERE S.CITY = ‘London’ ;

Поскольку  столбец  CITY  (как  и  все  столбцы)  в  таблице  значений  полей  хранится  в отсортированном  порядке,  то  для  поиска  ячеек,  содержащих  значение   London,  может применяться бинарный поиск. Если рассматривается таблица значений  полей, приведенная на  рис.  А.6,  то  такими  ячейками  являются  [2, 4 ]  и  [3 ,4 ].  Теперь можно сформировать зигзаги, следуя по  кольцам указателей, проходящим  через  ячейки [2,4]  и  [3,4]  таблицы реконструкции записей. В данном примере указанные зигзаги выглядят следующим образом.

[ 2 , 4 ] ,     [ 4 , 1 ] ,     [ 3 , 2 ] ,     [ 2 , 3 ]   И

[ 3 , 4 ] ,     [1 , 1 ],                                         [ 5 , 2 ] ,                                          [ 3 , 3 ]

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

При  совместном  использовании  таблица  значений  полей  и  таблица   реконструкции записей   предоставляют   также   непосредственную   поддержку   многих   других   операций пользовательского  уровня,  а  не  только  поддержку   простых  запросов  с  конструкциями ORDER  BY  и  операциями  сокращения  с   проверкой  на  равенство.  В  действительности, основная   часть   или   даже   все   фундаментальные   реляционные   операции   (сокращение, проекция,   соединение,    агрегирование   и   др.,   не   говоря   уже   об   операции   удаления дубликатов,  необходимость в использовании которой на промежуточных этапах возникает всегда,  даже в истинно реляционных системах) имеют алгоритмы реализации, основанные на способности  получать  доступ  к  данным  в  некоторой  конкретной   последовательности.   В качестве примера рассмотрим операцию соединения. В главе 18  было сказано, что удобным способом  реализации  соединения  является  сортировка—слияние.  А  модель  TR  позволяет выполнять соединения по методу сортировки-слияния без необходимости выполнения самой сортировки! (Или, по  меньшей мере, без необходимости выполнять сортировку  на  этапе прогона,   поскольку  сортировка  осуществляется  при  формировании  таблиц  значений полей  и реконструкции записей, иными словами, неформально можно утверждать,  что  она выполняется на этапе загрузки данных.) Например, для соединения отношений поставщиков и  деталей  по   названиям  городов  достаточно  просто  обратиться  к   каждой  из   двух соответствующих   таблиц   значений  полей   в   порядке   названий   городов   и   выполнить соединение в стиле операции слияния.

Одним важным следствием из всего сказанного является то, что работа  оптимизатора системы  намного  упрощается, а  именно,  гораздо  проще  становится  процесс  выбора  пути доступа  (см.  главу  18),  а  в  некоторых  случаях   необходимость  в  его  использовании полностью исключается. Еще одним  следствием является то, что становятся ненужными также  многие  из   вспомогательных  структур  (индексы,  хэши  и  т.д.),  применяемых  в традиционных    СУБД.   Наконец,   важным   следствием   становится   то,   что   физическое проектирование  базы  данных  значительно  упрощается  в  связи  с  тем,  что   количество различных опций и вариантов выбора структур данных становится намного меньше; то же самое касается и настройки производительности.

Формирование таблицы реконструкции записей

Рассмотрим   результаты   применения   различных   вариантов   упорядочения   с помощью сортировки к файлу, показанному на рис. А.З. Например, предположим, что была выполнена его сортировка в порядке возрастания номеров поставщиков, а затем   получены   записи   в    последовательности   4,   3,   5,   1,   2.   Назовем   эту последовательность                                         "перестановкой,                                        соответствующей                                        упорядочению                                        с возрастанием  атрибута S#" (или сокращенно перестановкой S#). Другие варианты перестановки показаны ниже.

■        По возрастанию значения SNAME: 2,5,1,3,4.

■        По возрастанию значения STATUS: 3, 1, 4,2,5.

■        По возрастанию значения CITY: 2, 1,4, 3, 5.

Итоговые  данные  по  этим  перестановкам  приведены  в  следующей   таблице перестановок, в которой ячейка [i,  j ] содержит номер в файле  поставщиков той записи,   которая   присутствует   в   i-й   позиции,   если    файл   отсортирован   по возрастанию значений в j-м поле.

Как показывает эта таблица, перестановка S# (еще раз повторяем) представляет собой следующую последовательность. 4,    3,    5,    1,    2 Обратной по отношению к этой перестановке является следующая последовательность.

4,    5,    2,    1,    3

Эта  обратная  перестановка  является  такой уникальной  перестановкой,  которая после ее применения к первоначальной последовательности 4, 3, 5, 1 , 2 приводит к получению  последовательности  1,  2,  3,  4,  5.  (Если   SEQ   —   первоначальная последовательность 4, 3, 5, 1, 2, то четвертым  элементом в последовательности SEQ  является  элемент  1,  пятым—  2,  вторым—  3  и  т.д.)  Вообще  говоря,  если рассматривать    любую    заданную    перестановку    как   вектор    V,    то    обратная перестановка V может быть  получена  в  соответствии  с  простым  правилом,  что если V[ i)  = i 1 , то V [ i 1 ]  = i. Применяя это правило к каждой из перестановок в

6 Теперь можно приступить к формированию таблицы реконструкции записей. Например, первый столбец (s#) можно сформировать, как описано ниже. приведенной выше таблице перестановок, получим следующую  таблицу  обратных перестановок.

Выполнение этого алгоритма для i = 1, 2, . . . ,  5 позволяет получить весь столбец  S#

таблицы реконструкции записей. Другие столбцы формируются аналогичным образом.

Примечание. Настоятельно  рекомендуем читателю  в  качестве  упражнения  проработать

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

такого  упражнения  позволяет  получить  ключ  к  пониманию  работы  алгоритма.   Кстати,

следует  отметить,  что  таблица  реконструкции  записей  формируется  исключительно   на

основании файла,  поскольку  в  этом  процессе  таблица  значений  полей  вообще  не  играет

никакой роли.

Неуникальная таблица реконструкции записей

В предыдущем подразделе (кроме всего прочего) было сказано, что перестановка CITY для  файла поставщиков, приведенного на рис. А.З, имела последовательность 2, 1, 4, 3, 5. Но из  того, что и поставщик S1, и поставщик S4 находятся в одном и том же городе, так же, как и поставщики S2 и S3, следует, что можно было бы с такой же уверенностью утверждать, что перестановкой по атрибуту CITY была последовательность 2,4,1,3,5, илиЗ, 1, 4, 2, 5, или 3, 4, 1, 2, 5. Иными словами, перестановка CITY не является уникальной2. Из этого следует, что таблица  перестановок не уникальна и поэтому также не уникальна и таблица реконструкции записей. Но оказалось, что применительно к каждому конкретному отношению пользовательского уровня  всегда имеются определенные таблицы реконструкции записей, являющиеся "предпочтительными", в том смысле, что они обладают некоторыми желательными свойствами,  которых  другие  таблицы  реконструкции  записей  не  имеют.  Но  подробные  сведения  об  этих особенностях выходят за рамки настоящего приложения; дополнительная информация приведена в [А. 1].

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

По теме:

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