Повна версія

Головна arrow Інформатика arrow Бази даних: проектування

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Моделювання універсальних структур

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

Моделювання ієрархічних структур

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

Під ієрархічною структурою розуміють багаторівневу форму організації об'єктів з суворою соотнесенностью об'єктів нижнього рівня певного об'єкту верхнього рівня.

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

  • - Конструкція даних, в якій екземпляри об'єктів пов'язані з принципом батько-нащадок;
  • - Взаємозв'язок екземплярів об'єктів, що відображає супідрядність одного примірника щодо іншого;

взаємозв'язок екземплярів об'єктів, що відображає структурний опис об'єкта;

- Багаторівнева форма організації об'єктів з суворою соотнесенностью об'єктів нижнього рівня певного об'єкту верхнього рівня.

При описі ієрархій використовується термін "ступінь вершин" кількість ребер, пов'язаних з вихідної вершиною (вузол). Також застосовуються додаткові терміни, що описують окремі складові ієрархічної структури:

  • а) ступінь вузла - кількість дерев, що може бути побудоване на підставі дочірніх вузлів (нащадки);
  • б) кореневої вузол (корінь) - вузол дерева, що не має зв'язків з батьківськими вузлами;
  • в) кінцевий вузол (лист) - вузол дерева зі ступенем 0, що означає, що на дочірньому рівні немає ніяких вузлів;
  • г) вузол розгалуження - некінцевим вузол, що містить один або кілька дочірніх вузлів;
  • д) рівень вузла - порядковий номер рядка розміщення вузла, починаючи відлік від кореневого вузла, який володіє номером рівня "О".

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


  • 1. Дерево - ієрархічна структура, що припускає строго орієнтований граф, що не містить перетинів.
  • 2. Мережа - ієрархічна структура, що дозволяє утримувати перетину ребер, забезпечуючи зв'язок між вузлами типу М: М.

Основним поданням ієрархії є "Дерево" (рис. 4.39) з реалізацією ряду принципів його побудови:

  • 1) кожен нащадок пов'язаний тільки з одним батьком;
  • 2) на першому рівні представлений тільки один вузол, від якого вибудовуються всі інші вузли;
  • 3) кожна структура, що відходить немає від кореневого вузла, може бути представлена ​​самостійною структурою ієрархії.

image250

Мал. 4.39. Деревоподібне уявлення ієрархічної структури


При побудові ієрархічної структури в теорії графів виділяються наступні види:

  • а) двійкове (бінарне) неорієнтоване дерево - кожен вузол може мати не більше трьох дочірніх вузлів (нащадків);
  • б) двійкове (бінарне) орієнтоване дерево - кожен вузол може мати не більше двох дочірніх вузлів (нащадків);
  • в) Л ^ -арнос неорієнтоване дерево - кожен вузол може мати не більше N + 1 дочірніх вузлів (нащадків);
  • г) ЛГ-арное орієнтоване дерево - кожен вузол може мати не більше N дочірніх вузлів (нащадків).

Одним із прикладів організації ієрархічної структури виду "Дерево" є адміністративна карта держави, наприклад Німеччини, Франції, Росії і т.д. (Рис. 4.40). При розгляді адміністративного поділу держави існує чітко спрямована вкладеність дрібніших регіонів в більші.

На представленій адміністративній мапі Німеччини явно видно така наступна вкладеність.

  • 1. Німеччина
  • 1. Нижня Саксонія
  • 1. Бремен
  • 2. Ганновер
  • 3. ...

  • 2. image251Саксонія-Ангальт
  • 1. Магдебург
  • 2. Лейпциг
  • 3. ...
  • 3. Північна Рейн-Вестфалія 1. ...
  • 4. Бранденбург
  • 1. Берлін
  • 2. Потсдам
  • 3. ...
  • 5. Баварія
  • 1. ...
  • 6. ...

Пшбу



НІДЕРЛАНДИ, Фрлйоу Дортмунд © X
Ерфурт, на-Маннс Вірою, Потсдам, 0 Лейн ції и




■ ерхтеегялен

армшп-Партікнрхсі

Мал. 4.40. Приклад області застосування ієрархічної структури

Аналогічним чином можуть бути представлені будь-які інші держави. Залежно від розмірів держави ієрархічна структура може бути досить сильно розгалуженої з великою кількістю рівнів. При цьому се побудова може грунтуватися на лінійного зв'язку
рівнів між собою, визначаючи сувору послідовність і кількість рівнів структури.

Кращим прикладом такої організації ієрархії може бути представлення структури навчальної дисципліни (рис. 4.41), де є рівні ієрархічної структури (приклад): Дисципліна, Розділ, Тема, Питання.

image252

Мал. 4.41. Приклад ієрархічної структури


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

Додатковими прикладами організації ієрархічної структури виду "Дерево" можуть бути: структура розділів прайс-листа, структура бібліотеки, де але певним правилам розміщуються літературні твори; структури комп'ютерної та оргтехніки, забезпечуючи зручний доступ до окремих елементів при організації обслуговування і ремонту; організаційна структура підприємства; класифікації різних об'єктів, забезпечуючи їх розподіл відповідно до визначених класифікаційними ознаками.

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

Мережева структура практично повністю ідентична ієрархічній структурі виду "Дерево" (рис. 4.42), але дозволяє зберігати дані, використовуючи можливість безлічі батьків для одного нащадка. Дана організація досить громіздка і не оптимальна, оскільки вимагає від розробника досить великого програмування контролю роботи з елементами ієрархії.

Ієрархічна структура виду "Мережа" створюється на основі наступних принципів:

  • а) кожен вузол може бути пов'язаний з безліччю нащадків і безліччю батьків;
  • б) на кореневому рівні може розміщуватися безліч вузлів.

image253

Мал. 4.42. Мережеве уявлення ієрархічної структури


Ключовою особливістю даної ієрархічної структури є те, що на неї не поширюються правила суворої послідовності ієрархічних рівнів, а також з'являється можливість описати будь-які можливі взаємозв'язки між елементами, в тому числі циклічні (рекурсивні), коли елементи нижніх рівнів будуть батьками для елементів більш високих рівнів.

Одним з найбільш важливих недоліків організації такої ієрархічної структури є необхідність ведення досить об'ємного контролю за структурою на рівні програмного коду в процедурах бази даних.

Якщо розглянути ієрархічну структури виду "Мережа" у вигляді стандартної ієрархічної структури типу "Дерево", то видно, що зберігання інформації про структуру потребує дублювання елементів (рис. 4.43). Причому кількість продубльованих елементів буде дорівнює кількості необхідних зв'язків з даним елементом.

image254

Мал. 4.43. Деревоподібне уявлення мережевої структури


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

Подання ієрархічної структури виду "Мережа" дозволяє говорити про ідентичність принципів побудови і обробки по відношенню до ієрархічній структурі "Дерево".

З огляду на унікальний характер даної структури, не можна не згадати про ще один важливий факт, який визначає можливість при- мсненія ієрархічної структури, - все вузли повинні мати певне узагальнення, тобто дані, на які посилаються вузли структури (це відноситься і до "Дереву", і до "Мережі"), повинні відображати деяку загальну суть предметної області. Наприклад, "Область", "Край", "Округ" і т.д. можуть бути узагальнені єдиним терміном "Адміністративна одиниця".

Основним застосуванням ієрархічної структури виду "Мережа" є опис якого-небудь процесу, який передбачає деяку послідовність дій з можливими ветвлениями, поверненнями і перескакування (рис. 4.44). Для прикладу можна взяти графи технологічного процесу, наприклад складання будь-якого складного вироби. Такий граф передбачає можливі різні шляхи виконання операції складання з виходом на єдиний кінцевий результат (виріб).

image255

Мал. 4.44. Приклад представлення мережевої структури


Іншим прикладом може бути взаємодія категорій товарів в рамках прайс-листа. В даному випадку різні підкатегорії одних категорій можуть бути підкатегоріями для інших підкатегорій. Якщо уявити кожну вкладену категорію у вигляді певної спрямованої ієрархії "Дерево", то завдання побудови системи взаємодії підкатегорій приведуть до побудови ієрархії "Мережа".

Іншими прикладами ієрархічної структури "Мережа" можна назвати:

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

В основному ієрархічні структури грунтуються на наступних принципах (рис. 4.45).

Основу класичного підходу до побудови ієрархічних структур в базах даних становить моделювання структури даних, що відображають взаємодію окремих рівнів ієрархії між собою. При такому підході не доводиться говорити про будь-яку практичну користь від застосування подібної структури, але, тим не менш, вона ефективна, коли немає

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

image256

Мал. 4.45. Базові принципи побудови ієрархічної структури


Говорячи про розширення ієрархічної структури, припускають, що в структурі можуть з'явитися нові рівні, або ієрархія з поля зору "Дерево" перетвориться в вид "Мережа", що, природно, призведе до повної реорганізації структури даних. Прикладами такої організації можуть бути наступні елементи предметних областей:

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

Для кращого розуміння особливостей побудови ієрархічної структури при класичному підході трохи відвернемося від розглянутого прикладу і візьмемо структуру, що отримується при організації опису навчальної групи в освітній установі [1] (рис. 4.46).

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

image257

Мал. 4.46. Класична модель ієрархічної структури


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

  • 1) структура відображає взаємодію жорстко певної кількості рівнів, що істотно ускладнює механізми модернізації структури, як мінімум, в сторону розширення;
  • 2) використовується дублювання даних з метою побудови однозначної послідовності екземплярів різних рівнів;
  • 3) необхідно забезпечувати складну систему контролю послідовності обробки даних на рівні програмного коду;
  • 4) неможливо без додаткової обробки отримати візуальне уявлення ієрархічної структури як у вигляді всієї структури, так і її частин;
  • 5) неможливість зв'язати дані останньої (функціональної) таблиці з даними інших класифікаторів, крім останнього.

Тепер повернемося до розглянутої предметної області - електронний магазин. У цій предметної області є дві ієрархічні структури: адміністративний поділ адреси організації або фізичної особи і структура прайс-листа у вигляді поділу категорій товарів. Для прикладу будемо розглядати структуру категорій прайс-листа (рис. 4.47).

image258

Мал. 4.47. Подання структури прайс-листа в класичному варіанті


Застосовуючи класичну структуру ієрархії, варто задуматися про правильність опису атрибутів в сутності, і як наслідок, в таблицях бази даних. При цьому необхідно пам'ятати не тільки про типах даних, що зберігаються, а й про можливості зберігання значень NULL, можливих тригерних діях. Звичайно, більшість прийнятих рішень по опису атрибутів грунтується на реальній предметній області. Особливо це стосується функціональних атрибутів (табл. 4.20). Але для зовнішніх ключів і зв'язків між сутностями визначаються правила, які не залежать від предметних областей і орієнтовані на роботу в СУБД.

Таблиця 4.20

Опис властивостей сутностей структури

сутність

NULL

кардинальність

тригер

Категорія

-

11одкатегорія 1-го рівня - 0: Л Г *

-

11одкатегорія 1 -го рівня

"ІДФ Категорії" - так (якщо присутній на всіх категоріях)

I [одкатегорія 2-го рівня - 0: Л Г '

Каскадне зміна Установка NULL при видаленні

11одкатегорія 2-го рівня

"ІДФ підкатегорії 1-го рівня" - немає

Товари - 0: N

Каскадне зміна Заборона видалення

Товари

"ІДФ підкатегорії 2-го рівня" - немає

-

Каскадне зміна Заборона видалення



У разі роботи зі структурою послідовної зв'язку між класифікаторами необхідно відповісти на наступні питання.

Чи можуть бути відсутніми дані на батьківських рівнях? - Якщо можуть, то при описі зв'язків розглядається можливість існування записів в дочірніх таблицях при одночасній відсутності записів в батьківських таблицях, що призводить до вказівкою можливості зберігання значення NULL для зовнішніх ключів розглянутих сутностей.

Яка повинна бути потужність зв'язку від батьківської сутності до дочірньої? - Відповідь дозволяє визначити необхідність виконання додаткової обробки при внесенні значень в базу даних. Наприклад, підрахунок кількості наявних пов'язаних записів.

- Чи можливо видалення записів з батьківських таблиць зі збереженням дочірніх даних? - У результаті може бути прийнято рішення про блокування видалення, каскадному видаленні або інших видах тригерних дій.

Припустимо, що прайс-лист містить три рівні ієрархії і представляється суворим деревом. В цьому випадку модель буде представлена, як се змоделювали в процесі побудови моделі бази даних. Однак, потреба в розміщенні товарів не тільки по відношенню до останнього рівня ієрархії, а також для будь-якого рівня, призведе до необхідності в структурі суті "Товари" вказувати три зовнішніх ключа (рис. 4.48).

image259

Мал. 4.48. Модель категоризації товарів


Така організація моделі вимагає вказівки для всіх зовнішніх ключів, крім першого рівня, можливості храпения порожніх значень. У тому числі спостерігається дублювання зв'язків. З одного боку, всю структуру категоризації можна отримати через послідовні зв'язку підкатегорій, а з іншого - через зовнішні ключі. До того ж спостерігається можливе порушення цілісності даних, яке може виникнути при заповненні суті "Товари". Склад значень зовнішніх ключів категоризації товару може відрізнятися від структури, що формується зв'язками між сутностями підкатегорій. Також є аномалія оновлення, що не дозволяє додати товари в різні категорії.

Природно, що дана організація актуальна тільки в разі суворої послідовності рівнів і неможливості, з точки зору предметної області, пропуску будь-якого рівня. Якщо ж виникає необхідність в процесі опису значень ієрархічної структури опустити будь-якої рівень, то рішенням буде використання порожній записи, але дане рішення призводить до ряду негативних наслідків:

  • - Наявність "сміття" (порожні записи) в таблицях-класифікаторах на відповідних рівнях;
  • - Необхідність додаткової обробки одержуваних при вибірці даних з метою виключення порожніх даних і зв'язування даних різних рівнів.

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

image260

Мал. 4.49. Модель ієрархічної структури на основі сутності-зв'язки


Як очевидно з представленої нової моделі, фактичної ієрархічної структури між названими раніше рівнями не існує, що призводить до необхідності забезпечення структури на рівні програмного коду, істотно ускладнюючи процеси обробки даних. Проте, представлене рішення знімає проблему дублювання даних і зберігання "сміття" в таблицях-класифікаторах.

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

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

Використання подібної моделі ієрархії доцільно тільки в разі потреби давати лише візуальне уявлення ієрархічної структури на екранній формі в якості інформаційних відомостей, але не застосовувати її для зв'язків з іншими даними.

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

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

Однією з ключових особливостей є, з метою забезпечення унікальності записів в таблиці-структурі, необхідність використовувати унікальний індекс на базі комплексу полів - зовнішніх ключів структури. В кінцевому рахунку виходить модель ієрархічної структури, яка відповідає всім вимогам цілісності структури і забезпечення максимально ефективної обробки даних.

Описуючи подібну структуру, необхідно доповнити таблицю характеристик колонкою опису індексів (табл. 4.21). Але, знаючи, що в СУБД на первинні ключі кластерні унікальні індекси створюються автоматично, розглядати їх не будемо.

Таблиця 4.21

Опис властивостей структури на основі сутності-зв'язки

сутність

NULL

кардинальність

тригер

індекс

Категорія

-

Структура - (0,1 ): N

-

-

Будь 1-го рівня

Структура - 1: Л Г




сутність

NULL

кардинальність

тригер

індекс

Будь 2-го рівня

Структура - 1: Л Г

структура

Зовнішні ключі - так / ні (в залежності від умов предметної області)

Категорія - 0: Л Г 11одкатегорія 1 -го рівня -

  • 0: Л Г
  • 11одкатегорія 2-го рівня -
  • 0: Л Г

Товари - (0,1): N

Категорія,

категорія

  • 1-го рівня, категорія
  • 2-го рівня - каскадне зміна При видаленні - в залежності

від умов

предметної

області

складовою:

  • - категорія
  • - категорія
  • 1-го рівня
  • - категорія
  • 2-го рівня

Товари

"ІДФ структури" - немає

Структура - 1: jV

Каскадне зміна Заборона видалення


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

У випадку з функціональної сутністю, яка містить зовнішній ключ від сутності-структури, рішення про можливість існування значення NULL у зовнішнього ключа грунтується на вирішенні питання можливості опису об'єкта, яку представляють сутністю, поза прийнятої структури.

Необхідно звернути увагу на той факт, що тригерні дію відповідно до умов можливості зберігання значення NULL може бути різним - встановлення NULL, каскадне видалення (обмежується умовами тригера по зв'язку "Структура" - "Функціональна сутність"), заборона видалення.

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

Для такої організації ієрархічної структури використовується родітельскодочерняя модель структури (модель з подвійним зв'язком), де всі елементи представляються лінійним класифікатором, а сама структура


описується в окремій суті, містить вказівку на батьківський і дочірній елементи.

Розглядаючи класифікатор елементів, потрібно визначити основний фактор їх використання - унікальність існування кожного елемента в ієрархії, узагальненість опису кожного елемента, специфічність елементів на кожному вузлі ієрархії. Відповідно до правил, визначених у цій чиннику, ієрархія може бути представлена ​​кількома варіантами (рис. 4.50).

image261

Мал. 4.50. Модель ієрархічної структури з подвійним зв'язком


Перший варіант ієрархії цієї структури передбачає, що кожен елемент є унікальним і в структурі ієрархії може повторюватися. В цьому випадку функціональні суті опису цих елементів будуть пов'язані з класифікатором елементів, а сутність-структура буде відображати тільки принцип взаємодії елементів в ієрархічній структурі (див. Рис. 4.50). Ідентична модель буде використовуватися при узагальненості опису елементів структури.

У разі унікальності опису окремих елементів ієрархічної структури в залежності від їх розміщення в структурі необхідно використовувати кілька скориговану модель (рис. 4.51), де сутність опису буде зв'язуватися з сутністю-структурою.

image262

Мал. 4.51. Модель ієрархічної структури з описом окремого

елемента структури


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

image263

Мал. 4.52. Модель ієрархічної структури з додаванням рівня

Найчастіше при використанні подібної моделі організації ієрархічної структури виникає необхідність конкретизувати і впорядкувати рівні ієрархії. Ця умова істотно обмежує можливості ієрархії, але впорядковує уявлення елементів ієрархії відповідно до їх розташуванням на рівнях. При цьому необхідно пам'ятати, що розміщення елементів виконується в строгій послідовності рівнів і ніяк інакше.

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

Під рівнем ієрархічної структури розуміється розташування вузла ієрархії в структурі щодо початку ієрархії.

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

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

може бути пов'язана з сутністю-структурою ( "Структура") або з сутністю-класифікатором ( "Елементи структури"). Відповідно до прийнятого рішення розглядаються різні варіанти опису кардинальності зв'язків і можливості зберігання порожніх значень.

Незалежно від обраного принципу побудови ієрархії в даній моделі всі рішення по описаним тут характеристикам приймаються на основі аналізу предметної області. Наприклад, при обліку структури комп'ютерного обладнання і його характеристик можливі варіанти, коли планується придбання обладнання з певними характеристиками, але фактично в ієрархію до моменту придбання відповідний вузол не буде додано. В результаті дана ситуація може призвести до необхідності зберігати опису, не прив'язані до вузлів ієрархії, з наступною ув'язкою з доданим вузлом (ами). В цьому випадку для атрибута "ІДФ зв'язку" по суті "Опис вузлів" можливо зберігання порожніх значень (NULL), а також встановлення кардинальності 0: N або 0: 1.

Відносно індексів варто також проаналізувати предметну область і відповісти на питання: чи можливо зберігання зв'язки "Батько" - "Нащадок" кілька разів з однаковими значеннями? Якщо неможливо, то індекс буде складовою і унікальний. Якщо ж така ситуація можлива, то індекс буде тільки складовою (рис. 4.53).

image264

Мал. 4.53. Використання рівня в якості звичайного атрибута


Як очевидно з представлених раніше варіантів моделі ієрархічної структури, основними сутностями є: сутність-класифікатор, де описуються характеристики елементів ієрархії, і сущность- структура, де описується безпосередня організація ієрархічної структури. Даний підхід дозволяє істотно скоротити дублювання даних і відокремити самі елементи ієрархії від їх описів та структури ієрархії. Природно, що організація ієрархії через сутність з числовими атрибутами дозволяє спільно з застосуванням технологій індексування максимально підвищити швидкість обробки всієї структура.

При цьому, в моделі передбачається наявність двох зв'язків між сутностями, одна з яких вказує на батьківський елемент, а інша - па дочірній. Цей метод організації зв'язку потребують, при виконанні вибірок, створювати дублікати (клони) таблиці-класифікатора. Додатково виникає серйозна проблема з можливостями обробки ієрархії, яка полягає в тому, що при отриманні списку всіх дочірніх елементів до найнижчого рівня потрібна складна обробка на рівні програмного коду програми. Рішенням даної проблеми є додавання ще одного атрибута - "Рівня Вкладеності".


Опис характеристик моделі е подвійним зв'язком

сутність

NULL

кардинальність

тригер

індекс

елементи структури

Ієрархія (Батько) - 0: И ієрархія (Нащадок) - 0: ^ Опис вузлів - 0: Л Г

рівні ієрархії

-

Ієрархія - 0: ДГ

-

-

структура

Батько - Так (для першого рівня ієрархії)

Нащадок - Ні

Елементи структури (Батько) - 1: ДГ

Елементи структури (Нащадок) - 1: М

Рівні ієрархії - 1: Л Г Опис - вузлів - 0: Л Г

Каскадне зміна по зв'язку з елементами структури

Каскадне видалення по зв'язку з елементами структури

Заборона зміни по зв'язку з рівнями ієрархії

Заборона видалення по зв'язку з рівнями ієрархії

складовою:

  • - батько
  • - нащадок

опис вузлів

ІДФ зв'язку - Пет

Ієрархія - 1: М

Каскадне зміна каскадне видалення

-

ІДФ елемента - Ні

Елементи структури - 1: Л Г

Каскадне зміна каскадне удалегIне

-




Під рівнем вкладеності розуміється порядковий номер рівня розміщення дочірнього вузла щодо батьківського вузла.

Цей атрибут дає можливість при виконанні запиту вибірки спільно з атрибутом "Рівень ієрархії" впорядкувати елементи ієрархії в потрібній послідовності, що істотно скоротить обробку на рівні додатку.

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

 
Мал.  4.54.  Модель структури з одного рекурсивної зв'язком

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



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

Основна проблема при використанні даної технології організації ієрархічної структури полягає в правильній організації роботи з тригерними процедурами, які забезпечать якісну роботу з видалення вузлів ієрархії.

При розгляді даної моделі ієрархічної структури складність в описі характеристик становить рекурсивна зв'язок (табл. 4.23). Її наявність вимагає від СУБД використання додаткових механізмів (клонування), щоб забезпечити цілісність даних, що, природно, знижує швидкість обробки даних, що зберігаються.

В описі характеристик варто відзначити особливість зберігання порожнього значення для атрибута "Батько", який є зовнішнім ключем. Принцип храпения даних в подібній моделі передбачає, що використовується зв'язок між двома атрибутами всередині однієї сутності (рекурсивна зв'язок) і деякі СУБД не передбачають можливості зберігання порожнього значення для зовнішнього ключа. До того ж в цілях однаковості обробки даних по атрибуту "Батьківський" як батько самого верхнього рівня закладається порожній запис з незначними значеннями.

Таблиця 4.23

Опис властивостей структури з рекурсивної зв'язком

сущ

ність

NULL

Карди готівка ьность

тригер

індекс

еле

менти

струк

тури

Ієрархія - 0: Л Г

Струк

туру

Елемент структури - Ні

Елемент структури - 1: 1

Каскадне зміна каскадне видалення (за умовами предметної області)

По необхідності

Батьківський - Так (Ні-за наявності базової записи)

Батьківський - 0: Л Г

Каскадне зміна Заборона видалення Власний тригер по операції видалення



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

Також варто відзначити, що для забезпечення видалення необхідних даних по ієрархії необхідно використовувати тригери, написані розробниками, оскільки вбудовані механізми забезпечення цілісності не дадуть необхідного ефекту і приведуть до відбраковування практично будь-якої операції з видалення даних. Замість триггерного дії можуть використовуватися рекурсивна процедура і процедура з циклічною обробкою курсора (рис. 4.55).

image266

Мал. 4.55. Модель структури з подвійною рекурсивної зв'язком


Представлена ​​раніше модель володіє одним дуже істотним недоліком - база даних, побудована за цією моделлю, не дозволить без додаткового програмування отримати ієрархічну структуру розмірності більше одного рівня. Цей недолік може бути виправлений за допомогою побудови структури, що містить дві рекурсивні зв'язку. Звичайно, дана організація зберігання ієрархічних даних призводить до великої надмірності даних, але це компенсується гнучкістю отримання ієрархічної структури з бази даних.

Організація двох рекурсивних зв'язків дозволяє забезпечити зберігання не тільки класичної ієрархічної структури у вигляді дерева, а й мережевої структури, зберігаючи інформацію про взаімоподчіненность елементів відносно один одного. При цьому представлена ​​структура ієрархії дозволяє отримувати, використовуючи один нескладний запит, ієрархію будь-якого обсягу (кількість рівнів вкладеності) і щодо будь-якого вузла. До того ж, можна отримати доступ до будь-якої комбінації елементів, як в напрямку нащадків, так і в напрямку батьків, незважаючи на розташування елементів за рівнями.

Представлена ​​модель ієрархії дозволяє зберігати стандартну організацію дерева (з одного рекурсивної зв'язком) і "просунуту" модель (з організацією всіх зв'язків, включаючи мережеву організацію ієрархії). При цьому кількість рівнів вкладеності є необмеженим. У разі використання класифікатора рівнів їх кількість обмежується розміром класифікатора. Якщо класифікатор рівнів не використовувати, то кількість рівнів в ієрархії обмежується тільки можливостями відображення дерева в клієнтському додатку.

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

Щоб уникнути цієї проблеми, по суті-структурі використовується атрибут "Номер Вкладеності", що позначає кількість дуг, яке необхідно використовувати для досягнення елемента-нащадка, відштовхуючись від елемента-батька. В результаті такої операції модель ієрархії набуває подвійне властивість сортування і угрупування але атрибутам "Номер рівня" і "Номер Вкладеності", існуючих незалежно один від одного, але одночасно доповнюють один одного при виконанні вибірки ієрархічної структури.

Представлена ​​модель ієрархії володіє додатковим властивістю забезпечення цілісності даних: неможливість виконати операцію видалення батьківських вузлів без видалення всіх дочірніх вузлів. Дана властивість в інших моделях ієрархії не могло бути забезпечено з огляду на те, що їх реалізація грунтувалася на зберіганні тільки одного рівня вкладеності нащадка щодо батька. Створюючи надмірність даних і забезпечуючи подвійну рекурсивную зв'язок, ми проектуємо найбільш розвинену ієрархічну структуру (табл. 4.24).

При роботі з цією організацією ієрархічної структури потрібно досить відповідально підійти до реалізації подвійний рекурсивної зв'язку. Наявність обох зв'язків більшістю СУБД сприймається як заборона на видалення елементів, що може призвести до складнощів при виконанні даної операції. До того ж багато СУБД проводять видалення записів без урахування їх вкладеності в рамках однієї сутності, тому часто при виконанні видалення виникає помилка видалення, яка може бути виправлена ​​зниженням рівня контролю цілісності даних (прибрати рекурсивні зв'язку, залишивши атрибути) або написанням власних тригерних операцій.

У даній організації моделі ієрархії стоїть особливо виділити атрибут "Нащадок", одним з властивостей якого є неможливість зберігання порожнього значення (принцип зберігання даних - однозначна відповідність батька і нащадка), але для моделі допускається такий варіант. Обумовлено це тим, що для забезпечення цілісності даних передбачається зв'язок батько-нащадок елемента самого з собою. Для того, щоб уникнути проблем при додаванні даних, необхідно представити тригерні дію по додаванню даних, яке, за відсутності явно зазначеного нащадка, внесе значення первинного ключа в колонку "Нащадок".

Таблиця 4.24

Опис властивостей структури з подвійною рекурсивної зв'язком

сутність

NULL

кардинальність

тригер

індекс

еле

менти структури

Структура - 0: Л Г

структура

Елементи структури - Ні

Елементи структури - 1: 1

Каскадне зміна каскадне видалення (за умовами предметної області)

Батьківський - Так (Ні - при наявності базової записи)

Батьківський - 0: ЛГ

Каскадне зміна каскадне видалення

Унікальний за комплексом атрибутів (Батьківський; Дочірній)

Дочірній - Так

Дочірній - 1: Л Г

Каскадне зміна Заборона видалення Тригер на додавання по установці значення

Тригер на видалення



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

Однією з реалізацій бази даних з ієрархічною структурою є використання типу XML (рис. 4.56), який має на меті представити комплекс відомостей у вигляді дерева, спрямованого на подання до інтернет-додатку з можливістю виконання асинхронного процесу обробки даних. Цей варіант представлення даних зручний

для роботи користувача з уеЬ-ресурсами, але абсолютно неприйнятний з точки зору застосування для управління даними, оскільки вимагає створення дубльованих і надмірності даних.

 
Мал.  4.56.  Приклад представлення адреси

Схематично ХМЬ-схема даних може бути представлена ​​в досить звичному для розробника баз даних вигляді, де будуть описані взаємозв'язки між об'єктами даних і характеристики кожного об'єкта. Однак якщо реалізувати цю модель у вигляді коду розмітки ХМБ-страііци, то стане видно, що частина інформації втрачається або дублюється, а програмний додаток, обробляє таку структуру, має бути досить сильно орієнтоване на розглянуту структуру даних, оскільки механізму метаданих в СУБД для ХМБ- схеми не передбачається.



Ці обмеження дозволяють говорити про недостатню застосовності даного формату для роботи з ним у вигляді бази даних, але основні правила подання і опису даних можуть бути застосовані в комплексі з базами даних, що виражається у використанні спеціалізованих типів даних для атрибутів сутностей і мов обробки XML- даних поряд зі стандартним SQL-програмуванням.

Використання спеціалізованого типу даних в структурі бази даних дасть можливість інтегрувати XML-розмітку в структуру бази даних, а наявність спеціалізованої мови обробки XML-даних - зробити вибірку в реляційної базі даних але умовам до даних XML- формату (рис. 4.57). Це дозволяє при вибірці даних відразу отримати необхідну розмітку інтернет-сторінки в необхідному оформленні і не зажадає будь-якого додаткового програмування обробки вибірки з бази даних.

Проте, підхід з використанням формату XML має деякі недоліки, одним з яких є те, що дані зберігаються в текстовому
вигляді і тип даних "XML" є нащадком твань даних "Text", нс передбачає наявності розвинутого механізму обробки. До того ж для обробки даних, що зберігаються у форматі XML, необхідно використовувати спеціальні розширення або специфічні функції мов в СУБД. Все це накладає особливі обмеження на використання даного підходу.

image268

Мал. 4.57. Приклад суті з атрибутом типу XML


Додатково потрібно відзначити, що використання формату XML для зберігання ієрархії в базах даних призводить до суттєвої надмірності даних і необхідності забезпечити серйозну програмну обробку контролю значень однакових атрибутів в різних записах. Такий стан є наслідком зберігання даних в стандартному текстовому, але структурованому форматі.

Як приклад можна взяти дані клієнта (табл. 4.25), де адреса буде представлятися ієрархічною структурою, при припущенні наступної зв'язки: "Країна" - "Регіон" - "Місто" - "Вулиця" - "Будинок / Корпус" - "Квартира" . Як очевидно з наведеної таблиці, для кожного клієнта вказується власний набір ХМL-даних, що описують місце проживання людини. В даному прикладі проілюстрована ситуація, коли ряд даних (країна, регіон, місто і т.д.) може бути продубльований своїми значеннями, що може привести до суттєвих обмежень цілісності даних і не дозволить якісно провести обробку та вибірку необхідних даних.

З огляду на особливість того, що користувач може ввести, наприклад, назва країни різними варіантами: "Росія" або "РОСІЯ", що розглядається як різні екземпляри, вибрати всіх людей, що проживають в країні "Росія", буде неможливо, оскільки проживають в країні "РОСІЯ "можу не потрапити в результат вибірки. Ця проблема вирішується в реляційних базах даних, але на рівні XML-даних така проблема нерозв'язна.

Таблиця 4.25

Приклади представлення даних адреси в форматі XML

№ п / п

клієнт

Адреса

1

Іванов І. І.

<Country id = "PocciiH">

<Province id = "Центральний округ">

<City id = "MocKBa">

<Street> Рязанський npocneicr </ Street> <Home> 91 </ Home>

<App> 68 </ App>

</ City>

</ Province>

</ Country>



Закінчення табл. 4.25

№ п / п

клієнт

Адреса

2

ТОВ "Електроніка"

<Country id = "Poccnn">

<Province id = u Центральний округ ">

<City id = "MocKBa">

<Street> Рязанський npocncKT </ Strcct> <Hoine> 64 </ Home>

<App> 12 </ App>

</ City>

</ Province>

</ Country>

3

Сидоров С. С.

-



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

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

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

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

Раніше було сказано, що адреса повинна формуватися з класифікаторів, до яких можна віднести: "Країна", "Регіон", "Місто", "Вулиця".

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

image269

Мал. 4.58. Нормалізоване відношення, що містить адресу доставки


Розглядаючи зв'язку "Країна" - "Регіон" - "Місто" - "Вулиця", можна сказати, що перші три елементи є структурними компонентами адміністративного поділу держави і мають ідентичним набором атрибутів. Це наводить на думку про те, що до того ж, з огляду на їх ієрархічну зв'язок, їх потрібно представити ієрархічною структурою. Класифікатор "Вулиця", з одного боку, з огляду на його відмінного смислового наповнення щодо інших розглянутих класифікаторів адреси, недоцільно включати до складу формованої ієрархічної структури, але, з іншого боку, функціональна залежність вулиць тільки від рівня "Місто" вимагає відстеження функціональної залежності від листового елемента ієрархічної структури. У зв'язку з цими протиріччями можна використовувати два варіанти подання класифікатора "Вулиці", що складається з трьох атрибутів - "Поштовий індекс", "Тип вулиці" і "Назва вулиці".

Використання класифікатора "Вулиці" в окремій суті

(Рис. 4.59). Цей варіант найбільш логічний, що передбачає відділення смислово незв'язаного класифікатора в окрему сутність.

Розділивши адресу на структурні елементи, вулицю, подану класифікатором, пов'язаним з містом, але правилами нормалізації виділяють в окрему сутність. Між нею і вихідної сутністю встановлюється ідентифікує зв'язок один - до - багатьох.

image270

Мал. 4.59. Виділення вулиці в окрему сутність


Використання ієрархічного уявлення. При використанні другого варіанта застосування класифікатора "Вулиці" можливо його додавання до ієрархічній структурі, яка зв'язує країну, регіон і місто (рис. 4.60). Оскільки кількість рівнів ієрархічної структури не фіксоване (наприклад, для Росії вкладеність адміністративного поділу регіонів відрізняється від розміру вкладених адміністративного поділу Німеччини), то доцільно використовувати модель ієрархічної структури з рекурсивної зв'язком. З огляду на, що в обробці буде необхідно регулярно отримувати відомості по всій структурі ієрархії від листового елемента до всіх його батьківських компонентів, а також робити вибірки, що не включають певні рівні (наприклад, останній рівень, що відноситься до класифікатору вулиць), для організації моделі структури варто використовувати подвійну рекурсивную зв'язок.

image271

Мал. 4.60. Модель ієрархічного представлення адреси


В результаті всіх процедур нормалізації і побудови ієрархічної структури в моделі представлення адреси введена сутність "Структура адміністративного поділу", що припускає рівень деталізації до вулиці. Важливо відзначити один елемент, який відрізняється від усіх раніше представлених варіантів використання. Це ключовий елемент "ІДФ структури елемента (батьківський)". Даний атрибут, представляючись зовнішнім ключем, має властивість можливості зберігання порожнього значення "NULL". При тому, що зовнішні ключі, за замовчуванням, не повинні дозволяти зберігання порожніх значень, в даному випадку це обгрунтовано. Однією з реалізацій ієрархічних структур є можливість посилання на порожній екземпляр структури. Зробити це можна за допомогою установки властивості можливості використання порожнього значення для зовнішнього ключа, що визначає батьківський елемент (вузол).

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

Важливо ще звернути увагу на сутність "Вулиці". Звідти був прибраний атрибут "Назва вулиці", оскільки при включенні цього елемента в ієрархічну структуру назва вулиці буде, як і інші елементи структури, зберігатися в лінійному класифікаторі "Елементи адміністративного поділу". Сама сутність все одно необхідна в зв'язку з тим, що окремі атрибути ( "Поштовий індекс" і "Тип вулиці") мають відношення тільки до листовому елементу дерева, тобто до вулиць. Внесення вулиці в ієрархічну структуру дозволило позбутися від необхідності постійного контролю закріплення вулиці за містом, а не будь-яким іншим елементом структури.

  • [1] Вибір іншого предметної області для даного прикладу обумовлений більш явним поданням особливостей організації структури. При подальшому розгляді ми повернемося до вихідної предметної обла
 
<<   ЗМІСТ   >>