ОСНОВНА ІДЕЯ TransRelational

Найбільш важлива думка, що лежить в основі моделі 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 SS#, SSNAME, SSTATUS, SCITY FROM S

ORDER BY St

Аналогічним чином, для реалізації наведеного нижче запиту досить виконати обробку шпальти таблиці значень полів з номерами постачальників в зворотному порядку і провести операції реконструкції, починаючи з клітинки [5, 1], потім [4, 1] і тд

SELECT SS#, SSNAME, SSTATUS, SCITY FROM S

ORDER BY Sf DESC

Причому і в тому, і в іншому випадку не потрібно ні виконувати сортування на етапі прогону, ні використовувати індекс

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

можна входити в ці кільця в будь-якій точці Тому процес застосування алгоритму реконструкції можна починати з будь необхідної комірки Наприклад, якщо почати з осередку [1, 3] (тобто з першої клітинки у стовпці STATUS), то буде отримана наступна запис

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

SELECT SSTATUS, SCITY, SS#, SSNAME FROM S

ORDER BY STATUS

Аналогічним чином, обробка таблиці реконструкції записів у порядку значень покажчиків в стовпці SNAME дозволяє отримати файл постачальників, відсортований за зростанням лексикографічних значень імен постачальників, а обробка цієї таблиці в порядку значень покажчиків в стовпці CITY – файл, відсортований за зростанням лексикографічних значень назв

міст Іншими словами, при спільному використанні таблиця реконструкції записів і таблиця значень полів служать одночасно представниками всіх цих способів упорядкування при цьому (Ще раз повторюємо) не виникає необхідність ні у використанні індексів, ні у виконанні сортування на етапі прогону

Тепер розглянемо наступний запит, який вимагає виконання операції скорочення з перевіркою на рівність

SELECT SS#, SSNAME, SSTATUS, SCITY FROM S

WHERE SCITY = 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 с: Ил – Парал тит англ

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


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

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

Ваш отзыв

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

*

*