Харківський національний університет радіоелектроніки

Летучий Дмитро Олександрович

МЕТОДИ І ЗАСОБИ ОРГАНІЗАЦІЇ ДЕДУКТИВНИХ БАЗ ДАНИХ

01.05.04 – системний аналіз і теорія оптимальних рішень

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків – 2004

Дисертацією є рукопис.

Робота виконана в Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник: доктор технічних наук, професор Буслік Микола Миколайович, Харківський національний університет радіоелектроніки, професор кафедри штучного інтелекту.

Офіційні опоненти:

– доктор технічних наук, професор Петров Едуард Георгійович, Харківський національний університет радіоелектроніки, завідувач кафедри системотехніки;

– кандидат технічних наук Шостак Ігор Володимирович, Національний аерокосмічний університет ім. М.Є. Жуковського “Харківський авіаційний інститут”, доцент кафедри програмного забезпечення комп'ютерних систем.

Провідна установа:

Інститут кібернетики імені В.М. Глушкова НАН України, відділ автоматизації програмування, м. Київ.

Захист відбудеться "07" липня о 15 годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел: (057) 702-14-51.

З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки (61166, м. Харків, пр. Леніна,14).

Автореферат розісланий "4" червня 2004 р.

Вчений секретар

спеціалізованої вченої ради В.М. Левикін

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

Теорія ДБД виникла в результаті започаткованих із середини 70-x рр. досліджень, зв'язаних з використанням апарата логіки предикатів як моделі даних. Розвиток теорії ДБД багато в чому визначило інтенсивне дослідження проблем організації даних і природного опису предметних областей, що проводилося багатьма вітчизняними і закордонними вченими (А.О. Стогній, О.О. Бакаєв, Б.В. Ігнатенко, Ю.П. Шабанов-Кушнаренко, М. М. Буслік., Д.О. Поспєлов, А.В. Замулін, Д. Цикритзис, П. Джексон та ін.).

На теперішній час склалося кілька наукових шкіл з теорії ДБД, на чолі яких стоять такі відомі вчені як Н. Леоне (Італія-Австрія), Дж. Мінкер (США), С. Чері (Італія-США), М. Кіфер (Ізраїль-США) та ін. Після первісного становлення теорії ДБД і створення дослідницьких прототипів систем ДБД, що підтвердили практичну доцільність застосування їх для розв'язання широкого кола задач, у тому числі й задач прийняття рішень, на перший план вийшли питання розвитку технології ДБД, створення методів і засобів організації ДБД у рамках існуючих технологій баз даних. Впровадження такої технології на промислових підприємствах народного господарства України сприятиме підвищенню ефективності та якості управлінських рішень.

Зв'язок роботи з науковими програмами і темами. Дисертація виконувалася за планом наукових досліджень Харьківського національного університету радіоелектроніки у рамках держбюджетних науково-дослідних робіт “Розробка концепцій, методів та моделей підтримки систем з розподіленим штучним інтелектом” (№ ДР 0100U001341, 2000-2002 рр.) та “Розробка математичного, інформаційно-лінгвістичного і програмного забезпечення розподілених мережевих інтелектуальних систем” (№ ДР 0103U001548, 2003-2005 рр.) у яких автор брав участь як виконавець.

Мета і задачі дослідження. Мета роботи полягає у створенні технології (методів і засобів) розробки експертних систем (ЕС), проблемно-орієнтованої на розв'язання задач інтелектуального аналізу даних у ІСППР, на основі застосування дедуктивних баз даних (ДБД). Для досягнення поставленої мети в роботі вирішені наступні задачі:–

дослідження абстрактних моделей ЗПР і розробка способів подання ЗПР у рамках теоретико-доказового підходу;–

структурний і семантичний аналіз логіко-предикативної моделі ЗПР, синтез і оптимізація моделі пошуку рішення (створення плану обчислень);–

розробка методу відображення моделі ЗПР в систему рівнянь розширеної реляційної алгебри та керованого методу її обчислення;–

розробка архітектури й принципів функціонування системи ДБД як основи технології ЕС у ІСППР.

Об'єктом дослідження є процеси розв'язання задач інтелектуального аналізу даних у ІСППР.

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

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

Наукова новизна роботи полягає у досягненні таких результатів:–

вперше запропонована абстрактна логіко-предикативна модель подання знань проблемної області ЗПР, що, на відміну від існуючих моделей, в повному обсязі відтворює вирази розширеного числення предикатів першого порядку, і, таким чином, дає змогу розв’язувати широкий клас ЗПР декларативними засобами;

– удосконалено методи аналізу коректності опису і синтезу моделі пошуку рішення за рахунок уведення комплексу нових структурно-лінгвістичних моделей опису задачі, що дає змогу підвищити рівень інтелектуалізації етапів розв’язку задач підготовки та прийняття рішень;

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

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

Практичне значення отриманих результатів. У роботі знайшла обґрунтування можливість використання теоретико-доказового підходу і результатів теорії ДБД для розвитку засобів інтелектуального аналізу даних в ІСППР. Показано необхідність системної організації математичного забезпечення, що лежить в основі технології декларативного опису і розв’язку задач.

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

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

3. Розроблені методи організації ДБД і запропоновані принципи СДБД лягли в основу створення діючого прототипу СДБД "DLQ", який було апробовано в умовах промислової експлуатації при виконанні наступних госпдоговірних тем:–

“Розробка комп'ютерно-орієнтованої моделі комплексу задач обробки даних радіоекологічного моніторингу” (замовник – Харківський державний міжобласний спецкомбінат, акт від 3.04.2002); –

“Розробка концепції й архітектури інформаційно-дорадної системи “Газотурбінні установки для енергетики і промислового використання” (№ ДР 0103U005709, замовник – ТОВ “ФЕС”, робота знаходиться у стадії виконання, акт приймання-здачі першого етапу від 28.02.2004).

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

Особистий внесок здобувача. У працях, що написані в співавторстві, дисертанту належить: [1] – особисто запропоновано модифікацію алгебраїчного методу обчислення, наведено формальні правила перетворення логічної програми у систему SQL запитів; [2] – особисто запропонована абстрактна логіко-предикативна модель подання знань, досліджено структурні властивості цієї моделі і розроблені методи її структурного та семантичного аналізу; [3] – особисто запропонований принцип відкритості мовних засобів СДБД, розроблено модифікований метод нисхідного аналізу мови ДБД; [4] – особисто проаналізовано можливість застосування технології дедуктивних баз даних для реалізації ЗПР, запропоновані принципи створення СДБД: зв'язування ДБД із реляційною базою даних, єдність засобів опису задачі і керування даними, поділ середовища формування і реалізації запитів, принцип мінімальних обчислень в ітеративному процесі виведення.

Апробація результатів роботи. Результати дисертаційної роботи доповідалися й обговорювалися на конференціях “Радіоелектроніка і молодь у XXI столітті” (Харків, 2001, 2002)[86, 89, ], на 8-й Міжнародній конференції “Теорія і техніка передачі, прийому й обробки інформації” (Харків, 2002)[87], на Міжнародній науково-практичній конференції “Комп'ютери. Програми. Інтернет” (Київ, 2003)[88].

Публікації. За темою дисертації опубліковано вісім робіт, із них чотири – у виданнях, затверджених ВАК України.

Структура і обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновку, викладених на 134 сторінках машинописного тексту, містить 20 ілюстрацій і 3 таблиці на 2 сторінках, список використаних джерел з 100 найменувань на 8 сторінках і 4 додатки на 27 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі аналізується концепція ДБД як засобу реалізації загальної задачі прийняття рішень у ІСППР. Як відомо, переважна більшість ІСППР функціонує в рамках технології реляційних баз даних. Так, традиційно ІСППР ототожнюють з OLAP системами. Однак OLAP системи забезпечують кінцевого користувача в основному засобами статистичного аналізу даних і не надають яких-небудь засобів для інтелектуального аналізу даних. Разом з тим, на практиці часто виникає ситуація, коли аналітик (експерт) не може чітко сформулювати запит у OLAP системі, тому що не має якісну інформацію про наявні дані, тобто фактично не знає, яка порція даних повинна піддаватися кількісному (статистичному) аналізу для виявлення характерних тенденцій у предметній області. Методи реалізації запитів такого роду одержали розвиток у новому активно розроблюваному поколінні OLAP систем – систем "видобутку" даних (Data mining). У роботі розвивається теоретико-доказовий підхід (технологія ДБД) для розробки засобів інтелектуального аналізу в ІСППР, що на відміну від традиційного, теоретико-модельного підходу забезпечує:

· високий рівень абстракції при реалізації ЗПР;

· рішення ЗПР винятково на основі опису предметної області задачі.

Дедуктивна БД описується триплетом

<EDB, IDB, IC>,

де EDB – множина основних атомарних формул (екстенсіональних фактів);

IDB – множина визначальних правил для інтенсіональних предикатів;

IC – множина обмежень.

Компоненти ДБД описуються на Пролог подібній декларативній мові Дейталог. Вирішити задачу в середовищі ДБД – означає обчислити предикати її IDB, що відповідає виконанню логічної програми. Обчислення програми має ітеративний характер і завершується, коли на черговому кроці виведення неможливо вивести жоден новий факт. Результат обчислення логічної програми (множина екстенсіональних і інтенсіональных фактів) є моделлю програми, якщо тільки не порушені обмеження IC. Таким чином, обчислення ЗПР ототожнюється з пошуком моделі логічної програми ДБД.

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

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

· покрокове поліпшення породжуваних (виведених) альтернатив;

· нумерація (індексація) виведених фактів інтенсіональної БД (дозволяє фіксувати виведення зовні однакових альтернатив на різних кроках розв'язку ЗПР);

У другому розділі вводиться і досліджується сукупність оригінальних логіко-предикативних моделей опису узагальненого класу ЗПР виду

<Pi, Pi> (i = I, II, III),

де Pi – множина діз'юнктів опису предметної області (екстенсіональних

фактів EDB і правил логічної програми);

Pi – множина основних атомів, які задовольняються у Pi, або так звана модель Pi.

Множина усіх можливих моделей Pi зветься семантикою, яка позначається Mi. Сукупність логіко-предикативних моделей становить абстрактну логіко-предикативну модель подання знань проблемної області ЗПР.

Кванторним виразом a називається кон'юнкція кінцевої множини позитивних літералів і (чи) кванторних виразів:

a: $YjОN &k sk(..., Xki, ...),

де N – множина індексів зв'язаних змінних, {Yj} М k{Xki};

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

Кванторний вираз a, що заперечується (записується як ~a), називається негативним атрибутивом, (позитивний) кванторний вираз – (позитивним) атрибутивом. Змістовно позитивний атрибутив інтерпретується висловлюванням “існує”, негативний атрибутив – “не існує”.

У роботі досліджено структурні властивості моделі з кванторними виразами, обґрунтована редукція T-a(S) програми S PI (програми Дейталога з атрибутивами) до програми відомої версії стратифікованого Дейталога (Дейталога). Показано зворотне перетворення T+a програми Дейталога у програму PI:

S = T+a(T-a(S)).

Пропозиція 1. Теорія Дейталога з атрибутивами повна і несуперечлива.

Наслідок. Семантика MI програми S PI є M(T-a(S)), де M – семантика стратифікованого Дейталога.

Позначимо i часткову модель, що містить факти, виведені до початку виконання кроку i+1. Обмежимо область значень змінних атрибутива константами, що індуковані фактами часткової моделі:

a(i ): $YjОN &k sik(..., Xki, ...),

де sik(..., Xki, ...) – значення предиката (атрибутива) на частковій моделі i.

Назвемо такого роду “обмежені” атрибутиви частковими. Змістовно (позитивний) частковий атрибутив інтерпретується висловлюванням “вже існує”, а негативний частковий атрибутив – “ще не існує”.

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

Визначимо оператор T*S(i), що діє на множині позитивних цілих:

де

infer*(X) – множина фактів, безпосередньо виведених з множини X з урахуванням запропонованої семантики часткових атрибутивів;

FACTS(S) – множина фактів програми S;

RULES(S) – множина правил S.

На основі введеного оператора T*S була обґрунтована наступна пропозиція.

Пропозиція 2. Теорія Дейталога з частковими атрибутивами повна і несуперечлива.

При доведенні пропозиції була встановлена тотожність моделі програми з частковими атрибутивами, що складається з однієї страти, найменшій верхній грані множини {T*S(i) | i N}.

Наслідок. Семантика MII програми S PII є

MII(S) = j lub {T*Sj(i) | i, j N, Sj – страта j програми S}.

З метою створення цілісної технології опису і рішення задач на основі ДБД у Дейталог були включені наступні традиційні розширення:

· убудовані предикати арифметичного порівняння;

· типізація змінних;

· функціональні терми.

У роботі отримано розв'язок однієї з складних проблем теорії ДБД – нумерації фактів, – на основі введення в Дейталог системного типу даних counter (лічильник). Вивчена і формально визначена семантика MIII програм S PIII з типом даних counter:

MIII(S) = j lub {Tc(i) | i N, Sj – страта j програми S},

де

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

Визначимо рекурсивно залежність аргументу argr головного предиката pi від аргументу args предиката pk тіла правила R:

1) pk міститься в тілі R і змінна в позиції аргументу argr збігається зі змінною в позиції аргументу args;

2) argr залежить від argt предиката pm і argt залежить від args предиката pk.

Аргумент є рекурсивним, якщо він залежить від самого себе.

Предикат лічильно-рекурсивний, якщо він рекурсивний і містить у схемі аргумент типу counter.

В роботі проаналізовано сходимість обчислень і строго обґрунтовані додаткові умови безпеки програм PI PII PIII:

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

Теорема 2. Якщо програма PIII не має лічильно-рекурсивних предикатів, то вона має кінцеву модель.

Розроблені логіко-предикативні моделі ЗПР <Pi, Pi> (i = I, II, III) покладені в основу мови дедуктивних баз даних – квантифікованого Дейталога (DLQ).

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

· виявлення структурних властивостей програми з метою побудови коректного і раціонального плану її обчислення;

· визначення контекстно-залежних умов (наприклад, перевірка погодженості типів даних змінних), у тому числі умов безпеки.

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

Позначимо множину індексів страт логічної програми через K.

Твердження 1. {Si} = {T+a(S'i )}, iK, причому S' = iS'i, S'iS'j = (i,jK; ij).

На додаток до існуючих структурно-лінгвістичних моделей програм ДБД (графа залежностей предикатів, графа відношень-аксіом) були введені дві нові моделі:

· граф залежностей змінних (ГЗП = <V, E>):

V = {<<p, v, n, fl>, t>},

де p – предикат, v - змінна p, n - позиція v у p,

fl – прапорець входження v у головний предикат (fl О {.T., .F.}),

t – мітка, яка позначає, що v входить у складений терм (t='f ');

E = {<<p1, v1, n1, f1>, <p2, v2, n2, f2>> | v1=v2 & f2=.F. & (f1=.T. Ъ f1=.F. &

& n1<n2};

· граф залежностей аргументів (ГЗА = <V, E>):

V = <<p, n>, t>;

E = {<<p1, n1>, <p2, n2>> | аргумент n1 предиката p1 залежить від аргументу n2 предиката p2}.

Для побудови ГЗА розроблено метод, що зв'язує множину ГЗП за наступними правилами:

1. <<p, n>, t> ГЗА.1, якщо тільки G {ГЗП}? <<p, v, n, fl>, t> G.1;

2. <<p1, n1>, <p2, n2>> ГЗА.2, якщо тільки

(G1, G2 {ГЗП} <<p1, v1, n1, .T.>, <p11, v11, n11, f11>> G1.2 &

& <<p11, v21, n11, .T.>, <p2, v2, n2, f2>> G2.2)

(G {ГЗП} <<p1, v1, n1, f1>, <p2, v2, n2, .F.>> G.2).

Твердження 2. Аргументи, що входять у ланцюг ГЗП, повинні бути погодженими.

Твердження 3. Програма небезпечна, якщо в ГЗА існує цикл із дугою, позначеною 'f '.

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

Рис. 1. Оптимізація обчислень в ДБД

Нехай S – програма DLQ, – перетворення методом статичної фільтрації, MDLQ – семантика програми DLQ.

Твердження 4. (S) DLQ і MDLQ((S)) = MDLQ(S).

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

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

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

Розглянемо правило "p :- r, s" і його алгебраїчне подання "P = R ґ S" (тут для зручності і без втрати узагальненості змінні опущено).

Принцип мінімальності ітеративних обчислень. Схема обчислення виключає повторне одержання фактів у послідовності кроків j виведення:

P T: {D(R ґ S)(j) | j О N} ґ J, J = {<j>},

T(j) = T(j-1) И D(R ґ S)(j) ґ J,

D(R ґ S)(j) = (R(j-1) ґ DS И DR ґ S(j-2)).

Тут DX(j) – збільшення відношення X на кроці j (диференціал X).

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

Твердження 5. Ітеративний процес, що порушує принцип мінімальності, не сходиться при обчисленні програм з типом даних counter.

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

· зв'язування ДБД із реляційною БД;

· єдність засобів опису задачі і керування даними. У роботі наводиться надмова DLQ, що розширює DLQ командами створення, видалення і модифікації ДБД і її компонентів (користувачів ДБД, параметрів зв'язку ДБД із РБД), а також командами формування запитів як до самої ДБД, так і до її компонентів;

Рис. 2. Методичне й алгоритмічне забезпечення СДБД

· поділ середовища формування і реалізації запитів (створення СДБД на основі архітектури "клієнт-сервер");

· відкритість мовних засобів. Запропоновано модифікований метод нисхідного аналізу, в основі якого лежить модифіковане подання граматики мови (МБНФ) й об'єктно-зорієнтоване подання символів граматики. Модифікований метод дає змогу автоматизувати процес створення транслятора мови ДБД.

Система ДБД розглянута як засіб організації діяльності експерта в ІСППР. Розробленій системі ДБД дана якісна оцінка. Особливо підкреслено системний характер рішення задач у рамках теоретико-доказового підходу.

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

У висновках сформульовано основні положення, що виносяться на захист.

У додатках містяться специфікація мов ДБД, опис задачі обчислення мінімальних шляхів на графі, схема трансляції правил DLQ у SQL запити, матеріали впровадження результатів досліджень, зокрема, наведено опис задачі оптимізації мережі точок радіаційного контролю, декларативна модель задачі, та її відображення у систему SQL запитів, отриманих із застосуванням СДБД “DLQ”.

ВИСНОВКИ

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

1. Проведено аналіз концепції ДБД як засобу реалізації загальної задачі прийняття рішень, зокрема, задачі інтелектуального аналізу даних у сучасних ІСППР. Визначено проблеми створення експертної технології ІСППР. Показано необхідність системної організації засобів декларативного розв’язку задач.

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

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

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

5. Розроблено модифікацію напівбезпосереднього алгебраїчного методу обчислення логічної програми. В основу модифікованого методу покладено принцип мінімальності, а також принцип синтаксично керованої трансляції, що забезпечує одержання оптимізованого SQL подання логічної програми. Модифікований метод використовує план пошуку рішення, що суттєво підвищує ефективність обчислень в ДБД.

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

7. Створено діючий прототип СДБД “DLQ”, що був впроваджений для моделювання процесів розв'язку ЗПР та реалізації комплексу задач аналізу даних радіоекологічного моніторингу в умовах його дослідно-промислової експлуатації на Харківському державному міжобласному спецкомбінаті.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ

1. Буслик Н.Н., Копылов Г.В., Летучий Д.А. Об одном подходе к оптимизации программ логической базы данных // Вестник Харьковского государственного политехнического университета. – 2000. – № 117. – С. 9-13.

2. Буслик Н.Н., Летучий Д.А. Отрицательные литералы и вычислительная парадигма Дейталога // Проблемы бионики. Всеукраинский научн.-техн. сб. – 2001. – Вып. 55. – С. 3–8.

3. Буслик Н.Н., Летучий Д.А. Организация объектно–ориентированного предиктивного синтаксического анализатора // Проблемы бионики. Всеукраинский научн.-техн. сб. – 2002. – Вып. 56. – С. 21–25.

4. Буслик Н.Н., Летучий Д.А. Технология дедуктивных баз данных в системах поддержки принятия решений // Восточно-Европейский журнал передовых технологий. Харьков. – 2003. – № 6. – С 21–24.

5. Буслик Н.Н., Летучий Д.А. Об одном расширении вычислительной парадигмы Дейталога. // 5-й Международный молодежный форум "Радиоэлектроника и молодежь в XXI веке": Сборник научных трудов. Ч. 1. – Харьков: ХТУРЭ, 2001. – C. 432–433.

6. Летучий Д.А., Кузьменок А.Е. Архитектура дедуктивных систем управления базами данных. // 6-й Международный молодежный форум "Радиоэлектроника и молодежь в XXI веке": Сборник научных трудов. Ч. 2. – Харьков: ХНУРЭ, 2002. – C. 444–445.

7. Буслик Н.Н., Летучий Д.А., Копылов Г.В. О современных тенденциях развития языков обработки данных. // 8-я Международная конференция "Теория и техника передачи, приема и обработки информации" (Интегрированные информационные системы, сети и технологии) "ИИСТ-2002": Сборник научных трудов. – Харьков: ХНУРЭ, 2002. – C. 35–37.

8. Летучий Д.А. Расширенная модель отрицаний в дедуктивных базах данных. // Сборник тезисов конф. “Компьютеры. Программы. Интернет. 2003”. – Киев, 2003. – 44 с.

АНОТАЦІЯ

Летучий Д.О. Методи і засоби організації дедуктивних баз даних. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.04 – системний аналіз і теорія оптимальних рішень. Харківський національний університет радіоелектроніки. Харків, 2004.

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

Ключові слова: дедуктивна база даних, Дейталог, інтелектуальний аналіз даних, ІСППР, методи оптимізації пошуку рішень.

АННОТАЦИЯ

Летучий Д.А. Методы и средства организации дедуктивных баз данных. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.04 – системный анализ и теория оптимальных решений. Харьковский национальный университет радиоэлектроники. Харьков, 2004.

В работе рассмотрены вопросы создания технологии экспертных систем, проблемно-ориентированной на решение задач интеллектуального анализа данных в ИСППР, на основе применения дедуктивних баз данных. Развита концепция ДБД, предусматривающая глубокую интеграцию с технологией реляционных баз данных.

Первый раздел посвящен обзору декларативных языков ДБД. Определено множество конструктов, необходимых для реализации общей задачи принятия решений. Исследованы вопросы применимости систем ДБД в технологии ИСППР.

Во втором разделе вводится совокупность логико-предикативных моделей, включающих характерные для задач принятия решений конструкции. Исследованные модели положены в основу оригинальной версии языка ДБД – квантифицированного Дейталога (DLQ). Развита теория Дейталога с кванторными выражениями, в ней обоснован новый подход к описанию семантики логической программы ДБД (определена декларативно-процедурная семантика), доказана полнота и непротиворечивость теории Дейталога с кванторными выражениями. В рамках новой парадигмы кванторных выражений обоснованы такие расширения, как типизация переменных (в том числе, системного типа данных "счетчик"), функциональные термы (в частности, агрегатные функции), встроенные предикаты. Строго определены условия безопасности (сходимости вычислений) программ DLQ.

В третьем разделе рассмотрены методы анализа и оптимизации программ DLQ. Метод стратификации и метод статической фильтрации были модифицированы для оригинальной версии языка ДБД. Предложены граф зависимостей переменных и граф зависимостей аргументов как математические модели анализа свойств логической программы, в частности, для проверки условий безопасности. Разработан метод построения графа зависимостей аргументов на основе множества графов зависимостей переменных. Предложен принцип минимальности итеративных вычислений логической программы, выполнение которого исключает повторный вывод фактов. Показано, что процесс вычисления, нарушающий принцип минимальности, не сходится для программ DLQ с типом "счетчик". Определена схема трансляции программы DLQ в язык реляционных баз данных SQL. Разработан модифицированный полунепосредственный метод вычисления программ DLQ на основе принципа минимальности и алгоритма синтаксически управляемой трансляции правил логической программы в SQL запросы. Модифицированный метод управляется моделью поиска решений (планом вычислений).

В четвертом разделе полученные теоретические результаты используются для формирования единого математического и алгоритмического обеспечения системы управления ДБД. Рассматриваются принципы организации СДБД: связывание ДБД с реляционной БД, единство средств описания и управления данными, открытость языковых средств. Для автоматизации процесса создания транслятора языка ДБД (для реализации приципа открытости языковых средств) предложен модифицированный метод нисходящего анализа.

Развитая концепция системы ДБД нашла воплощение в разработанном в экспериментальной части диссертации действующем прототипе СДБД "DLQ". Использование разработки на ряде народнохозяйственных предприятий дало возможность решить следующие задачи: построение обобщенных декларативных моделей предметных областей, анализ сети точек радиационного контроля, оптимизация режима функционирования сети, анализ состава изделий, в частности, подетальная спецификация узлов и изделий, взаимозаменяемость детале-сборочных единиц.

Ключевые слова: дедуктивная база данных, Дейталог, интеллектуальный анализ данных, ИСППР, методы оптимизации поиска решений.

SUMMARY

Letuchy D.A. Methods and means for deductive databases organization. – Manuscript.

Candidate of technique sciences thesis in specialty 01.05.04 – system analysis and theory of optimal decisions. Kharkov national university of radioelectronics. Kharkov, 2004.

The questions of the creation of the technology of expert systems on the basis of deductive databases (DDB) which is oriented on the decision of intellectual data analysis problems in DSS have been examined. The concept of deductive database systems as means to decide badly formulated problems in modern technology of informational decision support systems has been developed. The set of logic-predicative models which have new, essential for describing decision problems constructions, has been developed. Methods of structural and semantic analysis have been improved. Seminaive calculation method has been modified to work with original logic-predicative models; it uses proposed principle of minimality of iterative calculations and is based on the developed translation scheme which represents DDB program into the system of SQL sentences. Principles of the organization of DDB systems have been proposed.

Keywords: deductive database, Datalog, intellectual data processing, DSS, optimization methods of the decision search.

Летучий Дмитро Олександровіч

Методи і засоби організації дедуктивних баз даних

Автореферат дисертації

Відповідальний за випуск Левикін В.М.

Підп. до друку р. Формат 6084 1/16. Папір офісний.

Друк на ризографі. Ум.– друк. арк. 1,05. Обл.-вид. арк. 0,9.

Зам. № . Тираж 100 прим.

Надруковано в навчально-науковому видавничо-поліграфічному центрі ХНУРЕ

61166, Харків, просп. Леніна, 14