Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області
Представлено аналіз проблеми застосування CSP-концепції для виконання інтелектуального аналізу даних засобами технології Constraint Logic Programming. Введено формально-логічне обґрунтування процедури ефективного керування множиною обмежень на прикладі задачі нафтогазової предметної області In this...
Saved in:
| Date: | 2008 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/1493 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області / Л.І. Випасняк, Б.І. Шпакодрай, В.І. Шкета // Пробл. програмув. — 2008. — N 2-3. — С. 355-360. — Бібліогр.: 9 назв. — укp. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860046542638940160 |
|---|---|
| author | Випасняк, Л.І. Шпакодрай, Б.І. Шекета, В.І. |
| author_facet | Випасняк, Л.І. Шпакодрай, Б.І. Шекета, В.І. |
| citation_txt | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області / Л.І. Випасняк, Б.І. Шпакодрай, В.І. Шкета // Пробл. програмув. — 2008. — N 2-3. — С. 355-360. — Бібліогр.: 9 назв. — укp. |
| collection | DSpace DC |
| description | Представлено аналіз проблеми застосування CSP-концепції для виконання інтелектуального аналізу даних засобами технології Constraint Logic Programming. Введено формально-логічне обґрунтування процедури ефективного керування множиною обмежень на прикладі задачі нафтогазової предметної області
In this paper the analysis of CSP conception implementation problem for intelligible data analysis by means of Constraint Logic Programming is presented and formal logical substantiation of effective control routine for constraints set is introduced on the base of example data from oil&gas subject domain.
|
| first_indexed | 2025-12-07T16:58:29Z |
| format | Article |
| fulltext |
Моделі і засоби систем баз даних і знань
© Л.І. Випасняк, Б.І. Шпакодрай, В.І. Шекета, 2008
ISSN 1727-4907. Проблеми програмування. 2008. № 2-3. Спеціальний випуск 355
УДК 004.942
ІМПЛЕМЕНТАЦІЯ CSP-КОНЦЕПЦІЙ ДЛЯ ІНТЕЛЕКТУАЛЬНОГО
АНАЛІЗУ ДАНИХ НАФТОГАЗОВОЇ ПРЕДМЕТНОЇ ОБЛАСТІ
Л.І. Випасняк, Б.І. Шпакодрай, В.І. Шекета
Івано-Франківський національний технічний університет нафти і газу,
76019, Івано-Франківськ, вул. Карпатська, 15/1416.
Тел.: +38 097 988 6938, факс +38 034–224 2139,
e-mail: lyubic@gmail.com
Представлено аналіз проблеми застосування CSP-концепції для виконання інтелектуального аналізу даних засобами технології
Constraint Logic Programming. Введено формально-логічне обґрунтування процедури ефективного керування множиною обмежень
на прикладі задачі нафтогазової предметної області.
In this paper the analysis of CSP conception implementation problem for intelligible data analysis by means of Constraint Logic
Programming is presented and formal logical substantiation of effective control routine for constraints set is introduced on the base of
example data from oil&gas subject domain.
Вступ
Одна з актуальних проблем штучного інтелекту – проблема задоволення обмежень (CSP – constraint
satisfaction problem) [1], яка має ряд застосувань: прогнозування, розподілення ресурсів, планування,
розміщення ресурсів та ін. Наукові пошуки в області CSP базуються на класичних задачах штучного інтелекту,
мовах програмування штучного інтелекту, абстрактних обчисленнях, теоріях логіки. В першому наближенні
обмеження можна розглядати як прості логічні відношення між кількома невідомими чи змінними які
набувають значення з своїх доменів. Обмеження таким чином розділяє можливі значення, які змінні можуть
набувати. Вони представляють деяку часткову інформацію про змінні. Формалізовано проблема задоволення
обмежень може бути представлена кортежом ),,( ConstrDX [2], яка складається з множини змінних
nixX i .1},{ == , скінченних множин iD їх можливих значень (доменів), niDD i ,1},{ == , і множини обмежень
які обмежують значення, що змінні можуть одночасно приймати niConstrConstr i ,1},{ == . Розв’язком CSP є
набір значень з відповідних доменів для кожної змінної, таких щоб задовольнялося кожне накладене
обмеження. Розрізняють пошук тільки одного розв’язку; всіх розв’язків; оптимального розв’язку[3].
Обмеження мають ряд властивостей: можливість описувати часткову інформацію; обмеження не є
напрямленими; обмеження мають декларативний характер, тобто можуть описувати відношення без опису
обчислювальних процедур; обмеження адитивні, тобто порядок їх виклику не є суттєвим; спільні обмеження
можуть використовуватися для розділених змінних.
Проблему задоволення обмежень (над скінченними доменами) типово розв’язують використовуючи
алгоритми пошуку. Найбільш часто вживані алгоритми – це форми бектрекінгу (backtracking), поширення
обмежень (constraint propagation), та локального пошуку (local search). Як відомо, бектрекінг – це рекурсивний
алгоритм, що підтримує часткове присвоєння змінних. На кожному кроці, вибраній змінній присвоюються всі
можливі значення, які вона може отримати. Для кожного отриманого значення використовується послідовність
часткового присвоєння з накладеними обмеженнями які верифікуються через рекурсивний виклик. Коли всі
значення будуть верифіковані, задається рекурсивне повторення. В базових імплементаціях бектрекінгу для
CSP, виконуюча послідовність означається як процес задоволення всіх обмежень для ініціалізованих змінних.
Для концепції CSP існує кілька імплементацій: backmarking – реалізація, що дозволяє покращити ефективність
перевірки послідовності, backjumping – зберегти частину множини пошуку в вигляді розділених змінних, look-
ahead – використовувати ефект передбачення вибору змінних чи їх послідовностей і використовується при
виконанні задоволення обмежень у випадку розбиття загальної CSP задачі на ряд підзадач. Концепція
поширення обмежень (constraint propagation) – це методи, що використовуються, для модифікації проблеми
задоволення обмеження у вигляді локальної послідовності, умови якої пов’язані з послідовністю групи змінних
чи обмежень. Технологія поширення обмежень має застосування у вигляді кількох кроків. На першому кроці
початкова задача перетворюється на еквівалентну, яка є простішою для вирішення. На другому кроці
виконується задоволення обмежень або доводиться неможливість задоволення системи обмежень. Найбільш
вживаними формами локальної послідовності для поширення обмежень є: дугові послідовності, гіпер-дугові
послідовності, шляхові послідовності[3]. Найбільш оптимальний метод поширення обмеження – алгоритм AC-
3[2]. З другого боку методи локального пошуку що використовуються є алгоритмами неповного задоволення
обмежень. Тобто вони, можуть, знайти вирішення проблеми, а можуть видати помилку навіть у випадку коли
проблема є такою, що не може бути розв’язана. Суть їхнього функціонування близька до ітераційного методу,
Моделі і засоби систем баз даних і знань
356
тобто поступова зміна початкових значень змінних з метою задоволення накладених обмежень. На кожному
кроці велика кількість змінних з модифікованими значеннями приводить до збільшення числа обмежень, що
були задоволені даним присвоєнням. В практичних імплементаціях локальний пошук працює ефективно, коли
зміни вносяться не тільки базовим алгоритмом пошуку а ще й деякими альтернативними алгоритмами. Тобто
реально діючі алгоритми є гібридними за своєю структурою [1,2]. Правила керування обмеженнями [3]
спочатку означалися як формалізм для специфікації розв’язувачів обмежень. Пізніше відбулося їхнє
вбудовування в логічне програмування. Виділяються два типи правил керування обмеженнями. Правила
першого типу задаються згідно умови, що множина обмежень є еквівалентною до деякої іншої множини.
Правила другого типу задаються згідно умови, що з однієї множини обмежень слідує інша множина. В теорії
constraint satisfaction problem (CLP), що підтримує правила виведення з обмеженнями можемо використати ці
правила для специфікування модифікації множини обмежень, і можливого додавання обмежень до цієї
множини.
Отже, виконаний аналіз літературних джерел показує актуальність проблеми інтелектуалізації
інформаційно-пошукових задач шляхом ефективного керування множиною обмежень. Проте невирішеними
залишається ряд проблем ефективного керування множиною накладених обмежень засобами абстрактних
логічних програм з обмеженнями та їх модифікацій.
Мета роботи – введення формально-логічної процедури для ефективного керування множиною
обмежень накладених на задану пошукову задачу, та їх ефективне використання з точки зору концепції
constraint logic programming.
З точки зору теорії абстрактної імплементації проблема задоволення обмеження в обмеженому домені є
NP – повною проблемою [2]. Тобто можемо застосовувати контексти обмежень і формулювати результуюче
дерево рішень. Деякі дослідження показують існуюче співвідношення проблеми задоволення обмеження і
абстрактних теорій побудованих на скінченних моделях. З другого боку, семантика CLP[4] може бути
сформульована в термінах віртуального інтерпретатора, що підтримує пари ConstrSetGoal, під час виконання
програми. Перший елемент (Goal – ціль) називається поточною ціллю, другий елемент називається множиною
обмежень, що накладається на процес задоволення цілі. Поточна ціль містить літерали, які інтерпретатор
намагається довести і також може містити обмеження, які він намагається задовольнити. Множина обмежень
містить всі обмеження, які інтерпретатор розглядає як такі, що можуть бути задоволені на даний момент часу.
Після вибору початкової цілі множина обмежень є порожньою. Інтерпретатор починає свою роботу з видалення
першого елемента поточної цілі і його аналізу. В результаті даного аналізу можемо одержати успішне або
неуспішне завершення програми. Даний аналіз може включати в себе також рекурсивні виклики і додавання
нових літералів до поточної цілі і нових обмежень до множини обмежень. Інтерпретатор починає працювати в
зворотному напрямі якщо генерується переривання про хибне завершення. Успішне завершення генерується
якщо поточна ціль є порожньою і множина обмежень є такою, що задовольняється. Після того, як видалили
літерал з заголовку цілі, виконується перевірка чи це є обмеження чи літерал. Якщо це є обмеження то воно
додається до множини обмежень. Якщо це літерал то вибирається твердження, заголовок якого має той самий
предикат що й вибраний літерал. Це твердження перезаписується через заміну змінних новими змінними.
Результат цього процесу називається новим варіантом твердження. Тіло нового варіанта твердження
розміщається в заголовку цілі.
Під час виконання цієї операції виконується ряд контрольних перевірок, зокрема множина обмежень
перевіряється на консистентність кожного разу коли додається нове обмеження. В загальному випадку
перевірка множини обмежень є така, що вона не може бути задоволена, має виконуватися алгоритмом
бектрекінгу, хоча така перевірка, на кожному кроці не є ефективною для загального процесу. З цієї причини
використовується аналізатор часткового задоволення. На практиці можливість задоволення множини обмежень
перевіряється на основі методів, що спрощують множину обмежень, тобто виконують її переписування в
еквівалентну форму, але яка є простішою для розв’язання. Ці методи можуть, але не завжди, доводити не
можливість задоволення множини обмежень. Вважається, що інтерпретатор довів істинність цілі, якщо поточна
ціль порожня і множина обмежень є така, що не містить фактів які можуть бути інтерпретовані як не
можливість задоволення цілі.
Наслідком виконання описаної процедури є поточна множина або спрощена поточна множина обмежень.
Дана множина може включати обмеження, вигляду i
i
C
DX (де ni ,1= , iC – обмеження накладені на змінні iX з
домену iD ), що змушують змінні приймати певні значення, але можуть включати також обмеження
j
j
C
D
X , що
виконують прив'язування змінних до певного діапазону без присвоєння їм певного значення.
Формально семантика CLP позначається в термінах послідовних доведень [4]. Для цього
використовується представлення пар ціль/множина обмежень ConstrSetGoal, і такий перехід у процесі
доведення позначається як tConstrSelGoaConstrSetGoal ′′<< ,, . Така пара описує можливі переходи з стану
ConstrSetGoal, в tConstrSelGoa ′′, . Згідно [3, 4] перехід можливий в трьох випадках:
� елемент oalG – обмеження onstrÑ , тоді }{\ ConstrGoallGoa =′ , }{ConstrConstrSettConstrSe ∪=′ ;
тобто обмеження може бути перенесено з цілі до множини обмежень;
Моделі і засоби систем баз даних і знань
357
� елемент oalG – літерал ),...,( 1 nttL тоді існує твердження, що може бути модифіковано використанням
нових змінних, таких як BttL n <<′′ ),...,( 1 , oalG є lGoa ′ з ),...,( 1 nttL і замінюються вони таким чином
Btttt nn ,,...,11 == і ConstrSettConstrSe =′ ; іншими словами літерал може бути замінений тілом нового варіанта
твердження, що має ті самі предикати в заголовку через додавання тіла нового варіанта і відповідності термів у
цілі;
� ConstrSet і tConstrSe ′ – еквівалентні згідно певної семантики обмежень.
Отже, послідовність доведення розглядається як послідовність пар ConstrSetGoal, , ціль oalG може
бути верифікована, якщо існує таке доведення з 0Goal, в ConstrSet,0 з деякої множини обмежень
ConstrSet , що може бути задоволена. Ця семантика формалізує подальший розвиток ідеї інтерпретації, як
явного вибору літералів з цілі, для обробки тверджень, для заміни літералів. Іншими словами, ціль є доведеною
в певній семантиці, якщо існує послідовність виборів літералів і тверджень серед множини можливих інших
тверджень, що ведуть до порожньої цілі, множини обмежень, що можуть бути задоволені. Фактичний процес
інтерпретації елементів цілі слідує порядку LIFO: тобто елементи додаються до заголовка цілі і обробляються з
заголовка цілі. Вони відповідно вибирають також твердження з другого правила відповідно до порядку в якому
вони записані і переписують множину обмежень коли виконується її верифікація. Іншим можливим варіантом
інтерпретації є заміна множини обмежень на еквівалентну. Така заміна обмежується тільки певними
специфічними методами як, наприклад поширенням обмежень. Семантика CLP – параметрична, не тільки з
точки зору вигляду обмежень, що використовуються, але також з точки зору методів перезапису множини
обмежень. Специфічний метод, що використовується на практиці дозволяє замінити множину обмежень такою,
яка простіша для задоволення. Якщо множина обмежень така, що не може бути задоволена, то таке спрощення
дозволить виявити таку можливість в деяких випадках, про те не у всіх. Результат оцінювання цілі CLP
програми означається через доведення цілі. В даному випадку можна стверджувати, що існують деякі
доведення з початкової пари до деякої пари, для якої ціль є порожньою. Множина обмежень для другої пари
розглядається як наслідок такого оцінювання. Така ситуація існує тому, що множина обмежень містить всі
обмеження, для яких було припущено, що вони є такі, що можуть бути задоволені для досягнення поставленої
цілі. Іншими словами, ціль доведена для всіх змінних оцінювання, що задовольняють дані обмеження.
Кожна CLP програма, як логічна програма, що складається з правил, може бути модифікована з метою
підвищення ефективності. Першим правилом у такій програмі є процедура, що задає опис літералів, воно має
бути поміщено після певної множини обмежень для помічених літералів, що згенеровані в множині обмежень.
Тобто, i
i
C
DXXlabelingX ),()( <<Π є еквівалентною до )(,)( XlabelingXX i
i
C
D<<Π , де ()labeling – це процес
маркування. Пошук виконується коли інтерпретатор зустрічає маркуючий літерал у множині обмежень, що не
містить обмеження i
i
C
DX . Як результат можемо одержати генерацію розв’язків, таких, що задовольняють j
j
C
DX
які пізніше будуть встановлені як такі, що не задовольняють дане обмеження. З іншого боку, в другому
формулюванні пошук здійснюється тільки тоді коли обмеження знаходиться в початковій множині обмежень.
Як результат, алгоритм пошуку буде повертати тільки ті рішення, що зменшують область пошуку.
Друга модифікація яка збільшує ефективність є розміщення обмежень та літералів у тілі тверджень. Тоді
i
i
C
DXXX ),()( 21 Π<<Π є в принципі еквівалентна до )(,)( 21 XXX i
i
C
D Π<<Π . Проте перший запис вимагає певних
обчислень. Наприклад, якщо множина обмежень містить обмеження i
i
C
DX , тоді інтерпретатор рекурсивно
оцінить )(2 XΠ в обох випадках. Приклад правил: )(|)()( 321 XXX ΠΠ⇔Π ; )(|)()( 321 XXX ΠΠ⇒Π .
Третім способом модифікації є додавання залишкових обмежень. Якщо програміст знає, що рішення
програми задовольняє певні обмеження, то вони можуть включати обмеження, що спричиняє незв’язність
множини обмежень найшвидшим способом.
Практичний досвід імплементації інформаційних систем для нафтогазової предметної області [5,6] та
досвід практичної експлуатації інформаційних інтелектуальних систем побудованих на основі концепції
абстрактних логічних програм показує, що користувач стикається з проблемою накладання та задоволення
обмежень навіть у випадку найпростіших систем даного класу, зокрема експертних систем: COLLECTOR,
PLAST, PRYPLUV; які розроблені на кафедрі програмного забезпечення автоматизованих систем Івано-
Франківського національного технічного університету нафти і газу (www.nung.edu.ua, www.pz.nung.edu.ua) під
керівництвом доктора технічних наук, професора, В.М. Юрчишина, та використовуються в профільних
підприємствах галузі. Тому зручним є виконання представлення множини обмежень у вигляді баз знань
( ConstrSet
BK ). Згідно представлення логічних програм у вигляді правил, що модифікуються[7] враховуючи
послідовності ConstrSetGoal, , запишемо:
)(,...),(),(,...),()( 11
,
m
ConstrSet
B
ConstrSet
Bl
ConstrSet
B
ConstrSet
B
ConstrSetGoal
ConstrSet
B pKpKoKoKoK
OutOutInInIn
<< , (1)
)(,...),(),(,...),()( 11
,
m
ConstrSet
B
ConstrSet
Bl
ConstrSet
B
ConstrSet
B
ConstrSetGoal
ConstrSet
B pKpKoKoKoK
OutOutInInOut
<< , (2)
Моделі і засоби систем баз даних і знань
358
де ,,, Opoo ii ∈ << – дескриптор модифікації. Розглядатимемо базу знань як набір інформаційних сутностей
атомарних предикатів з деякого скінченого інформаційного простору О [8, 9]. Всі зміни, що відбуватимуться в
базі знань, будемо розглядати, як наслідок модифікаційних предикатних запитів, що генеруються ІС відповідно
до вказівок користувача. Основою самих запитів є набір модифікаційних предикатних правил. Основна ідея
такого запису правил у тому, що )(oK
InConstrSet
B означає, що деяке обмеження o має бути включено в базу знань
обмежень ConstrSet
BK , а )(oK
OutConstrSet
B означає, що o – має бути виключено з бази знань обмежнь.
Введемо поняття необхідної модифікації, яка буде описувати всі операції ()
InConstrSet
BK і ()
OutConstrSet
BK , що
спричиняються модифікаційним запитом для вихідної бази знань обмежень ConstrSet
BK . Мета такої модифікації –
ефективне керування множиною обмежень, щоб отримати таке наповнення бази знань яке може бути
задоволено найпростішим (оптимальним) способом.
Означення 1. Нехай
ConstrSet
MQ – модифікаційний предикатний запит. Позначимо )( ConstrSet
M
ConstrSet
nm Qλ
необхідні модифікації для ConstrSet
BK . )( ConstrSet
M
ConstrSet
nm Qλ фактично є найменшою моделлю для
ConstrSet
MQ , якщо
)( ConstrSet
M
ConstrSet
nm Qλ розглядати, як Хорн-програму
ConstrSet
MQ побудовану з незалежних атомарних предикатів
вигляду )(oK
InConstrSet
B і )(oK
OutConstrSet
B . Нехай, наприклад, модифікаційний предикатний запит
ConstrSet
MQ має вигляд
)}()(),()()({
,,,
oKrKoKpKoK
OutOutInOutIn ConstrSet
B
ConstrSetGoal
ConstrSet
B
ConstrSet
B
ConstrSetGoal
ConstSet
B
ConstrSetGoal
ConstrSet
B <<<<<< , тоді
)}(),({)( pKoKQ
OutIn ConstrSet
B
ConstrSet
B
CosntrSet
M
ConstrSet
nm =λ .
В результаті виконання модифікаційних предикатних запитів база знань обмежень ConstrSet
BK змінюється,
але статус деяких елементів залишається незмінним. При створенні набору модифікаційних правил ми власне
зазначаємо тільки опис того, чи слід змінити певні елементи. Якщо для певного елемента немає правила
модифікації, то відповідно, згідно принципу інерції, він не буде змінюватися в ході виконання модифікацій.
Тобто, як і показує досвід практичної експлуатації систем COLLECTOR, PLAST, PRUPLUV на певних етапах
роботи даних систем користувач має справу з інертними обмеженнями. Проблема усунення інертних обмежень
з бази знань обмежень буде однією з наступних тем досліджень даного напряму, що виконуються на кафедрі.
Отже, множину всіх модифікаційних літералів, що описують елементи бази знань ConstrSet
BK , статус яких
не змінюється в процесі переходу від бази знань
1ConstrSet
BK до бази знань
2ConstrSet
BK ,
ConstrSet
MQ і
21
,
ConstrSet
B
ConstrSetGoal
ConstrSet
B KK << можна розглядати множину інерції для
1ConstrSet
BK ,
2ConstrSet
BK і означати, як:
}.:{}:)({),(
212121 ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
Bi KKoKKKooKKKO
OutIn
∪∉∪∩∈=
Означення 2. Залишком для
ConstrSet
MQ стосовно баз знань обмежень ),(
21 ConstrSet
B
ConstrSet
B KK
21
, ConstrSet
B
ConstrSet
B KK
MQ
будемо називати новий модифікаційний запит, який отримується із
ConstrSet
MQ шляхом видалення із тіла кожного
модифікаційного правила в
ConstrSet
MQ всіх модифікаційних літералів, які належать також і ),(
21 ConstrSet
B
ConstrSet
Bi KKO .
Означення 3. Базу знань
2ConstrSet
BK будемо називати
ConstrSet
MQ – модифікацією для
1ConstrSet
BK , якщо
множина необхідних модифікацій для
21
, ConstrSet
B
ConstrSet
B KK
MQ є когерентною і якщо
)(
2112 , ConstrSet
B
ConstrSet
B KK
M
ConstrSet
nm
ConstrSet
B
ConstrSet
B QKK λo= .
Розглянемо наступний приклад.
Приклад 1. Припустимо, нам слід будувати процедуру логічного висновку для інтелектуальної системи
на основі баз даних і знань нафтогазової предметної області PLAST виходячи із чотирьох характеристик
нафтогазоносної породи:
}._,,,{ опорукоефіцієнтьпроникністьнасиченістпористістьConstrSet =
Причому, виходячи із досвіду експертів за опрацюванням даних характеристик породи, будемо мати
справу із певним набором додаткових обмежень. А саме:
Constr1: Характеристики “пористості” і “насиченості” – найбільш продуктивна для виконання процедури
логічного висновку тому одна із них має обов’язково бути присутньою у вихідній базі знань
InitialConstrSet
BK .
Constr2: Використання характеристики “проникність” – неефективна без одночасного опрацювання
характеристики “коефіцієнт_опору”. Це так звані парні характеристики і якщо в
InitialConstrSet
BK не буде включено
характеристику “коефіцієнт_опору”, то не слід включати і характеристику “проникність”.
Constr3: Спільне використання характеристик “коефіцієнт_опору” і “проникність” не є ефективним,
оскільки вони мають різну фізичну природу і методики їх вимірювання базуються на різних принципах.
Моделі і засоби систем баз даних і знань
359
Constr4: Неефективне також спільне використання характеристик “насиченість”, “коефіцієнт_опору”
відповідно до причин, викладених у пункті 3.
Згідно перелічених обмежень як початкового складу бази знань приймемо
},{ ьпроникністпористістьK
InitialConstrSet
B = .
Прагнемо сформувати базу знань обмежень ConstrSet
BK , яка б задовольняла всім чотирьом накладеним об-
меженням. Таким чином у термінах вищевведених означень отримуємо },{
1
ьпроникністпористістьK ConstrSet
B = .
Побудуємо модифікаційний предикатний запит
ConstrSet
MQ :
),()({
,
ïîðèñò³ñòüKüíàñè÷åí³ñòK
OutIn ConstrSet
B
ConstrSetGoal
ConstrSet
B <<
),()(
,
üíàñè÷åí³ñòKïîðèñò³ñòüK
OutIn ConstrSet
B
ConstrSetGoal
ConstrSet
B <<
),()_(
,
üïðîíèêí³ñòKîïîðóêîåô³ö³ºíòK
InIn ConstrSet
B
ConstrSetGoal
ConstrSet
B <<
),_()(
,
îïîðóêîåô³ö³ºíòKüïðîíèêí³ñòK
OutOut ConstrSet
B
ConstrSetGoal
ConstrSet
B <<
),_()(
,
îïîðóêîåô³ö³ºíòKïîðèñò³ñòüK
InOut ConstrSet
B
ConstrSetGoal
ConstrSet
B <<
)}()_(
,
üíàñè÷åí³ñòKîïîðóêîåô³ö³ºíòK
InOut ConstrSet
B
ConstrSetGoal
ConstrSet
B <<
Покажемо, що }{
2
пористістьK ConstrSet
B = є
ConstrSet
MQ – модифікацією для
1ConstrSet
BK . Виходимо з того, що
}_,,,{ опорукоефіцієнтьпроникністьнасиченістпористістьO = .
Тоді
)}_(),(),({),(
21
опорукоефіцієнтKьнасиченістKпористістьKKKO
OutOutIn ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
Bi = ,
)(),(),({
21
,
пористістьKпористістьKьнасиченістKQ
InOutInConstrSet
B
ConstrSet
B ConstrSet
B
ConstrSet
B
ConstrSet
B
KK
M =
)(),()_(
,,
üïðîíèêí³ñòKüïðîíèêí³ñòKîïîðóêîåô³ö³ºíòK
OutInIn ConstrSet
B
ConstrSet
B
ConstrSetGoal
ConstrSet
B
ConstrSetGoal
<<<<
),_()(
,,
îïîðóêîåô³ö³ºíòKïîðèñò³ñòüK
InOut ConstrSet
B
ConstrSetGoal
ConstrSet
B
ConstrSetGoal
<<<<
)}()_(
,
üíàñè÷åí³ñòKîïîðóêîåô³ö³ºíòK
InOut ConstrSet
B
ConstrSetGoal
ConstrSet
B << .
Звідки
)}.(),({)(
21
,
ьпроникністKпористістьKQ
OutInConstrSet
B
ConstrSet
B ConstrSet
B
ConstrSet
B
KK
M
ConstrSet
nm =λ
Збережена властивість когерентності
)(
2112 , ConstrSet
B
ConstrSet
B KK
M
ConstrSet
nm
ConstrSet
B
ConstrSet
B QKK λo= .
Так показали, що
2ConstrSet
BK є
ConstrSet
MQ – модифікація для
1ConstrSet
BK .
Тепер покажемо, що
ConstrSet
MQ
BK є
ConstrSet
MQ – модифікацією для
InitialConstrSet
BK . Припустимо, що правила з
модифікаційного запиту
ConstrSet
MQ є такими, що не є всі одночасно хибними. Тоді
ConstrSet
ME є найменшою
моделлю для ConstrSet
M
EIn
R
EInitial
R Q
ConstrSet
M
ConstrSet
M ∪>∆<∪∆ ))(()( . Для того, щоб обчислити залишок
ConstrSet
MQ
B
InitialConstrSet
B KK
ConstrSet
MQ
, для
ConstrSet
MQ маємо видалити з тіла кожного модифікаційного правила всі атомарні
предикати )(oK
InConstrSet
B , такі, що
ConstrSet
B
Initial Q
B
ConstrSet
B KKo ∩∈ , і всі атомарні предикати )(oK
OutConstrSet
B , такі, що
ConstrSet
B
Initial Q
B
ConstrSet
B KKo ′∩′∈ . Це будуть ті атомарні предикати, що є істинними в
ConstrSet
ME , завдяки множині
>∆<
ConstrSet
MEIn
R )( . Тому
ConstrSet
ME залишається найменшою моделлю модифікованого запиту
ConstrSet
BQ
B
InitialConstrSet
B
ConstrSet
M
ConstrSet
M
KK
ConstrSet
M
EIn
R
EInitial
R Q
,
))(()( ∪>∆<∪∆ .
Необхідна модифікація )(
,
ConstrSet
BQ
B
InitialConstrSet
B KK
ConstrSet
M
ConstrSet
nm Qλ – найменша модель для ConstrSet
BQ
B
InitialConstrSet
B KK
ConstrSet
MQ
,
.
Розглянемо дві множини:
)}()(:{
,
ConstrSet
BQ
B
InitialConstrSet
B
In
KK
ConstrSet
M
ConstrSet
nm
ConstrSet
BIn QoKoO λ∈= ,
Моделі і засоби систем баз даних і знань
360
)}()(:{
,
ConstrSet
BQ
B
InitialConstrSet
B
Out
KK
ConstrSet
M
ConstrSet
nm
ConstrSet
BOut QoKoO λ∈= .
Тоді запит ConstrSet
BQ
B
InitialConstrSet
B
ConstrSet
M
ConstrSet
M
KK
ConstrSet
M
EIn
R
EInitial
R Q
,
))(()( ∪>∆<∪∆ складається із трьох незалежних
частин, причому залишок ConstrSet
BQ
B
InitialConstrSet
B KK
ConstrSet
MQ
,
більше не містить атомарних предикатів, які б входили в інші
дві частини. Множина
ConstrSet
ME буде складатися з:
}:)({}:)({
InitialOutInitialIn ConstrSet
B
ConstrSet
B
ConstrSet
B
ConstrSet
B KooKKooK ′∈∪∈ ∈∈ ,
}:)({}:)({
InitialConstrSet
B
OutInitialConstrSet
B
In ConstrSet
B
Q
B
ConstrSet
B
ConstrSet
B
Q
B
ConstrSet
B KKooKKKooK ′∩′∈∪∩∈ ∈∈ ,
}:)({}:)({ Out
ConstrSet
BIn
ConstrSet
B OooKOooK
OutIn
∈∪∈ ∈∈
на даній основі, робимо висновок, що:
In
ConstrSet
B
Q
B
ConstrSet
M
ConstrSet
B
Q
B OKKEoKoK
InitialConstrSet
B
InConstrSet
B ∪∩=∈= )(})(:{ ,
Out
ConstrSet
B
Q
B
ConstrSet
M
ConstrSet
B
Q
B
Q
B OKKEoKoKOK
InitialConstrSet
B
OutConstrSet
B
ConstrSet
B ∪′∩′=∈==′ )(})(:{\ .
Отже множина необхідних модифікацій )(
,
ConstrSet
BQ
B
InitialConstrSet
B KK
ConstrSet
M
ConstrSet
nm Qλ є когерентною. Також
OutIn
ConstrSet
B
Q
B OOKK
InitialConstrSet
M \)( ∪= . Звідки слідує, що
ConstrSet
MQ
BK є
ConstrSet
MQ – модифікацією для початкової
множини обмежень
InitialConstrSet
BK .
Висновки
Отже, в даному дослідженні введено формально-логічне обґрунтування процедури ефективного
керування множиною обмежень на прикладі задачі нафтогазової предметної області. Представлено аналіз
проблеми застосування CSP-концепцій для виконання інтелектуального аналізу даних засобами технології
Constraint Logic Programming для інформаційно-пошукової задачі з чотирма накладеними обмеженнями.
Подальші дослідження будуть напрямлені на імплементацію отриманих формально-логічних результатів
на основі шаблонів JCL (Java Constraint Library).
1. http://www.bracil.net/edward/FCS.html
2. http://en.wikipedia.org/wiki/Constraint_satisfaction
3. http://kti.mff.cuni.cz/~bartak/constraints/systems.html
4. http://en.wikipedia.org/wiki/Constraint_logic_programming
5. Шекета В.І. Інформаційна система для прогнозування нафтогазоносних покладів // Дис. канд. техн. наук: 05.13.06 / Херсон. держ. техн.
ун-т. – Херсон, 1999. – 130 с.
6. Юрчишин В.М. Наукові основи застосування інформаційних технологій при управлінні процесами розробки нафтогазових родовищ
//Дис. д-ра техн. наук: 05.15.06 / Івано-Франків. нац. техн. ун-т нафти і газу. – Івано-Франківськ, 2006. – 353 с.
7. Шекета В.І. Модифікаційні предикатні запити // Проблеми програмування. – 2004. – № 2-3. – С. 339 – 43.
8. Шекета В.І. Використання необхідної модифікації, як інструменту трансформації баз знань нафтогазової предметної області // Наук.
пр. Донецьк. нац.–техн. ун. – Випуск 70. Сер.: "Інформатика, кібернетика та обчислювальна техніка" – Донецьк: ДонНТУ, 2003. –
С. 39–46.
9. Шекета В.І., Бестильний М.Я.,Храбатин Р.І. Інтерпретація предикатних запитів на основі премоноїдної дедукції в семантичній
стратегії і системі обмежень // Проблеми програмування. – 2006. – № 2-3. – С. 436 – 444.
|
| id | nasplib_isofts_kiev_ua-123456789-1493 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:58:29Z |
| publishDate | 2008 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Випасняк, Л.І. Шпакодрай, Б.І. Шекета, В.І. 2008-07-31T15:06:31Z 2008-07-31T15:06:31Z 2008 Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області / Л.І. Випасняк, Б.І. Шпакодрай, В.І. Шкета // Пробл. програмув. — 2008. — N 2-3. — С. 355-360. — Бібліогр.: 9 назв. — укp. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1493 004.942 Представлено аналіз проблеми застосування CSP-концепції для виконання інтелектуального аналізу даних засобами технології Constraint Logic Programming. Введено формально-логічне обґрунтування процедури ефективного керування множиною обмежень на прикладі задачі нафтогазової предметної області In this paper the analysis of CSP conception implementation problem for intelligible data analysis by means of Constraint Logic Programming is presented and formal logical substantiation of effective control routine for constraints set is introduced on the base of example data from oil&gas subject domain. uk Інститут програмних систем НАН України Моделі і засоби систем баз даних і знань Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області The implementation of CSP-conceptions for data intellectual analysis of oil&gas subject domain Article published earlier |
| spellingShingle | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області Випасняк, Л.І. Шпакодрай, Б.І. Шекета, В.І. Моделі і засоби систем баз даних і знань |
| title | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області |
| title_alt | The implementation of CSP-conceptions for data intellectual analysis of oil&gas subject domain |
| title_full | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області |
| title_fullStr | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області |
| title_full_unstemmed | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області |
| title_short | Імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області |
| title_sort | імплементація csp-концепцій для інтелектуального аналізу даних нафтогазової предметної області |
| topic | Моделі і засоби систем баз даних і знань |
| topic_facet | Моделі і засоби систем баз даних і знань |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1493 |
| work_keys_str_mv | AT vipasnâklí ímplementacíâcspkoncepcíidlâíntelektualʹnogoanalízudanihnaftogazovoípredmetnoíoblastí AT špakodraibí ímplementacíâcspkoncepcíidlâíntelektualʹnogoanalízudanihnaftogazovoípredmetnoíoblastí AT šeketaví ímplementacíâcspkoncepcíidlâíntelektualʹnogoanalízudanihnaftogazovoípredmetnoíoblastí AT vipasnâklí theimplementationofcspconceptionsfordataintellectualanalysisofoilampgassubjectdomain AT špakodraibí theimplementationofcspconceptionsfordataintellectualanalysisofoilampgassubjectdomain AT šeketaví theimplementationofcspconceptionsfordataintellectualanalysisofoilampgassubjectdomain |