УПАКОВКА І РОЗПАКОВУВАННЯ ВІДНОСИН

У даному розділі розглядаються два нових (і надзвичайно важливих) реляційних оператора, званих PACK і UNPACK Але в якості проміжного етапу на шляху до визначення цих операторів спочатку необхідно зробити короткий відступ і розглянути два простіших їх аналога, які називаються, відповідно, COLLAPSE і EXPAND Крім того, для спрощення викладу ці останні оператори будуть описані в зворотному порядку

Оператори EXPAND і COLLAPSE

Обидва оператора, EXPAND І COLLAPSE, в тому вигляді, в якому вони описані в цьому разделе7, приймають в якості єдиного операнда унарное ставлення, кортежі якого містять інтервали, і виробляють в якості результату інше ставлення такого ж типу Наприклад, припустимо, що ставлення r виглядає приблизно таким чином

У такому випадку оператори EXPAND Г І COLLAPSE r виробляють результати, які виглядають наступним чином

7 Більш загальні версії цих операторів описані в [234]

Пояснення Припустимо, що унарное ставлення r включає DURING в якості єдиного атрибута, a DURING має значення у вигляді інтервалу Тоді і розгорнута, і згорнута форми ставлення r є унарними відносинами такого ж типу, як r, які визначені, як описано нижче

Розгорнутою формою є таке ставлення rх, містить всі кортежі (і лише такі кортежі), які містять одиничний інтервал у формі [р: р], де р – позиція в деякому інтервалі з деякого кортежу r, певного, як показано нижче

Стислій формою ставлення r є ставлення rс, таке що мають місце описані нижче умови

а) Відносини r і rс мають одну і ту ж розгорнуту форму

б) Ніякі два різних кортежу відносно rс не містять інтервали il і i2, відповідно, такі що вираз il MERGES i2 є істинним Рав ним чином, ніякі два різних кортежу відносно rс не містять, відпо відно, інтервали il і i2, такі що визначено вираз il UNION i2 (З цього випливає, що ставлення rс може бути обчислено з відношення r шляхом послідовної заміни пар кортежів tl і t2 відносно r за допомогою на щью кортежу t, що містить обєднання інтервалів в кортежі tl і t2, до тих пір, поки такі заміни більше не будуть можливі)

Тепер розглянемо ці ідеї більш докладно Для спрощення в решті частини даного підрозділу передбачається, що єдиними розглянутими тут відносинами є саме унарні відносини, в яких кортежі містять інтервали Тому нижче наведено визначення важливого поняття еквівалентності таких відносин

■ Два відносини, rl і r2, є еквівалентними тоді і тільки тоді, коли безліч всіх позицій, що містяться в інтервалах кортежів відносини rl, одно безлічі всіх позицій, що містяться в інтервалах кортежів r2

Після аналізу цього і наведених раніше визначень розгорнутих і згорнутих форм стають очевидними наведені нижче висновки

■ Для будь-якого конкретного відношення r завжди існує відповідна развер нутая форма цього відношення r

■ Така розгорнута форма еквівалентна відношенню r Дійсно, можна стверджувати, що два відносини є еквівалентними тоді і тільки тоді, коли вони мають однакову розгорнуту форму

■ Така розгорнута форма є унікальною точніше, розгорнута форма пред ставлять собою таке унікальне еквівалентне ставлення, в якому всі інтер вали мають мінімально можливу довжину (одиничну довжину)

■ Інтуїтивно ясно, що розгорнута форма ставлення r дозволяє нам займатися аналізом інформаційного наповнення відносини r на елементарні му рівні, не турбуючись про те, що може існувати безліч різних способів, за допомогою яких ця інформація могла б бути обєднана в якісь проме жуточние конгломерати.

■ Якщо відношення r є порожнім, то розгорнута форма r також порожня

Аналогічним чином, можна прийти до наведених нижче висновків

■ Для будь-якого даного відношення r завжди існує відповідна згорнута форма ставлення r

■ Така згорнута форма еквівалентна відношенню r Можна фактично утвер чекати, що два відносини є еквівалентними тоді і тільки тоді, коли вони мають одну і ту ж згорнуту форму

■ Така згорнута форма є унікальною точніше, вона являє уникаль ве еквівалентне ставлення, яке має мінімально можливу карди нальность

■ Інтуїтивно ясно, що згорнута форма ставлення r дозволяє нам займатися аналізом інформаційного наповнення відносини r в стислій формі (перед уявлення у вигляді єдиного конгломерату), не турбуючись про те, що існує ймовірність сполучення або перекриття різних конгломератів.

■ Якщо відношення r є порожнім, то згорнута форма ставлення r також порожня

До речі, припущення про те, що оператори EXPAND і COLLAPSE протилежні по відношенню один до одного, є помилковим Фактично, взагалі кажучи, ні вираз EXPAND (COLLAPSE r), ні вираз COLLAPSE (EXPAND r) не є тотожно рівними відношенню r (хоча обидва ці вирази, безумовно, еквівалентні відношенню r) Дійсно, легко показати, що мають місце наведені нижче тотожності

EXPAND ( COLLAPSE r ) ≡  EXPAND r

COLLAPSE ( EXPAND r ) ≡ COLLAPSE r

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

Є EXPAND)

На завершення цього підрозділу наведемо ще два зауваження

■ В [234] показано, що і оператор EXPAND, і оператор COLLAPSE можна визна лити в термінах операторів, які вже передбачені в реляційної алгебри Іншими словами, обидва оператора є просто скороченнями

■ Крім того, в [234] показано, що дуже бажано визначити такі версії операторів EXPAND І COLLAPSE, які працюють з нуль-арнимі, а не з унар вими відносинами Докладний аналіз цього питання тут не наведено, а замість цього зазначимо, що якщо r – нуль-арное ставлення, то вирази EXPAND Г І COLLAPSE r повертають r До того ж визначимо, що два нуль-арних відносини є еквівалентними тоді і тільки тоді, коли вони є рівними

Оператори PACK і UNPACK

У своїй найбільш загальній формі і оператор PACK, і оператор UNPACK приймають в якості єдиного операнда n-арное ставлення, в якому один з атрибутів має значення у вигляді інтервалу і в якості свого результату виробляє інше ставлення такого ж типу Наприклад, припустимо, що ставлення r виглядає приблизно таким чином

У такому разі висловлення PACK r ON DURING і UNPACK r ON DURING виробляють, відповідно, результати, які виглядають наступним чином

Слід зазначити, що неформально кожен з цих результатів представляє таку ж інформацію, що і початкове ставлення r, але характеризується описаними нижче особливостями

■ У разі оператора PACK ця інформація була переупорядкувати таким чином, що ніякі два інтервали DURING, що відносяться до певного постачальника, не є суміжними і не перекриваються

■ У разі оператора UNPACK ця інформація була переупорядкувати таким обра зом, що кожне значення DURING (а значить, в силу цього і кожен окремий інтервал DURING, що відноситься до певного постачальника) являє собою

саме одиничний інтервал Взаємозвязок операторів COLLAPSE і EXPAND з операторами PACK і UNPACK повинна бути інтуїтивно ясною Повинно бути, повідомимо, також очевидно, що початкове ставлення r і відповідні йому упакована і розпаковані форми є в певному сенсі еквівалентними один одному (точний зміст цього твердження буде визначений наприкінці поточного розділу)

Тепер зосередимося саме на вивченні оператора PACK Спочатку розглянемо наведену нижче версію запиту А, переформулювати в термінах бази даних, наведеної на рис 234

■ Запит А Визначити пари S #-DURING для постачальників, які були здатні поставляти щонайменше одну деталь протягом щонайменше одного інтервалу часу, де DURING позначає такий інтервал

Якщо як приклад розглядаються дані, наведені на рис 234, то бажаний результат виглядає наступним чином

Це відношення являє собою упаковану форму деякої проекції змінної відносини SP по атрибуту DURING, а саме проекції по S # і DURING І ми, нарешті, підійшли до того етапу, коли зявилася можливість отримати цей результат за допомогою простого вираження в наступній формі

PACK Tl ON DURING

Тут Tl – зазначена проекція Але для досягнення зазначеної мети необхідно виконати ряд невеликих кроків На першому кроці застосуємо наступний вираз

WITH SP_DURING { S#, DURING } AS Tl :

Це вираз дозволяє отримати необхідну проекцію (насправді, в даному виразі просто відкидаються за допомогою операції проекції номери деталей, які не вимагаються в розглянутому запиті) При використанні значень даних, які звичайно застосовуються як приклад, проекція Т1 приймає наступний вигляд

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

На наступному кроці має бути отримано ще одне проміжне ставлення, Т2

WITH ( Tl GROUP { DURING } AS X ) AS T2 :

Результуюче відношення Т2 показано на рис 235

Атрибут X відносини Т2 має значення у вигляді відношення, тому до унарним відносинам, що є значеннями цього атрибута, можна застосувати оператор COLLAPSE таким чином

WITH ( EXTEND T2 ADD COLLAPSE ( X ) AS Y )

{ ALL BUT X } AS T3 :

Чергове проміжне ставлення ТЗ наведено нижче (зверніть увагу на те, що атрибут X був видалений за допомогою операції проекції, заданої у вигляді специфікації {ALL BUT X}), як показано на рис 236

Нарешті, виконується розгрупування отриманого відносини таким чином

ТЗ UNGROUP У

Рис 235 Результуюче відношення Т2Рис 236 Проміжне ставлення ТЗ Даний вираз дозволяє отримати бажаний результат Іншими словами, після

обєднання всіх описаних вище кроків (і невеликого спрощення) формується наступне загальне вираз, що дозволяє досягти бажаного результату

WITH SP_DURING { S#, DURING } AS Tl ,

( Tl GROUP { DURING } AS X ) AS T2 ,

( EXTEND T2 ADD COLLAPSE ( X ) AS Y ) { ALL BUT X } AS T3 :

T3 UNGROUP Y

Тепер можна визначити оператор PACK (який, безумовно, є скороченим позначенням) Цей оператор має наступний синтаксис

PACK  r  ON A

Тут r – реляційне вираз, а А – інтервальний атрибут відносини, позначеного цим виразом Семантика даного оператора визначена шляхом очевидного узагальнення операцій групування, розширення, проекції і розгрупування, за допомогою яких був отриманий результат на підставі вираження T1, як показано нижче

PACK r ON А = WITH (r GROUP {А} AS X) AS R1,

( EXTEND Rl ADD COLLAPSE ( X ) AS Y )

{ ALL BUT X } AS R2

: R2 UNGROUP Y

Як було зазначено вище, тепер запит А може бути сформульовано таким чином

PACK SP_DURING { S#, DURING } ON DURING

Примітка Як пояснення слід явно зазначити (як має бути очевидно з цього визначення оператора PACK), що для упаковки відносини по деякому атрибуту А необхідно виконати групування цього відношення по всіх його атрибутам, крім атрибута А (Як було зазначено в розділі 7, наприклад, вираз Tl GROUP

{DURING} .. можна прочитати як групувати Tl пo S #, де s # є єдиним атрибутом відносини Т1, крім зазначеного в специфікації GROUP) Але слід зазначити, що хоча і гарантується повернення виразом r GROUP {A} ..” результату, що містить точно один кортеж для кожного окремого значення в (де в позначає всі атрибути r, крім А), вираз PACK r ON А може повернути результат, який містить кілька кортежів, що відносяться до будь-якого заданому значенню в В якості ілюстрації можна вказати результат операції PACK для запиту А, який містить два кортежу, що відносяться до постачальника S4

Тепер перейдемо до вивчення onepaтopa UNPACK та запиту в

■ Запит в Визначити пари S #-DURING з даними про постачальників, що не були здатні поставляти будь-які деталі взагалі, впродовж щонайменше одного інтервалу часу, де DURING позначає такий інтервал

Тепер читачеві, ймовірно, стало ясно, що тут фактично потрібно знайти всі пари S #-DURING, які присутні або випливають з відносини S_DURING, і разом з тим не присутні і не випливають з відносини SP_DURING Такого короткого аналізу розглянутої задачі має бути достатньо, щоб зробити припущення (цілком обгрунтоване), що тут, по суті, знову потрібно виконати ряд операцій розпакування, застосувати до результатів операцію різниці, потім знову упакувати отриманий результат операції різниці Отже, спочатку розглянемо наведений нижче оператор UNРАСК

UNPACK r ON A = WITH (r GROUP {А} AS X) AS Rl, (EXTEND Rl ADD EXPAND (X) AS Y)

{ ALL

BUT X } AS R2 : R2 UNGROUP Y

Це визначення ідентичне визначенню оператора PACK, якщо не рахувати того, що у другому рядку замість оператора COLLAPSE зявився оператор EXPAND Назвемо результат цього виразу розпакованої формою ставлення r по атрибуту А .

Тому, що стосується запиту в, то лівий необхідний нам операнд (тобто пари S # DURING, які присутні або випливають з відносини S_DURING) МОЖНА отримати наступним чином

UNPACK S_DURING { S#, DURING } ON DURING

Нижче наведена розгорнута форма цього виразу

WITH S_DURING { S#, DURING } AS Tl ,

( Tl GROUP { DURING } AS X ) AS T2 ,

( EXTEND T2 ADD EXPAND ( X ) AS Y ) { ALL BUT X } AS T3 :

T3 UNGROUP Y

Детальну покрокову опрацювання цього виразу залишаємо читачеві як вправа Але якщо як приклад розглядаються дані, наведені на рис 234, то загальний результат (назвемо eгo Ul) виглядає наступним чином

Безумовно, правий операнд (тобто пари S #-DURING, які присутні або випливають з відносини SP_DURING) може бути отриманий аналогічним чином

UNPACK SP_DURING { S#, DURING } ON DURING

Тепер можна застосувати оператор різниці в такий спосіб

Нижче наведено результат цього виразу (назвемо його U2)

Ul  MINUS  U2

Результат цього виразу (назвемо його Uз) має наступний вигляд

Нарешті, упакуємо ставлення з, щоб отримати бажаний загальний результат

PACK U3 ON DURING

Остаточний результат наведено нижче

Отже, запит до має наступне формулювання у вигляді одного виразу

PACK

( ( UNPACK S_DURING { S#, DURING } ON DURING ) MINUS

( UNPACK SP_DURING { S#, DURING } ON DURING ) )

ON DURING

Відзначимо, що розпакування відносини r по атрибуту А (як і упаковка відносини r по атрибуту А) зводиться до групування відносини r по всіх атрибутів відносини r, крім А

Як і оператори COLLAPSE І EXPAND, на яких вони засновані, оператори PACK І UNPACK не є зворотними по відношенню один до одного Тому ні вираз UNPACK (PACK r ON A) ON А, ні вираз PACK (UNPACK Г ON A) ON А в загальному випадку не є тотожно рівними r (хоча обидва ці вирази еквівалентні відношенню r, в тому сенсі, який буде описаний трохи пізніше) Безумовно, можна легко показати, що справедливі наведені нижче тотожності

UNPACK r ON A ≡ UNPACK ( PACK r ON A ) ON A PACK r ON A ≡  PACK ( UNPACK r ON A ) ON A

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

Додаткові приклади

У цьому розділі розглядаються деякі додаткові приклади використання операцій PACK і UNPACK при формулюванні запитів Тут прийнято цілком обгрунтоване припущення, що в кожному випадку потрібно Результат у формі, упакованої належним чином

Як перший приклад навмисно розглянуто запит, що не належить до тимчасових інтервалах Припустимо, що задана змінна відносини NHW з атрибутами NAME, HEIGHT і WEIGHT, в якій міститься інформація про зріст і вагу окремих осіб Розглянемо запит: Для кожного значення ваги, представленого у змінній відносини NHW, отримати кожен діапазон значень зростання, такий що для кожного вказаного діапазону г і для кожного значення зростання в діапазоні r існує щонайменше одна особа, представлене в NHW, яке має такий зріст і такий вагу . Нижче наведена одна з можливих формулювань необхідного запиту

PACK

( ( EXTEND NHW { HEIGHT, WEIGHT }     ADD INTERVAL_HEIGHT ( [ HEIGHT : HEIGHT ] ) AS HR )

{ WEIGHT, HR }

) ON HR

Пояснення Почнемо з формування проекції NHW за атрибутами HEIGHT і WEIGHT, отримавши тим самим всі пари значень зросту і ваги з первинного відносини (тобто всі такі пари зросту і ваги, що є щонайменше одна особа з таким ростом і вагою) Потім ця проекція розширюється шляхом введення ще одного атрибута, HR, значенням якого в будь-якому заданому кортежі є одиничний інтервал у формі [h: h], де h – значення атрибута HEIGHT в тому ж кортежі (зверніть увагу на виклик селектора інтервалу INTERVAL_HEIGHT) Після цього за допомогою операції проекції видаляється атрибут HEIGHT і результат упаковується по атрибуту HR Остаточним результатом стає ставлення з двома атрибутами WEIGHT І HR, яке має наступний предикат

Для всіх значень зростання h в HR (але не для h = PRE (HR) або h = POST (HR)) існує щонайменше одна особа р, таке що р має вагу WEIGHT і зростання h

Як другий приклад знову розглянемо змінну відносини SP_DURING У будь-який конкретний момент часу (за умови, що в цей час взагалі виконувалися будь-які поставки) існує деякий номер деталі ротах, такий що жоден постачальник не здатний поставляти в цей час яку-небудь деталь з номером більше ротах (Безумовно, при цьому передбачається, що для значень типу Р # визначений оператор >.) Тому розглянемо запит: Для кожного номера деталі, який коли-небудь був таким значенням ротах, отримати цей номер деталі разом з інтервалом (інтервалами), протягом якого він фактично був таким значенням Рmах . Нижче наведена одна з можливих формулювань подібного запиту

WITH ( UNPACK SP_DURING ON DURING ) AS SP_UNPACKED , ( SUMMARIZE SP_UNPACKED

BY { DURING }

ADD MAX ( P# ) AS PMAX ) AS SUMMARY

: PACK SUMMARY ON DURING

Заключні зауваження

З приводу операторів PACK І UNPACK може бути сказано набагато більше, ніж було відведено місця в цій главі Їх докладний опис можна знайти в [234] нижче просто перераховані без докази або додаткових коментарів деякі найбільш важливі властивості цих операторів

■ Упаковка або розпакування будь-якого відношення r взагалі без зазначення будь-яких атрибутів призводить просто до отримання відносини r

■ Розпакування відносини r по двох або декільком атрибутам, притому що всі ці атрибути мають значення у вигляді інтервала8, здійснюється дуже просто якщо рас сматривать атрибутами є А1, А2, , An (в певному порядку), то бажаний результат може бути отриманий шляхом розпакування г по атрибуту А1, потім розпакування результату цієї першої розпакування по атрибуту А2, , Нарешті, розпакування результату передостанній розпакування по атрибуту An

■ Упаковка відносини r по двох або декільком атрибутам, притому що всі ці атрибути мають значення у вигляді інтервалу, стає трохи більш складним завданням Але неформально можна стверджувати, що якщо розглянутими атрибути тами є А1, А2, , An (у зазначеному порядку), то бажаний результат можна отримати, спочатку розпакувавши r за всіма зазначеними атрибутам, а потім упа кували отриманий результат розпаковування по атрибуту А1, упакувавши результат пер шої упаковки по атрибуту А2, , Нарешті, упакувавши результат передостанній упаковки по атрибуту An

■ Припустимо, що rl і г2 – відносини одного і того ж типу і атрибути А1,

А2, , An цих двох відносин мають значення у вигляді інтервалу Тоді

8 З цього випливає, що така операція ідеально підходить для обробки відносин, що мають два або декілька атрибутів зі значеніяміввідеінтервала

відносини rl і r 2 є еквівалентними (стосовно до атрибутів А1, А2, .., An) тоді і тільки тоді, коли результати операцій UN PACK rl ON (Al, A2, .., An) І UNPACK r2 ON (Al, A2,,,,, An) рівні: Tt Й

Джерело: Дейт К Дж, Введення в системи баз даних, 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>

*

*