Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 681.3:622.276

ЗАСТОСУВАННЯ ПРОЦЕДУРИ APPEND ПРИ АНАЛІЗІ АБСТРАКТНИХ ТИПІВ ДАНИХ МОДИФІКАЦІЙНИХ  ЗАПИТІВ

Шекета В.І.

Вступ. В даний час нафтогазова галузь має автоматизовані мікропроцесорні системи різних рівнів і типів, а також різні програмні комплекси для прогнозу нафтогазоносності, пошуку та розвідки родовищ нафти і газу, але масштаби та ефективність застосування ЕОМ для кожного рівня різні [1]. Впровадження нових інформаційних технологій на базі мікропроцесорних систем в нафтогазовій справі дає можливість суттєво змінити економіко-екологічний підхід до пошуково-розвідувальних робіт на нафту і газ .

В роботі [2] база знань інформаційної системи розглядається як набір інформаційних сутностей атомарних предикатів з деякого скінченого інформаційного простору Â. Всі зміни, що відбуваються в базі знань, розглядаються , як наслідок модифікаційних предикатних запитів , що генеруються інтелектуальною інформаційною системою відповідно до вказівок користувача. Основою самих запитів є набір модифікаційних предикатних правил. Розглядаються  два типи правил:

       ,          (1)

       ,            (2)

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

Порівняння різних технік і методик аналізу абстрактних типів даних в термінах точності, ефективності і загальності є досить важким завданням, оскільки такі техніки часто використовують різні методи аналізу, які  базуються на протилежних вихідних гіпотезах. Виконаний нами аналіз публікацій дозволяє виділити наступні методи: методи аналізу абстрактних типів даних і побудови на його основі процедури логічного висновку подібні до тих, які використовуються в функціональних мовах програмування високого рівня [3,4]; техніки аналізу на основі методів верифікації програм [5]; аналіз абстрактних типів на основі типованих графів [6]; техніки аналізу абстрактних типів на основі абстрактної інтерпретації[7–14].

Вихідним кроком підходу до аналізу абстрактних типів  даних на основі абстрактної інтерпретації , є вибір абстрактного домену, який визначає, як буде виконано присвоєння абстрактних типів термам. Формальні засоби опису базових типів не дозволяють обробляти залежності між типами. Деякі залежності абстрактних типів  серед попарно різних аргументів процедур можуть бути виражені через використання змінних типу в мовах програмування, що оперують із структурними типами даних. Це є стандартне рішення, описане зокрема в [5,7,10]. Подібну техніку використано також в рамках підходу, щодо регулярної апроксимації множин успішних рішень [9]. Проте, слід відмітити, що використання змінних типу не дозволяє виразити залежності між абстрактними типами даних із точки зору позиціювання аргументів  процедур. Тільки в роботах [7,8] показано приклад виключення випадку, який явним чином визначає залежності між типами. В [7] виконано оголошення абстрактного домену для аналізу базових типів. В даний роботі введено поняття типізованих програм, що значно звужує можливості застосування такого підходу. Крім того, оскільки змінні типів не використовуються, практичне застосування розроблених доменів є досить складним завданням. В роботі [8] автори виконують узагальнення техніки побудови домену POS для аналізу базовості до випадку абстрактних типів. Проте, коректність такого підходу не була підтверджена формальним доведенням. Більше того, використання змінних типу є в більшій мірі наслідком вибраного способу практичної реалізації, чим формальності теорії, що лежить в основі підходу. Стосовно роботи [2] недослідженим залишається питання  побудови  коректних методів аналізу абстрактних типів даних модифікаційних предикатних запитів.

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

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

 1) ; 2) ;

 3) ;  4) .

Означення 1. (Система обмежень для абстрактних типів даних). Нехай   – система абстрактних типів даних із в якості прототипу функторного відображення  . Системою обмежень для системи абстрактних типів даних  будемо вважати систему обмежень , де , ,- абстрактний оператор, F- функторний символ.   є замкнутою відносно операції  і  містить діагональні елементи

    , .        (3)

Означення 2.  Нехай дано

 і V, тоді:

 { є визначеним},                      (4)

                                             ,                                                    (5)

  .                                (6)

Означимо оператор абстрактної інтерпретації[15] :  наступним чином:

                                                                                                                             (7)

                                                                         (8)

                                                                    (9)

                                              (10)

Означення 3.  Нехай дано запит , введемо оператор еластичний оператор[15] : , як

        (11)

Означення 4. (Абстрактна аплікація). Нехай  і  дві системи обмежень:  і . Для заданого запиту  означимо , як запит, отриманий із Q через  заміну  обмежень в твердженнях запиту на їх абстрактні відповідники через . Подібним чином, якщо , тоді  є еластичним елементом[15], отриманим із Q через  заміну кожного обмеження  в твердженнях Q на .

Твердження 1.  Нехай  - система абстрактних типів , , ,-домен абстрактних логічних програм, ZT-змінна типу. Якщо  може бути одержано з О за допомогою процедури  резолюції[15] (тобто якщо існує спростування для  із  в якості обчислюваної підстановки), тоді  .

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

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

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

(12)

 
                          

                                      ,

де   і  дає нам обчислювальну підстановку

                                            для .                              (13)

Перший  крок пропонованої нами процедури виконання аналізу полягає в трансформації запиту в рамках введеного абстрактного синтаксису через використання класичної процедури Append()[5]. Результат  матиме вигляд

 або  .     (14)

 

Другий крок полягає у виконанні абстрагування  запиту (Означення 4) через відображення із Означення 6. При цьому ми будемо використовувати систему абстрактних типів, що містить поліморфні списки, числові типи даних і деякий абстрактний тип даних up. Таким чином ми також використаємо і процедуру .  Результат абстрагу-вання  матиме вигляд

 

 або  або

(15)

 

 

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

 

                                 (16)

 

Відмітимо, що ми виконали переіменування змінних  слідуючи означенню 3, хоча для цього була використана явна операція переіменування замість операції пошуку діагональних елементів і виконання циліндрифікації [15].

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

 

                                                                                            (17)

                         (18)

 

Далі, обчислимо 

 

                                                                                             (19)

 

Згідно означення 2  матимемо:

(20)

 
             

(21)

 

 

Слідуючи означенню 3, ми повинні переіменовувати запит  і виконати циліндрифіка-цію[15] по відношенню до змінних . Операція переіменування матиме своїм результатом

 

(22)

 

                                                  

.

 

Виконаємо операцію циліндрифікації

(23)

 

(24)

 

      (25)

 

Оскільки може бути показано, що , то ми маємо .

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

 

(26)

 

.

                   

.

(27)

 

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

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

 

                                                  .                                    (28)

 

Результатом такого оцінювання буде множина обмежень. Якщо предикат хиба може бути  одержаний в результаті застосування процедури резолюції до даного обмеження, то таке обмеження може бути вилучено із  подальшого розгляду. В нашому випадку обмеження О3, О6, О7 і О8 можуть бути видалені. Із решти чотирьох обмежень ми виведемо факт  . Це означає, що другий аргумент нами встановлено на відповідність сформованому виразу. Більше того, ті ж самі обмеження дозволяють нам вивести факт , що означає, що другий аргумент може бути також прив’язаний і до алгебраїчного виразу.  Множина обмежень, обчислених для запиту Q матиме вигляд:

Обмеження 1.:  ,,,,

                          ,

Обмеження 2.:  , , , ,

                        ,

Обмеження 3.:  ,,,

            ,,

Обмеження4.:  , ,,

                           , ,

Обмеження 6.: ,,

   ,,.

Обмеження 7.: ,,,

             ,,,

                          .

Обмеження 8.: , , ,

                          , , ,

                           .

Обмеження 9.: , , ,

                          , ,

                                      , .

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

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

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

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

 

In given paper the method of application of classic procedure Append is offered at implementation of analysis for abstract data types of predicate queries modification for the information  intellectual systems on the basis of databases and knowledgebases. The use of information representation in the form of logical negation, explicit representation of polymorphic dependencies between abstract data types, and the construction of abstract domains, on the formal-logical basis of theories of sequentially improving of domains and abstract interpretation is  the distinguishing features of offered approach .

 

1.                 Шекета В.І. Інформаційна система для прогнозування нафтогазоносних покладів. Дисертація на здобуття       наукового ступеня кандидата технічних наук. Херсон.–1999.-130с.

2.                 Шекета В.І. Модифікаційні предикатні запити, як інструмент підтримки діалогу з користувачем  в інформаційних системах на основі баз даних і знань. Вісник Тернопільського державного технічного університету.- 2003-Серія:Математичне моделювання. Том 8-№4 -2003- С.113-119.

3.                 Barbuti R., Giacobazzi R. A Bottom-up Polymorphic Type Inference in Logic Programming. Science of Computer Programming, 19(3).– 1992.–P.281–313

4.                 Apt K. R., Marchiori E. Reasoning about Prolog Programs: from Modes through Types to Assertions. Formal Aspects of Computing, 6(6A).–1994.P–743–765 .

5.                 Yardeni E., Shapiro E. A Type System for Logic Programs. Journal of Logic Programming, 10.–1991.–P.125–135

6.                 Hentenryck P., Cortesi A., Charlier B. Type Analysis of Prolog using Type Graphs. Journal of  Logic Programming, 22(3).–1995.–P.179–209

7.                 Codish M., Demoen B. Deriving Polymorphic Type Dependencies for Logic Programs Using Multiple Incarnations of Prop. In Proc. of the first International Symposium on Static Analysis, volume 864 of Lecture Notes in Computer Science. Springer-Verlag.–1994–P.281–296

8.                 Codish M., Lagoon V. Type Dependencies for Logic Programs Using ACI  Unification. In Proceedings of the 1996 Israeli Symposium on Theory of Computing and Systems, IEEE Press,June 1996.–P.136–145

9.                 Gallagher J., Waal D. A. Fast and Precise Regular Approximation of Logic Programs. In Pascal Van Hentenryck, editor, Proceedings of the Eleventh International Conference on Logic Programming,Santa Margherita Ligure, Italy, The MIT Press.–1994.–P.599–613

10.             Janssens G., Bruynooghe M.  Deriving Descriptions of Possible Values of Program Variables by means of Abstract Interpretation. Journal of Logic Programming, 13(2 & 3), 1992.–P.205–258

11.             Kifer M., Wu J.  A First Order Theory of Types and Polymorphism in Logic Programming. In IEEE Symposium on Logic in Computer Science.– 1991.

12.             12. Lunjin Lu. A Polymorphic Type Analysis in Logic Programs by Abstract Interpretation. Journal of Logic Programming, 36(1).–1998.–P.1–54

13.             Papadimitriou C. Computational Complexity. Addison-Wesley.–1994.

14.             Smaus J.-G., Hill P., King A. Mode Analysis for Typed Logic Programs. In Proc. of the LOPSTR'99 Workshop, Venice,Italy, September 1999.– P.163–170

15.             Шекета В.І. Аналіз еластичних семантик шаблонів виклику модифікаційних предикатних запитів // Вісник Тернопільського державного технічного університету / Технічні науки – 2004.-Том 9-№1.-С.117-122.

 





Ответы на вопросы [_Задать вопроос_]

Информационно-управляющие комплексы и системы

Теленик С.Ф., Ролік О.І., Букасов М.М., Андросов С.А. Генетичні алгоритми вирішення задач управління ресурсами і навантаженням центрів оброблення даних

Богушевский В.С., Сухенко В.Ю., Сергеева Е.А., Жук С.В. Реализация модели управления конвертерной плавкой в системе принятия решений

Бень А.П., Терещенкова О.В. Применение комбинированных сетевых методов планирования в судоремонтной отрасли

Цмоць І. Г., Демида Б.А., Подольський М.Р. Методи проектування спеціалізованих комп’ютерних систем управління та обробки сигналів у реально-му час

Теленик С.Ф., РолікО.І., Букасов М.М., РимарР.В., Ролік К.О. Управління навантаженням і ресурсами центрів оброблення даних при виділених серверах

Селякова С. М. Структура інтелектуальної системи управління збиральною кампанією

Еременко А.П., Передерий В.И. Принятие решений в автоматизированных системах с учетом психофункциональных характеристик оператора на основе генетических алгоритмов

Львов М.С. Алгоритм перевірки правильності границь змінення змінних у послідовних програмах

Ляшенко Е.Н. Анализ пожарной опасности сосновых насаждений в зоне Нижне-днепровских песков – самой большой пустыни в Европе

Кучеров Д.П., Копылова З.Н. Принципы построения интеллектуального автору-левого

Касаткина Н.В., Танянский С.С., Филатов В.А. Методы хранения и обработки нечетких данных в среде реляционных систем

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Применение когнитивного подхода для решения задачи поддержки принятия управленческих решений при ликвидации лесных пожаров

Гончаренко А.В. Моделювання впливу ентропії суб’єктивних переваг на прийняття рішень стосовно ремонту суднової енергетичної установки

Фарионова Н.А. Системный подход построения алгоритмов и моделей систем поддержки принятия решений при возникновении нештатных ситуаций

Биленко М.С., Серов А.В., Рожков С.А., Буглов О.А. Многоканальная система контроля качества текстильных материалов

Мотылев K.И., Михайлов M.В., Паслен В.В. Обработка избыточной траекторной информации в измерительно-вычислительных системах

Гончаренко А.В. Вплив суб’єктивних переваг на показники роботи суднової енергетичної установки

Гульовата Х.Г., Цмоць І.Г., Пелешко Д.Д. Архітектура автоматизованої системи моніторингу і дослідження характеристик мінеральних вод

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

ПотапенкоЕ.М., Казурова А.Е. Высокоточное управление упругой электромеханической системой с нелинейным трением.

Кузьменко А.С., Коломіц Г.В., Сушенцев О.О. Результати розробки методу еквівалентування функціональних особливостей fuzzy-контролерів

Кравчук А. Ф., Ладанюк А.П., Прокопенко Ю.В. Алгоритм ситуационного управления процессом кристаллизации сахара в вакуум-аппарате периодического действия с механическим циркулятором

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

Литвиненко В.И., Четырин С.П. Компенсация ошибок оператора в контуре управления следящей системы на основе синтезируемых вейвелет-сетей

Бардачев Ю.Н., Дидык А.А. Использование положений теории опасности в искусственных иммунных системах

Рожков С.О., Кузьміна Т.О., Валько П.М. Інформаційна база як основа для створення асортименту лляних виробів.

Ускач А.Ф., Становский А.Л., Носов П.С. Разработка модели автоматизированной системы управления учебным процессом

Мазурок Т.Л., Тодорцев Ю.К. Актуальные направления интеллектуализации системы управления процессом обучения.

Ускач А.Ф., Гогунский В.Д., Яковенко А.Е. Модели задачи распределения в теории расписания.

Сідлецький В.М., Ельперін І.В., Ладанюк А.П. Розробка алгоритмів підсистеми підтримки прийняття рішень для контролю якості роботи дифузійного відділення.

Пономаренко Л.А., Меликов А.З., Нагиев Ф.Н. Анализ системы обслуживания с различными уровнями пространственных и временных приоритетов.

Коршевнюк Л.О. Застосування комітетами експертів системи нечіткого логічного виводу із зваженою істинністю.. – С. 73 – 79.

Кирюшатова Т.Г., Григорова А.А Влияние направленности отдельных операторов и направленности всей группы на конечный результат выполнения поставленной задачи.

Петрушенко А.М., Хохлов В.А., Петрушенко І.А. Про підключення до мови САА/Д деяких засобів паралельного програмування пакету МРІСН.

Ходаков В.Е., Граб М.В., Ляшенко Е.Н. Структура и принципы функционирования системы поддержки принятия решений при ликвидации лесных пожаров на базе новых геоинформационных технологий.

Сидорук М.В., Сидорук В.В. Информационные системы управления корпорацией в решении задач разработки бюджета.

Нагорный Ю.И. Решение задачи автоматизированного расчета надежности иасуп с использованием модифицированного метода вероятностной логики

Козак Ю.А. Колчин Р.В. Модель информационного обмена в автоматизированной системе управления запасами материальных ресурсов в двухуровневой логистической системе

Гожий А.П., Коваленко И.И. Системные технологии генерации и анализа сценариев

Вайсман В.А., Гогунский В.Д., Руденко С.В. Формирование структур организационного управления проектами

Бараненко Р.В., Шаганян С.М., Дячук М.В. Аналіз алгоритмів взаємних виключень критичних інтервалів процесів у розподілених системах

Бабенко Н.И., Бабичев С.А. Яблуновская Ю.А. Автоматизированная информационная система управления учебным заведением

Яковенко А.Е. Проектирование автоматизированных систем принятия решений в условиях адаптивного обучения с учетом требований болонского процесса

Бараненко Р.В Лінеаризація шкали і збільшення діапазону вимірювання ємностей резонансних вимірювачів

Головащенко Н.В. Математичні характеристики шумоподібно кодованих сиг-налів.

Шерстюк В.Г. Формальная модель гибридной сценарно-прецедентной СППР.

Цмоць І.Г. Алгоритми та матричні НВІС-структури пристроїв ділення для комп'-ютерних систем реального часу.

Кухаренко С.В., Балтовский А.А. Решение задачи календарного планирования с использованием эвристических алгоритмов.

Бараненко Р.В., Козел В.Н., Дроздова Е.А., Плотников А.О. Оптимизация рабо-ты корпоративных компьютерных сетей.

Нестеренко С.А., Бадр Яароб, Шапорин Р.О. Метод расчета сетевых транзакций абонентов локальных компьютерных сетей.

Григорова А.А., Чёрный С. Г. Формирование современной информационно-аналитической системы для поддержки принятия решений.

Шаганян С.Н., Бараненко Р.В. Реализация взаимных исключений критических интервалов как одного из видов синхронизации доступа процессов к ресурсам в ЭВМ

Орлов В.В. Оценка мощности случайного сигнала на основе корреляционной пространственной обработки

Коджа Т.И., Гогунский В.Д. Эффективность применения методов нечеткой логики в тестировании.

Головащенко Н.В., Боярчук В.П. Аппаратурный состав для улучшения свойств трактов приёма – передачи информации в системах промышленной автоматики.