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

Ще одним зі способів представлення в пам'яті ЕОМ записів баз даних є використання рекурсивних структур, у яких один з аргументів кожного запису вказує на наступний запис. Рекурсивні структури – аналог однозв’язних списків в інших мовах програмування, але працювати з такими структурами в Пролозі легше, тому що він бере на себе всі дії з обробки покажчиків.

Для того, щоб на Пролозі створити рекурсивну структуру, що складається з записів work() („службовці”), єдине, що потрібно – це ввести в цю структуру додатковий аргумент, що вказує на наступний запис, у структурі якої також буде міститися аргумент, що вказує на наступний за ним запис і т.д. Для вказівки в останньому записі відсутності наступного за ним запису, як додатковий аргумент уводиться „end”. Розглянемо приклад лінійної рекурсивної структури Службовець(Ім’я, Відділ, Посада, Оклад , Покажчик на наступний запис).

Використовуючи синтаксис мови Пролог, позначимо цю структуру work3(). За аналогією з раніше розглянутим прикладом, вона буде містити три записи

work3(„Маслов”, 101, „оператор”, 200,

work3(„Денега”, 211, „начальник”, 450,

work3(„Петренко”, 101, „менеджер”, 300, end)))

Як видно, рівень вкладеності в кожному новому записі буде більший, ніж у попередньому. У п’ятому полі останнього запису міститься слово „end”, що означає, що більше записів немає. Слід зазначити, що додатковий аргумент структури, що вказує на наступні записи бази даних, сам має структуру цього запису. Тобто структура запису визначається сама через себе: Службовець(Ім’я, Відділ, Посада, Оклад, Службовець).

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

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

record(work(Name, Office, Post, Salary), work3(Name, Office, Post, Salary, NextRecord)).

record(work(Name, Office, Post, Salary), work3(_,_,_,_, NextRecord)) :- work3(work(Name, Office, Post, Salary), NextRecord).

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

Goal: record (work(Name, 101, Post, Salary), work3(„Маслов”, 101, „оператор”, 200, work3(„Денега”, 211, „начальник”, 450, work3(„Петренко” ,l01, „менеджер”, 300, end))).

Відповідь на цей запит буде отримана у вигляді:

Name=Маслов,

Post=onepaтop,

Salary=200

Name=Петренко,

Post=менеджер,

Salary=300

Аналогічний варіант запиту реалізований як мета 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() дозволяє виконувати доступ до окремого запису БД.