Page 44 - 4800

Аналогічний варіант запиту реалізований як мета print_101 програми 5.1.
/* Програма 5_1 */
domains
name = symbol
office = integer
worker = work(name,office)
/* опис рекурсивної структури */
work3 = work3(name, office, work3); end
predicates
print_101
record(worker, work3)
goal
print_101.
clauses
record(work(X, Y), work3(X, Y, _)).
record(work(X, Y), work3(_, _, Z)):- record(work(X, Y), Z).
print_101:- write(„Співробітники 101 відділу”), nl, record(work(X, 101),
work3(„Маслов”, 101, work3(„Денега”, 211, work3(„Петренко”, 101, end)))), write(X),
nl, fail.
Ця програма працює з БД work3(), представленою у вигляді лінійної рекурсивної
структури. Для спрощення програми в БД work() використовується лише два поля
(Прізвище і Відділ), тобто інформаційні елементи work(), містять лише по два
компоненти.
Процедура record() дозволяє виконувати доступ до окремого запису БД.

5.6 Представлення бази даних у вигляді двійкового дерева

Можна ще більше вдосконалити метод представлення даних у вигляді
рекурсивної структури, якщо перетворити структуру work3() у структуру типу двійкове
дерево. Це досягається шляхом введення в структуру запису БД ще одного додаткового
аргументу, що вказує на попередній запис.
Зміст використання двійкового дерева полягає в тому, щоб зберігати базу даних
у відсортованому вигляді. У розглянутому нижче прикладі база даних відсортована за
атрибутом, що описує ім'я службовця і представляється бінарним деревом, що
представлене на рис. 5.1.

Маслов, …

Денега, … Петренко, ….

end end end end

Рисунок 5.1 – Структура двійкового дерева

Тепер у структурі інформаційного елемента буде шість аргументів:
work4(LeftTree, Name, Office, Post, Salary, RightTree)
Змінна LeftTree описує вітку дерева, що містить усі цілісні інформаційні
елементи, що знаходяться (за алфавітом) перед поточним елементом. Змінна RightTree
описує вітку дерева, що охоплює всі цілісні інформаційні елементи, розташовані
відповідно до алфавіту, після даного елемента. Через те, що БД відсортована, цілісний
інформаційний елемент, що містить відомості про Денегу, є верхнім вузлом дерева, а
саму БД, представлену у вигляді двійкового дерева (рис. 5.1), можна записати в такий
спосіб:
work4(work4(end, Денега, 211, „начальник”, 450, end), „Маслов”, 101,
„оператор”, 200, work4(end, „Петренко”, 101, „менеджер”, 300,end))
Версія процедури record() для доступу до цілісного інформаційного елемента
БД, представленої у вигляді двійкового дерева, буде базуватися на трьох правилах:

44