Моделювання ієрархічних об’єктів, MS Office, Програмні керівництва, статті

Введення


Багатьом структурам та об’єктам властива ієрархічність. За прикладами далеко ходити не треба. Майже всі об’єкти складаються з частин, які, в свою чергу, можуть складатися з більш дрібних деталей. Громадські структури, як правило, відображають жорстку ієрархічну модель підпорядкування, сходящуюся до одного підрозділу або людини.


Через зовнішньої схожості, ієрархічні моделі часто називають деревами, Вершину ієрархії – коренем дерева, Найнижчі відгалуження – листям.

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

Спробуємо отримати відповіді на ці та інші питання.

Найпростіша ієрархія

Як приклад, візьмемо частину схеми підрозділів на підприємстві:












A1

B1

B2

C1

C2

C3


   
де А1 – підрозділ верхнього рівня (можливо, не єдине на цьому рівні),
В1 і В2 – входять до А1,
С1 – входить в В1, С2 і С3 – входять до В2.

Можна легко створити таблицю, яка містить інформацію про ці підрозділи (тут Ідалія – ​​синтаксис MS SQL):

create
 table Departments
(
Id int not null identity primary key,
Parent int not null references Departments(Id),
Name varchar(32) not null
)

Поле Parent є посиланням на Id (Первинний ключ) вищого рівня в ієрархії. В даному випадку воно вказує, в який підрозділ входить кожен відділ.

































Departments   

Id

Parent

Name

1

0

A1

2

1

B1

3

1

B2

4

2

С1

5

3

С2

6

3

С3


   
Характерні питання

Користуючись такою таблицею, легко можна знайти батьків або дітей у певного елемента. Але зазвичай з ієрархічними об’єктами виникають більш складні завдання.
Ймовірно, ми захочемо дізнатися, чи є даний елемент термінальним, Тобто, відсутні чи інші елементи, що входять в нього. Це потрібно, наприклад, для того, щоб відрізняти такі елементи від нетермінальних при виведенні ієрархічного довідника користувачеві.
Також може знадобитися дізнатися, на якому рівні ієрархії знаходиться заданий елемент.
Може виявитися необхідним отримати всіх предків даного елемента, починаючи зверху чи знизу.
Часто буває потрібно отримати всіх нащадків якогось елементу, при цьому з різними умовами: Наприклад, тільки термінальних, або, що знаходяться тільки на певному рівні і т. д.

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

Обхід дерева

Одне з рішень було запропоновано Joe Celko (див. [1]). Він рекомендував додати в таблицю два додаткові цілочисельних поля: Left і Right, В які заносяться результати обходу дерева, починаючи з кореня. Обхід організовується наступним чином: кожен раз, при проходженні якого-небудь елементу покажчиком, лічильник збільшується на одиницю; при попаданні в термінальний елемент, покажчик повертається в батька та шукає наступну дитину. В поле Left записується значення лічильника при першому проходженні елемента, а в поле Right – при останньому. При такому варіанті, наша таблиця підрозділів виглядала б наступним чином:

create
 table Departments
(
Id int not null identity primary key,
Parent int not null references Departments(Id),
Name varchar(32) not null,
Left int not null,
Right int not null
)

Departments












































Id

Parent

Name

Left

Right

1

0

A1

1

11

2

1

B1

2

4

3

1

B2

6

10

4

2

С1

3

3

5

3

С2

7

7

6

3

С3

9

9


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

Термінальні елементи помітно відразу – у них Left = Right.
Відносини предок – нащадок обчислюються теж легко: Left нащадка завжди більше ніж у предка, а Right – менше.
Інформацію про рівні заданого елемента можна дізнатися, отримавши кількість його предків.
Кількість нащадків = (Right – Left) / 2.
Головний недолік цього рішення в тому, що при зміні в структурі дерева, доводиться заново перераховувати значення полів Left і Right під всій таблиці. Тобто, такий спосіб годиться тільки для невеликих, рідко змінюваних таблиць.

Допоміжна таблиця

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

create
 table DepartmentsAncestors
(
Department int not null references Departments(Id),
Ancestor int not null references Departments(Id)
constraint DepartmentAncestor primary key (Department, Ancestor)
)

Поле Ancestor посилається на Id предка кожного елемента. В даному випадку воно дозволяє дізнатися всі підрозділи, в які входить даний відділ.

DepartmentsAncestors      





























Department

Ancestor

2

1

3

1

4

2

4

1

5

3

5

1

6

3

6

1


   
Подібна схема легко дозволяє отримати будь-яку інформацію про ієрархічних елементах одним запитом.
Очевидним чином, виходячи із самої структури допоміжної таблиці, можна отримати всіх предків, Або нащадків певного елемента.
Інформацію про рівні заданого елемента можна дізнатися, отримавши кількість його предків.
Термінальне елемента можна дізнатися, користуючись тільки основний таблицею – достатньо перевірити, чи є елементи, Parent яких дорівнює Id поточного.
Модифікація допоміжної таблиці, При зміні основної, проводиться досить просто. Турботу про неї можна надати або триггерам, або додатком.
Якщо запити з використання інформації про рівні і ознаку термінальній зустрічаються часто, і вимоги до часу їх виконання високі, то бажано створити відповідні поля в основній таблиці і підтримувати в них актуальні значення. Наприклад:

create table Departments
(
Id int not null identity primary key,
Parent int not null references Departments(Id),
Name varchar(32) not null,
Level int not null,
Terminal bit not null defaul(1)
)

Departments               












































Id

Parent

Name

Level

Terminal

1

0

A1

1

0

2

1

B1

2

0

3

1

B2

2

0

4

2

С1

3

1

5

3

С2

3

1

6

3

С3

3

1


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

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


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

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

Ваш отзыв

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

*

*