Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил
В даному дослідженні представлено підхід до виконання інтерпретації інформаційно-пошукових задач на основі обмежень з введеними правилами у вигляді пошуку співпадань інформаційної предикатної схеми з обмеженням та правилом з гіперграфом нафтогазової предметної області. Оцінка співпадань здійснюється...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/83306 |
| 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: | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил / Л.І. Випасняк, В.І. Шекета // Мат. машини і системи. — 2010. — № 4. — С. 82-88. — Бібліогр.: 5 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860049290354753536 |
|---|---|
| author | Випасняк, Л.І. Шекета, В.І. |
| author_facet | Випасняк, Л.І. Шекета, В.І. |
| citation_txt | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил / Л.І. Випасняк, В.І. Шекета // Мат. машини і системи. — 2010. — № 4. — С. 82-88. — Бібліогр.: 5 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | В даному дослідженні представлено підхід до виконання інтерпретації інформаційно-пошукових задач на основі обмежень з введеними правилами у вигляді пошуку співпадань інформаційної предикатної схеми з обмеженням та правилом з гіперграфом нафтогазової предметної області. Оцінка співпадань здійснюється на основі аналізу задоволення накладеної системи обмежень та верифікації відповідного ланцюга правил.
В данном исследовании представлен подход к выполнению интерпретации информационно-поисковых задач на основе ограничений с введенными правилами в виде поиска совпадений информационной предикатной схемы с ограничением и правилом с гиперграфом нефтегазовой предметной области. Оценка совпадений осуществляется на основе анализа удовлетворения наложенной системы ограничений и верификации соответствующей цепи правил.
In the research we present an approach of fulfillment of interpretation of the information retrieval problems based on the introduced rules restrictions in the form of a search of coincidence of informational predicate scheme with a constraint and a rule with an Oil & Gas domain hypergraph. A score match is made on basis of analysis of constraint system satisfaction and appropriate rules chain verification
|
| first_indexed | 2025-12-07T16:59:24Z |
| format | Article |
| fulltext |
82 © Випасняк Л.І., Шекета В.І., 2010
ISSN 1028-9763. Математичні машини і системи, 2010, № 4
УДК 004.942
Л.І. ВИПАСНЯК, В.І. ШЕКЕТА
ГРАФОВА ІНТЕРПРЕТАЦІЯ ІНФОРМАЦІЙНИХ СИСТЕМ НА ОСНОВІ БАЗ
ДАНИХ ТА ЗНАНЬ У РАМКАХ КОНЦЕПЦІЇ ЗАДОВОЛЕННЯ ОБМЕЖЕНЬ ТА
ПРАВИЛ
Анотація. В даному дослідженні представлено підхід до виконання інтерпретації інформаційно-
пошукових задач на основі обмежень з введеними правилами у вигляді пошуку співпадань інформа-
ційної предикатної схеми з обмеженням та правилом з гіперграфом нафтогазової предметної
області. Оцінка співпадань здійснюється на основі аналізу задоволення накладеної системи обме-
жень та верифікації відповідного ланцюга правил.
Ключові слова: інформаційно-пошукова задача, предикатна схема, гіперграф, нафтогазова пред-
метна область.
Аннотация. В данном исследовании представлен подход к выполнению интерпретации информа-
ционно-поисковых задач на основе ограничений с введенными правилами в виде поиска совпадений
информационной предикатной схемы с ограничением и правилом с гиперграфом нефтегазовой
предметной области. Оценка совпадений осуществляется на основе анализа удовлетворения на-
ложенной системы ограничений и верификации соответствующей цепи правил.
Ключевые слова: информационно-поисковая задача, предикатная схема, гиперграф, нефтегазовая
предметная область.
Abstract. In the research we presented an approach for interpretation of constraints satisfaction problem
based on information retrieval problem in the form of coincidence searching for predicate schemes with
constraint, rule and oil and gas subject field hypergraph. The evaluation of coincidence is based on satis-
faction analysis of imposed constraint system and relative rules chain verification.
Key words: constraint satisfaction problem, predicate query, hypergraph, oil&gas subject domain.
1. Вступ
Однією з актуальних проблем штучного інтелекту є проблема задоволення обмежень (CSP
– constraints satisfaction problem) [1], яка має ряд застосувань: прогнозування, розподіл ре-
сурсів, планування, розміщення ресурсів та ін. Наукові пошуки в області CSP базуються на
класичних задачах штучного інтелекту, мовах програмування штучного інтелекту [2, 3],
абстрактних обчисленнях, теоріях логіки. В першому наближенні обмеження можна розг-
лядати як прості логічні відношення між кількома невідомими чи змінними, які набувають
значення із своїх доменів. Обмеження, таким чином, розділяє можливі значення, які змінні
можуть набувати. Вони представляють деяку часткову інформацію про змінні. Формалізо-
вано проблема задоволення обмежень може бути представлена у вигляді множини змінних
nixX i ,1},{ == , скінченних множин iD , їх можливих значень (доменів), niDD i ,1},{ == і
множини обмежень, які обмежують значення, що змінні можуть одночасно приймати
niConstrConstr i ,1},{ == . Розв’язком CSP є набір значень з відповідних доменів для кожної
змінної, які б задовольняли кожне накладене обмеження. Розрізняють пошук тільки одного
розв’язку, всіх розв’язків, оптимального розв’язку [4]. Обмеження мають ряд властивос-
тей: можливість описувати часткову інформацію; обмеження не є напрямленими; обме-
ження мають декларативний характер, тобто можуть описувати відношення без опису об-
числювальних процедур; обмеження адитивні, тобто порядок їх виклику не є суттєвим;
спільні обмеження можуть використовуватися для розділених змінних.
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 83
Проте невирішеними залишаються проблеми щодо коректної інтерпретації процесу
пошуку рішення інформаційно-пошукових задач при накладеній множині обмежень та
введеній послідовності правил.
2. Введення гіперграфової інтерпретації
Метою даної статті є введення гіперграфової інтерпретації для формально-логічного опису
процесу пошуку рішення інформаційно-пошукових задач нафтогазової предметної області
на основі обмежень та правил.
Означення 1. Інформаційно-пошукову задачу на основі обмежень та правил представимо
кортежем ),,,( setset RulesConstrDX , де nixX i ,1},{ == – множина змінних; iD – множина
доменів їх значень, niDD i ,1},{ == ; setConstr – множина обмежень, які обмежують значен-
ня, що змінні можуть приймати; niConstrConstr iset ,1},{ == , }{ iiiset RCRPRulesRules →==
– послідовність правил [5].
Означення 2. Впорядкований набір ),,,,,,( ,
4
.
3
.
21
setsettrgextsrcexttrgsrcsetset RulesConstrffffHAVHG =
вважатимемо інформаційним гіперграфом з обмеженнями та правилами, якщо setV – скін-
ченна множина вершин, setHA – скінченна множина гіперребер, 1
srcf – функція присвоєння
послідовності вихідних вузлів до кожного гіперребра, 2
trgf – функція присвоєння послідов-
ності кінцевих вузлів до кожного гіперребра, 3
.srcextf – функція ініціалізації зовнішніх вихі-
дних вузлів, 4
.trgextf – функція ініціалізації зовнішніх кінцевих вузлів, setConstr – множина
обмежень, setRules – множина правил.
Означення 3. Нехай }...,,{ 3
][
2
][
1
][][ 321 cccConstr rrrRules
set
= – множина написів на ребрах гіперг-
рафа, які є правилами з введеними обмеженнями з множини вихідних обмежень для інфо-
рмаційно-пошукової задачі (CSP1). Тоді впорядкований набір
,,,,,,( 4
.
3
.
21
trgextsrcexttrgsrcsetset ffffHAVHGC = ),, ηsetset RulesConstr будемо вважати
)( ][ −
setConstrRules описаним гіперграфом з обмеженнями та правилами, якщо
,,,,( 21
trgsrcsetset ffHAVHGC = ),,, 4
.
3
. setsettrgextsrcext RulesConstrff є гіперграфом і
][:
setConstrsetset RulesHAV →∪η є функцією ініціалізації міток з множини ][ setConstrRules .
Означення 4. Інформаційною предикатною схемою
з обмеженням та правилом (рис. 1) на множині
унарних предикатів Π будемо називати об’єкт
,,,,,(
)(3
.
)(2)(1)()( PS
srcext
PS
trg
PS
src
PSPSRule
Constr fffHAVPS =
),,, )()()()(4
.
PSPSPS
set
PS
trgext setConstrRulesf η , де кожному
елементу приписаний відповідний предикат
ПHAV PSPS →∪ )()(:η .
Означення 5. Під співпаданням (або функцією співпадання) інформаційної предикатної
схеми Rule
ConstrPS з обмеженням та правилом з об’єктом Ω будемо розуміти ізоморфне вбудо-
вування предикатної схеми Rule
ConstrPS в Ω , тобто ін’єктивний морфізм Ω→Rule
ConstrPS:σ , та-
кий, що для всіх ПHAVx
Rule
Constr
Rule
Constr PSPS →∪∈ )()(: предикат )()( x
Rule
ConstrPSη є істинним для
))(()( xση Ω .
Рис. 1. Інформаційна предикатна
схема з обмеженням та правилом
84 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
Будемо вказувати тільки послідовність дуг для ініціалізації обходу гіперграфа
HGC
cspWalk . Такий підхід дозволяє встановлювати зовнішні вершини за допомогою функцій
3
.srcextf і 4
.trgextf та виконувати відповідну корекцію для ланцюга правил. Кількість ребер в
обході HGC
cspWalk вважатимемо довжиною обходу і на її основі визначатимемо довжину ла-
нцюга правил. Для побудови коректної інтерпретації по аналогії із звичайним графом мо-
жна виконувати побудову маршрутів HGC
cspRoute для гіперграфа HGC . Позначимо множину
всіх непорожніх маршрутів через +
HGC
cspRoute
T і включимо цю множину в формальне представ-
лення гіперграфа ),,,,,,( 4
.
3
.
21
trgextsrcexttrgsrcRoutesetset ffffTHAVHGC HGC
csp
+= . Введені нами функції
4
.
3
.
21 ,,, trgextsrcexttrgsrc ffff розширимо таким чином, щоб вони покривали операції обходу
HGC
cspWalk , маршруту HGC
cspRoute і шляху HGC
cspPath у гіперграфі HGC :
0110
:)),,...,,,((1
iii
RCRPr
iiisrc vvavavf
mm
iii
=
→= 48476
,
mm
i
m ii
c
iiiitrg vvavavf =:)),,...,,,((
110
2
48476
. Вважатимемо два обходи
1][ HGC
cspWalk і 2][ HGC
cspWalk такими, що можуть бути об’єднані, якщо
)]([)]([ 2112 HGC
cspsrc
HGC
csptrg WalkfWalkf = . Об’єднання обходів 1][ HGC
cspWalk і 2][ HGC
cspWalk , де
),...,,,,(][ 11111
1
1
110
4847648476 m
mm
rr
HGC
csp vavavWalk = і ),,...,,,(][ 2
...
2222
2
1
110 n
n
n
vavavWalk
cc
HGC
csp
4484476
= , визначимо як
),...,,,,,,...,,,(][][ 222221
...
1111
21
1
110
1
110
484764847648476
o
n
nnm
m
m
rrcc
HGC
csp
HGC
csp vavavvavavWalkWalk == .
Природно, що таке об’єднання буде асоціативним, тобто для обходів
1][ HGC
cspWalk , 2][ HGC
cspWalk , 3][ HGC
cspWalk буде справедливим
)][]([][][)][]([ 321321 HGC
csp
HGC
csp
HGC
csp
HGC
csp
HGC
csp
HGC
csp WalkWalkWalkWalkWalkWalk oooo = .
Нехай
),,][,][,][,][,,( )(4
.
)(3
.
)(2)(1)()(
setset
HGC
trgext
HGC
srcext
HGC
trg
HGC
src
HGC
set
HGC
set RulesConstrffffAVHGC = є гіпе-
рграфом. Тоді маршрут HGC
cspRoute є послідовністю ребер ),...,(
...1
1
48476 m
m
cc
ii aa , де всі
jia є різни-
ми і існують вузли
} }
),...,(
111
1
mmm
m
RCRPr
i
RCRPr
i vv
→=→=
, такі, що для всіх
jia
1
)(1
−
=
jj iisrc vaf і
jj iitrg vaf =)(2 . Кількість ребер у маршруті HGC
cspRoute будемо розглядати як довжину мар-
шруту. Множину всіх маршрутів у гіперграфі позначимо через HGC
cspRoute
T , а множину непо-
рожніх – через
+
HGC
cspRoute
T . Для непорожнього маршруту ),...,(
...1
1
48476 m
m
cc
iii aaRoute = ∈ +
HGC
cspRoute
T введе-
мо функції VTff HGC
cspRoute
T
trg
T
src →+:][,][ 21 , які означимо як )(][)(][
1
1
11 ic
i
T
trgi
T
src afRoutef = і
)(][)(][ 22 m
i
m
c
i
TT
trgi
T
src afRoutef = , відповідно.
Нехай Ω – деяка база даних, Rule
ConstrPS – інформаційна предикатна схема з обмежен-
ням та правилом і Ω⊆Ω1 є співпаданням
1
1
Rule
Constr
PS (рис. 2).
Тоді кожен надоб’єкт 2Ω для 1Ω Ω⊆Ω⊆Ω 21 є також співпаданням
1
1
Rule
Constr
PS . Не-
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 85
хай )()( ΩΦ
Rule
ConstrPS позначає множину всіх співпадань Rule
ConstrPS в Ω. Оскільки )()( ΩΦ
Rule
ConstrPS є
підмножиною ( )Ωθ , то структура ]),([ )( ⊆ΩΦ
Rule
ConstrPS є також частково впорядкованою мно-
жиною. Будемо назива-
ти мінімальний елемент
у цій частково впоряд-
кованій множині міні-
мальним співпаданням
або мінімальним екзем-
пляром Rule
ConstrPS в
Ω min][ Rule
ConstrPS .
Твердження 1.
Для заданого об’єкта Ω
структура [ ]⊆Ω),(θ є частково впорядкованою множиною, тобто ⊆ є рефлексивним, анти-
симетричним і транзитивним бінарним відношенням над )(Ωθ .
Доведення. ⊆ є рефлексивним тому, що Ω⊆Ω є справедливим для будь-якого
об’єкта Ω . Нехай 1Ω , 2Ω – два об’єкти, причому
),,][,][,][,][,,( )()()(4
.
)(3
.
)(2)(1)()(
1
11111111 ΩΩΩΩΩΩΩΩ=Ω setsettrgextsrcexttrgsrcSetSet RulesConstrffffHAV і
),,][,][,][,][,,( )()()(4
.
)(3
.
)(2)(1)()(
2
22222222 ΩΩΩΩΩΩΩΩ=Ω setsettrgextsrcexttrgsrcsetset RulesConstrffffHAV . Тоді
21 Ω⊆Ω і 12 Ω⊇Ω означимо, що 2211 )()( ΩΩΩΩ ∪=∪ setset RulesVRulesV і
2211 )()( ΩΩΩΩ ∪=∪ setset ConstrHAConstrHA і, таким чином, 21 Ω=Ω . Звідки слідує, що ⊆ є анти-
симетричною. Нехай
),,][,][,][,][,,( )()()(4
.
)(3
.
)(2)(1)()(
3
33333333 ΩΩΩΩΩΩΩΩ=Ω setsettrgextsrcexttrgsrcSetSet RulesConstrffffHAV . 21 Ω⊆Ω і
12 Ω⊇Ω означають, що )()( 2211 )()( ΩΩΩΩ ∪⊆∪ setset RulesVRulesV і
)()( 2211 )()( ΩΩΩΩ ∪⊆∪ setset ConstrHAConstrHA . Із 21 Ω⊆Ω і 32 Ω⊆Ω слідує
3)3(2)2(
1
3)3(
23 )(
)(1)(1)(1
ΩΩΩΩΩΩ ∪∪
Ω
∪
ΩΩ ==
setsetset ConstrHAConstrHAsrcConstrHAsrcsrc fff ,
3)3(2)2(
1
3)3(
23 )(
)(2)(2)(2
ΩΩΩΩΩΩ ∪∪
Ω
∪
ΩΩ ==
setsetset ConstrHAConstrHAtrgConstrHAtrgtrg fff .
Оскільки )()( 2233 )()( ΩΩΩΩ ∪⊆∪ setset ConstrHAConstrHA , то це є рівним
3)3(
1 )(1
ΩΩ ∪
Ω
setConstrHAsrcf , 3)3(
1 )(2
ΩΩ ∪
Ω
setConstrHAtrgf . Звідси слідує, що операція ⊆ є транзитивною.
Твердження 2. Для заданого об’єкта Ω [ ]⊆Ω),(θ є повною структурою, тобто ко-
жна непорожня підмножина )(Ωθ має найменшу верхню і найбільшу нижню границі.
Доведення. Нехай Ω – заданий об’єкт і { }mΩΩ=Λ ,...,1 підмножина )(Ωθ , dscf –
функція опису множини міток (обмежень та правил). Тоді
),
,],[],[(
]][][[
)(
][
)(2
][
)(1)()()()(
)()()()()()(
)()(
i
set
ii
set
i
i
i
set
i
i
i
set
i
i
iiii
ConstrHARulesVdscConstrHAtrg
ConstrHAsrcsetisetinng
ff
fConstrHARulesV
ΩΩΩΩΩΩ
ΩΩ
∪∪∪
Ω
∪
Ω
∪
ΩΩΩΩΩ ∪∪=Ω
II
I
II
є об’єктом перетину. Побудова найменшої верхньої границі може бути здійснена через
використання об’єкта об’єднання. Якщо ребро належить
][ )()()(
iinng
seti ConstrHAHA ΩΩΩ ∪= I , то вона належить і всім )( iHA Ω . Тоді його по-
чаткова і кінцева вершини належать )( iV Ω і, таким чином, також належить
)( nngV
Ω
.
Рис. 2. Інформаційна предикатна схема з обмеженнями
та співпаданнями
86 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
|Ω⊆Ωnng справджується для всіх mi ≤≤1 , тому що ][ )()()(
iinng
setRulesVV ΩΩΩ ∪⊆ і
][ )()()(
iinng
setConstrAA ΩΩΩ ∪⊆ , звідки nngΩ є нижньою границею. Припустимо, ми
маємо іншу нижню границю Ω ′ , і nngΩ⊆Ω ' не справджується, тоді існує вершина або
ребро ][ )()( Ω ′Ω ′ ∪∈ HAVx , причому ][ )()( nngnng HAVx ΩΩ ∪∉ . Звідси випливає, що існує
об’єкт iΩ , для якого ][ )()( ii HAVx ΩΩ ∪∉ . Але це відразу ж приводить до iΩ⊄Ω ' , що
суперечить тому факту, що 'Ω є нижньою границею.
Твердження 3. Нехай Ω – об’єкт і Rule
ConstrPS – інформаційна предикатна схема з об-
меженням та правилом. Нехай ),,,( setset RulesConstrDX є інформаційно-пошуковою зада-
чею на основі обмежень та правил, що має l-змінних { }|1,..., xxX = . Тоді кортеж
l
rr
C
l
C DDdd
i
l
i
i
l
i
i
i
××∈ ...),...,( 1
...
1
1
1
48476
є рішенням для пошукової задачі на основі обмежень тоді і тіль-
ки тоді, якщо відповідний йому підоб’єкт Ω є мінімальним співпаданням Rule
ConstrPS в Ω .
Доведення. Нехай ),...,(
...
1
1
1
48476
i
l
i
i
l
i
i
i
rr
C
l
C dd є рішенням пошукової задачі на основі обмежень та
правил, де i
l
i CC ,...,1 – i -ий набір обмежень, i
l
i rr ,...,1 i -ий набір правил. Для кожного
)][,...,]([
1
1
1
i
lC
i
li
iC
i
ii rlrj ddd ∈ виконаємо таке. Якщо
i
j
i
ji
C
rjd ][ є вершиною, тоді нехай
]},]{[][[][ )1()1()()(
i
j
i
ji
C
rj
j
set
jj
set
j dRulesVRulesV ∪∪=∪ −−
][][ )()1()()( j
set
jj
set
j ConstrHAConstrHA ∪=∪ − .
Якщо
i
j
i
ji
C
rjd ][ є ребром, тоді нехай
][][ )1()1()()( −− ∪=∪ j
set
jj
set
j RulesVRulesV і }]]{[][[][ )()1()()(
i
j
i
ji
C
rj
j
set
jj
set
j dConstrHAConstrHA ∪∪=∪ − .
Якщо
ij
HGC
cspRoute ][ є маршрутом, тоді нехай
][][ )1()1()()( −− ∪=∪ j
set
jj
set
j RulesVRulesV і
}]][{][[][ )()1()()(
i
j
i
ji
i
j
j
i
j
j
C
rj
C
i
C
i
j
set
jj
set
j dhahaConstrHAConstrHA ∈∪∪=∪ − .
Оскільки множина доменів була побудована на основі D , ми бачимо, що
][][ )()()()( ΩΩ ∪⊆∪ set
l
set
l RulesVRulesV і ][][ )()()()( ΩΩ ∪⊆∪ set
l
set
l ConstrAConstrA . Тепер
})()(:
{
)(2)(1)()(
)()()()()(
hafvhafvHAhaRules
VvRulesVRulesV
trgsrc
l
set
l
set
l
set
ii
ΩΩΩ
ΩΩΩ
=∪=∈∃
∪∈∪∪=∪
і )()( lHAHA i =Ω . Таким чином,
),
,,,(
)()()()()()(
)()(
)()(2
)(1)()()()(
i
set
ii
set
ii
set
i
i
set
i
iiii
ConstrHARulesVdscConstrHAtrg
ConstrHAsetsetseti
ff
fConstrHARulesV
ΩΩΩΩΩΩ
ΩΩ
∪∪∪
Ω
∪
Ω
∪
ΩΩΩΩΩ ∪∪=Ω
є підоб’єктом Ω , що відповідає )][,...,]([
1
1
1
i
lC
i
li
iC
i
i rlr
dd .
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 87
Нехай тепер ),,,,( )()(2)(1)()()()( ΩΩΩΩΩΩΩ ∪∪=Ω dsctrgsrcsetset fffConstrHARulesV є фіксова-
ним об’єктом і
,,,,(
)(2)(1)()()()(
Rule
Constr
Rule
ConstrRule
Constr
Rule
Constr
Rule
Constr
Rule
Constr
PS
trg
PS
src
PS
set
PSPS
set
PSRule
Constr ffRulesHARulesVPS ∪∪=
),,, )(
max
)(
min
)()( Rule
Constr
Rule
Constr
Rule
Constr
Rule
Constr PSPSPSPS
dscf ϑϑϑ
інформаційна предикатна схема. Нехай ),,,( setset RulesConstrDX – пошукова задача на ос-
нові обмежень з l-змінними { }|1,..., xxX = . Нехай lrlr
DDdd
i
lC
i
li
iC
i
i
××∈ ...)][,...,]([ 11
1
1
є рішенням
для пошукової задачі. Нехай ),,,,( )()(2)(1)()()()( iiiiiii
trgsrcsetseti ffConstrHARulesV ΩΩΩΩΩΩΩ ∪∪=Ω η
є підоб’єктом Ω , що відповідає )][,...,]([
1
1
1
i
lC
i
li
iC
i
i rlr
dd . Cпочатку покажемо, що iΩ є співпа-
данням для співставлення η в Ω , і тоді доведемо, що iΩ є мінімальним. Нехай σ є відо-
браженням між )()()()( ηηηη
setset ConstrARulesV ∪∪∪ і )()()( ][ Ω+Ω ∪∪ GC
cspRouteset TRulesV η , заданої
таким чином, що
j
iC
j
ij rij dx ][:)( =σ , де
j
iC
j
ij rid ][ є значенням змінної jx , що була введена в
пошукову задачу для представлення вузлів і ребер інформаційної предикатної схеми з об-
меженнями та правилами. Будемо використовувати змінні ix як синоніми для представ-
лення ребер і вузлів. Відображення σ є ізоморфним вбудовуванням η в
GS
cspRoute
TΩ . Нехай
jC
j
x є ребром в η , і 2
2
1
1
,
jRC
j
jRP
j
xx є її початковим і кінцевим вузлами. Тоді
),(
1
1
1
1
1
][)][,]([
876
jRCiRP
ji
j
iC
j
ij
j
iC
j
ij
xx
поч
riri Cdd
→
∈ і
),(
2
2
2
2
1
][)][,]([
876
jRCiRP
ji
j
iC
j
ij
j
iC
j
ij
xx
кін
riri Cdd
→
∈ , тому що обмеження
задані і )][,...,]([
1
1
1
i
lC
i
li
iC
i
i rlr
dd є рішенням для пошукової задачі. Виходячи із означення цих
двох обмежень, видно, що
1
1
1
][
j
iC
j
ij rid і
2
2
1
][
j
iC
j
ij rid є вузлами початку і кінця для
j
iC
j
ij rid ][ в
GS
cspRoute
TΩ . Подібним чином можна довести, що σ є ін’єктивною функцією, що використовує
ін’єктивні обмеження
),(
2
2
][
876
jRCiRP
ji xx
інC
→ .
Нехай jRP
j
x є вузлом. Тоді пр
xri jRP
j
j
iC
j
ij
Cd
)(
][ ∈ , звідки входження )()( jRP
jxΩη приймає
значення істина для )]([)(
j
iC
j
ij
GS
cspRoute
T
ridΩη . Далі, нехай jx – ребро. Тоді
пр
xri jRP
j
j
iC
j
ij
Cd
)(
][ ∈ і звідки
для всіх ребер в
j
iC
j
ij rid ][ предикат )()( jRP
jxΩη є істинним для відповідних міток.
Якщо таких двох змінних не існує, то умови з означень 1–3 задовольняються триві-
ально. Якщо вони все-таки існують, тоді
),(
1
1
2
2
1
1
1
1
][)][,]([
876
jRCiRP
ji
j
iC
j
ij
j
iC
j
ij
xx
кін
riri Cdd
→
∈ , оскільки існу-
ють обмеження, і )][,...,]([
1
1
1
i
lC
i
li
iC
i
i rlr
dd є рішенням для пошукової задачі. Це, у свою чергу,
88 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
передбачає, що надписи для
iC
i
i r
d
1
1
][ 1 і
iC
i
i r
d
2
2
][ 1 є однаковими, виходячи із означень заданих
обмежень.
Нехай jC
jx – деяке ребро. Якщо воно має AD як свій домен, тоді 1)()(
min =jC
jxηϑ і
1)()(
max =jC
jxηϑ . Якщо j
j
C
rjd ][ має своїм доменом
GS
cspRoute
TΩ , тоді обмеження min
)( jC
jx
C і max
)( jC
jx
C іс-
нують, і j
j
C
rjd ][ є членом обох з них, оскільки він входить у рішення пошукової задачі. Ви-
ходячи з означення обмежень, j
j
C
rjd ][ є не коротшим, ніж )()(
min
jC
jxηϑ , і не довшим, ніж
)()(
min
jC
jxηϑ .
Нехай ),,,,( )()(2)(1)()()()( iiiiiii
trgsrcsetseti ffConstrHARulesV ΩΩΩΩΩΩΩ ∪∪=Ω η є мінімаль-
ним співпаданням η в Ω . Нехай σ є функцією співставлення. Нехай
))(),...,((:)][,...,]([ 1
1
1
11
l
i
lC
i
li
iC
i
i
C
l
C
rlr
xxdd σσ= і lrlr
DDdd
i
lC
i
li
iC
i
i
××∈ ...)][,...,]([ 11
1
1
, тобто
)][,...,]([
1
1
1
i
lC
i
li
iC
i
i rlr
dd є потенційним рішенням для пошукової задачі. Перевіримо, чи воно за-
довольняє всім введеним умовам.
Нехай пр
x jC
jrj
C
)]([
є обмеженням на надписи(мітки). Якщо
jC
jrj
x ][ є вузлом, тоді предикат
)]([)( j
j
C
rjxΩη є істинним для ))]([()( j
j
C
rjxση Ω , тому що σ є функцією співпадання. Це
означає пр
x
C
rj j
j
j
Cx )()]([ ∈σ і таким чином пр
x
C
rj jC
jrj
j
j
Cd
)]([
][ ∈ , тому що η є функцією співстав-
лення. Таким чином, пр
x
C
rj jC
jrj
j
j
Cd
)]([
][ ∈ справджується і в цьому випадку.
3. Висновки
У даній статті виконано побудову гіперграфової інтерпретації інформаційно-пошукової
задачі на основі обмежень з введеними правилами. Процес пошуку рішень інформаційно-
пошукової задачі на основі обмежень та правил представлено у вигляді процедури співста-
влення інформаційної предикатної схеми з обмеженнями та правилами з відповідним гіпе-
рграфом нафтогазової предметної області. Подальші дослідження даного напряму будуть
спрямовані на створення модуля планування експертної інформаційної системи на основі
баз даних та знань для нафтогазової предметної області.
СПИСОК ЛІТЕРАТУРИ
1. Tsang E.P.K. Foundations of Constraint Satisfaction. – London and San Diego: Academic Press, 1993.
2. Шекета В.І. Інформаційна система для прогнозування нафтогазоносних покладів: дис. … канди-
дата техн. наук: 05.13.06 / Шекета Василь Іванович. – Херсон, 1999. – 130 с.
3. Шекета В.І. Інтерпретація предикатних запитів на основі премоноїдної дедукції в семантичній
стратегії і системі обмежень / В.І. Шекета, М.Я. Бестильний, Р.І. Храбатін // Проблеми програму-
вання. – 2006. – № 2–3.– С. 436 – 444.
4. Випасняк Л.І. Імплементація CSP-концепцій для інтелектуального аналізу даних нафтогазової
предметної області / Л.І. Випасняк, Б.І. Шпакодрай, В.І. Шекета // Проблеми програмування. –
2008. – № 2–3. – С. 355 – 360.
5. Випасняк Л.І. Використання коефіцієнтів впевненості при побудові предикатних запитів на
основі шаблонів JAVA-JESS / Л.І. Випасняк, В.І. Шекета, М.Я. Бестильний // Вісник Хмельницько-
го національного університету. Технічні науки. – 2007. – Т. 2. – С. 43 – 46.
Стаття надійшла до редакції 02.11.2009
|
| id | nasplib_isofts_kiev_ua-123456789-83306 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:59:24Z |
| publishDate | 2010 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Випасняк, Л.І. Шекета, В.І. 2015-06-18T09:37:14Z 2015-06-18T09:37:14Z 2010 Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил / Л.І. Випасняк, В.І. Шекета // Мат. машини і системи. — 2010. — № 4. — С. 82-88. — Бібліогр.: 5 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83306 004.942 В даному дослідженні представлено підхід до виконання інтерпретації інформаційно-пошукових задач на основі обмежень з введеними правилами у вигляді пошуку співпадань інформаційної предикатної схеми з обмеженням та правилом з гіперграфом нафтогазової предметної області. Оцінка співпадань здійснюється на основі аналізу задоволення накладеної системи обмежень та верифікації відповідного ланцюга правил. В данном исследовании представлен подход к выполнению интерпретации информационно-поисковых задач на основе ограничений с введенными правилами в виде поиска совпадений информационной предикатной схемы с ограничением и правилом с гиперграфом нефтегазовой предметной области. Оценка совпадений осуществляется на основе анализа удовлетворения наложенной системы ограничений и верификации соответствующей цепи правил. In the research we present an approach of fulfillment of interpretation of the information retrieval problems based on the introduced rules restrictions in the form of a search of coincidence of informational predicate scheme with a constraint and a rule with an Oil & Gas domain hypergraph. A score match is made on basis of analysis of constraint system satisfaction and appropriate rules chain verification uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Нові інформаційні і телекомунікаційні технології Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил Графовая интерпретация информационных систем на основе баз данных и знаний в рамках концепции удовлетворения ограничений и правил nformation systems represented as a graph, and based on data and knowledge bases within the concept of satisfaction of the constraints and rules Article published earlier |
| spellingShingle | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил Випасняк, Л.І. Шекета, В.І. Нові інформаційні і телекомунікаційні технології |
| title | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил |
| title_alt | Графовая интерпретация информационных систем на основе баз данных и знаний в рамках концепции удовлетворения ограничений и правил nformation systems represented as a graph, and based on data and knowledge bases within the concept of satisfaction of the constraints and rules |
| title_full | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил |
| title_fullStr | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил |
| title_full_unstemmed | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил |
| title_short | Графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил |
| title_sort | графова інтерпретація інформаційних систем на основі баз даних та знань в рамках концепції задоволення обмежень та правил |
| topic | Нові інформаційні і телекомунікаційні технології |
| topic_facet | Нові інформаційні і телекомунікаційні технології |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83306 |
| work_keys_str_mv | AT vipasnâklí grafovaínterpretacíâínformacíinihsistemnaosnovíbazdanihtaznanʹvramkahkoncepcíízadovolennâobmeženʹtapravil AT šeketaví grafovaínterpretacíâínformacíinihsistemnaosnovíbazdanihtaznanʹvramkahkoncepcíízadovolennâobmeženʹtapravil AT vipasnâklí grafovaâinterpretaciâinformacionnyhsistemnaosnovebazdannyhiznaniivramkahkoncepciiudovletvoreniâograničeniiipravil AT šeketaví grafovaâinterpretaciâinformacionnyhsistemnaosnovebazdannyhiznaniivramkahkoncepciiudovletvoreniâograničeniiipravil AT vipasnâklí nformationsystemsrepresentedasagraphandbasedondataandknowledgebaseswithintheconceptofsatisfactionoftheconstraintsandrules AT šeketaví nformationsystemsrepresentedasagraphandbasedondataandknowledgebaseswithintheconceptofsatisfactionoftheconstraintsandrules |