СТИСЛІ СТ ОЛ Б Ц И TransRelational

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

Тепер слід зазначити, що таблиця значень полів, показана на рис А9, містить значні ний обсяг надлишкової інформації, наприклад, назва міста London зявляється в ній три рази, вага

17 0 – два рази і тд Стиснення стовпців цієї таблиці дозволяє просто усунути зазначену надмірність Тому результат стає таким, що кожен стовпець містить тільки відповідні помітні значення, як показано на рис А 11 Зі сказаного випливають наведені нижче висновки

Рис А8 Варіант файлу для звичайно застосовуваного відносини деталей

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

Рис А 11 Стиснута версія таблиці значень полів, відповідна таблиці,

Рис А9 Таблиця значень полів, відповідна файлу на рис А8

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

показаної на рис А9

1 Припустимо і навіть бажано передбачити вибіркове застосування процесу стиснення У част ності, немає сенсу виконувати стиснення стовпця р #, оскільки номери деталей є уникаль вими

2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Значення полів в стислих стовпцях фактично використовуються спільно в різних записах файлу деталей Наприклад, імя міста 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]. Цей діапазон рядків означає, що якщо буде потрібно скасувати стиснення таблиці значень полів, тобто відновити її в первісному вигляді, то значення ваги 170 зявиться (Зрозуміло, в стовпці 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 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*