Главная » SQL, Базы данных » СЖАТЫЕ СТ ОЛ Б Ц Ы TransRelational

0

Рассмотрим рис. А.8, на  котором показан возможный вариант файла, соответствующего  обычно применяемому в  этой книге отношению деталей, рис. А.9, на  котором приведена  соответствующая таблица  значений  полей,  и  рис.  А.10,  где  показана  соответствующая   "предпочтительная"  таблица реконструкции записей.

Теперь следует отметить, что таблица значений полей, показанная на рис. А.9, содержит значитель ный объем избыточной информации, например, название города London появляется в ней три раза, вес

17 . 0 — два раза и т.д. Сжатие столбцов этой таблицы позволяет просто устранить указанную избыточность. Поэтому результат становится таким, что каждый столбец содержит только соответствующие различимые значения, как показано на рис. А. 11. Из сказанного следуют приведенные ниже выводы.

Рис. А.8. Вариант файла для обычно применяемого отношения деталей

2  Аналогичное утверждение справедливо и по отношению к перестановке STATUS, но, как оказалось, не относится к перестановке SNAME (а также, безусловно, к перестановке S#).

Рис. А. 11. Сжатая версия таблицы значений полей, соответствующая таблице,

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

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

показанной на рис. А.9

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

2.                  Значения полей в сжатых столбцах фактически используются совместно в разных записях файла деталей. Например, имя города London в ячейке [1, 5 ] используется в трех записях с данными о деталях, а именно с данными о деталях Р1, Р4 и Р6. Одним из следствий этого является возможность быстрее выполнять операции обновления, особенно INSERT, поскольку в них можно ис

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

произойдет, если пользователь вставит кортеж с данными о детали Р7, имеющей название  Nut,

цвет Red, вес 18 . О, город London. Но, как было указано в разделе АЛ, в целом операции  обновления выходят за рамки данного приложения.

3.             Сжатые столбцы, безусловно, становятся своего рода основой метода сжатия данных (причем та кого метода, который, как правило, не встречается в обычных реализациях с непосредственным

отображением), но  заслуживает внимания то,  насколько эффективное сжатие  они  позволяют обеспечить. Например, предположим, что в Министерстве автотранспорта  штата используется отношение с данными о водительских правах, где находится по  одному кортежу с данными о правах каждого водителя, выданных (скажем) в штате  Калифорния, причем общее количество таких кортежей составляет около 20 млн. Но, безусловно, количество различных значений веса, роста, цвета волос водителей, а также значений срока действия этих прав не составляет 20 млн! Иными словами, коэффициент сжатия иногда может достигать порядка одного к миллиону или примерно такого значения.

Диапазоны строк

Вернемся к анализу рис. А. 11. Вне всякого сомнения, нельзя просто заменить (например) три первоначальных вхождений названия города London только одним таким вхождением,  поскольку подобное решение привело бы к потере информации. (Сжатый столбец CITY содержит три значения, а количество деталей равно шести. Как в таком случае узнать, в каком городе находится та или иная деталь?) Поэтому необходимо  хранить  некоторую  дополнительную   информацию,  которая,  по   существу,  позволяет реконструировать первоначальную, несжатую  таблицу значений полей из ее сжатого аналога. Один из способов решения этой задачи состоит в  том, что наряду с каждым значением поля в каждом сжатом столбце таблицы значений полей  необходимо хранить данные о диапазоне номеров строк3  в несжатой версии этой таблицы, в  которых первоначально находилось это значение, как показано на рис. А.12. Например,  рассмотрим ячейку [3, 4 ]  на этом рисунке, которая содержит значение веса 17. 0. Рядом с этим  значением  веса  показан  диапазон  строк  "[4 :5 ]".  Этот  диапазон  строк  означает,  что  если потребуется отменить "сжатие" таблицы значений полей, т.е. восстановить ее в первоначальном  виде, то значение  веса  17.0  появится  (разумеется, в  столбце  WEIGHT,  т.е.  в  столбце  4)  в  строках  4  и  5, включительно, как в той таблице, какой она была до сжатия.

Рис. А.12. Сжатая таблица значений полей с указанием диапазонов строк

Кстати, не следует путать спецификацию в форме [4 :5] со спецификацией [4, 5 ] . Первая из них (с разделителем в виде двоеточия) обозначает определенный диапазон номеров строк, как  было описано выше, а последняя (с разделителем в виде запятой) — это индекс, обозначающий  конкретную ячейку, которая находится на пересечении указанных в этом индексе строки и столбца.

В  отношении  диапазонов  номеров  строк  необходимо  сделать  еще  одно  замечание.  Рассмотрим (например) столбец 3 (столбец COLOR) в таблице значений полей, приведенной на рис. А.12. Очевидно, что в этом столбце указано именно следующее: во-первых, множество  значений COLOR, которые в настоящее  время  присутствуют  в  файле  деталей,  и  наряду   с   этим,  во-вторых,  для  каждого такого

3   Автор  намеренно  выбрал  для  обозначения  диапазонов  строк  на  этом  рисунке  такой  же  формат,  как  и  для интервалов в главе 23, но нельзя отрицать, что информация о диапазоне строк может быть  физически представлена с помощью   многих   других,   отличных   от   этого   способов.   Один   из   способов   может   предусматривать   хранение информации  только  о  начале  или  только  о  конце  диапазона.  Еще  один  способ  может состоять в том, что вместо обозначений  начала  и  конца  диапазона  может  быть  указано  количество  строк  в  диапазоне.  Существуют  и  другие способы.

значения — количество случаев появления этого значения в заданном файле. Иными

словами, данный столбец может рассматриваться как гистограмма (рис. А. 13). В действительности, вообще говоря, вся сжатая таблица значений полей со своими диапазонами номеров строк может с очень большой пользой для дела рассматриваться как множество гистограмм, по одной для каждого сжатого столбца. Одним из следствий из указанного факта является то, что должна быть весьма высокой производительность тех запросов, которые концептуально требуют применения подобных гистограмм (таковым является, например, запрос: "Сколько имеется деталей каждого цвета?"). См. раздел А.6.

Приведем еще  одно  короткое замечание на  ту  же  тему: если таблица значений  полей может рассматриваться как множество гистограмм, то и таблица реконструкции записей (как уже было сказано в предыдущем разделе) может фактически  рассматриваться как множество перестановок. Например, после реконструкции файла  деталей с использованием столбца 3 таблицы  реконструкции  записей,  показанной  на  рис.  АЛО,  будет  получена  версия  файла, отсортированная по цвету деталей; иными  словами, будет получено то, что можно было бы назвать "перестановкой COLOR" этого файла. Поэтому представление с помощью модели TR любого конкретного набора  данных можно неформально охарактеризовать как множество гистограмм  в   сочетании   с  множеством  перестановок  (рассматриваемых  данных).  Такие гистограммы и перестановки, по сути, составляют все, что лежит в основе  представления данных в модели TR.

Рис. А. 13. Гистограмма цветов (основанная на данных рис. А. 12)

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

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

В   качестве  примера   рассмотрим  ячейку   [3 ,4]   таблицы   реконструкции   записей, приведенной на рис. АЛО, которая присутствует (безусловно) в столбце 4 (столбце WEIGHT) этой  таблицы.  Чтобы  найти  соответствующее  значение  веса  в   таблице  значений  полей, показанной на рис. А.11, выполним поиск в столбце WEIGHT этой таблицы и найдем в этом столбце уникальную запись, содержащую диапазон строк, в который входит строка 3. Данный рисунок  показывает, что  рассматриваемым элементом является ячейка [2 ,4]  (притом  что соответствующим  диапазоном строк является [3 :3 ]) ,  а требуемое значение веса равно 14 . 0. В качестве упражнения воспользуйтесь приведенной на рис. АЛО таблицей реконструкции записей  наряду со сжатой таблицей значений полей на рис. А. 12 для полной реконструкции файла   деталей   (начните   со   столбца   5,   чтобы   получить   результат   по    возрастанию последовательности лексикографических значений названий городов).

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

По теме:

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