РЕАЛІЗАЦІЯ Реляційних ОПЕРАТОРІВ TransRelational

У даному розділі коротко описано, які слідства повязані із застосуванням моделі 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 Relationalm1193 розглянутому випадку пошук призводить до виявлення осередку [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 &lt 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 можуть бути дуже ефективно реалізовані обмеження потенційного ключа (унікальності) і зовнішнього ключа (посилальної цілісності) завдяки тому, що таблиці значень полів зазвичай є одночасно і стислими, і слившимися

■ Нижче наведена цитата з самої першої статті Кодда, присвяченій реляційної моделі [61]

Знаючи про те, що існує певне ставлення, користувач буде рассчітиват на те, що у нього є можливість експлуатувати це відношення з використанням будь-якої комбінації його атрибутів як Відомого, а що залишилися атрибутів як невідомого, оскільки інформація, навіть якщо вона не видна, все одно присутній в цьому відношенні (як жевріє і Еверест, навіть якщо його не можна розгледіти за хмарами) У цьому і полягає одна з властивостей реляційної системи (відсутнє в багатьох інших сучасних інформаційних системах), яке ми надалі будемо називати (цілком обгрунтовано) симетричною експлуатацією відносин Але, цілком природно, не можна розраховувати на те, що така ж симетрія буде спостерігатися і в частині продуктивності

Але модель 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 US Patent and Trademark Office: Value-lnstance-Connectivity ComputerImplemented Database US Patent No 6,009,432 December 28, 1999

Це – оригінальний патент за методом перетворення тарена даний метод є інтелектуальною власністю компанії Required Technologies, Inc (Http://www Requiredtechcom) Але слід відзначити, що метод перетворення тарена в значній мірі розширений, і вийшов за межі того, що було описано в цьому оригінальному патенті Зокрема, він тепер охоплює цілий ряд методів оновлення і способів організації роботи з базами даних на диску (див [А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>

*

*