Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування
Досліджуються загальні властивості теоретико-множинних конструкцій, які використовуються, зокрема, в теорії реляційних баз даних при дослідженні табличних алгебр, побудованих на основі класичних реляційних алгебр Кодда. Розглянуто повний образ множини щодо бінарного відношення та розповсюдження ун...
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/14639 |
| 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. — № 2-3. — С. 80-88. — Бібліогр.: 16 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859544197364711424 |
|---|---|
| author | Буй, Д.Б. Кахута, Н.Д. Сільвейструк, Л.М. |
| author_facet | Буй, Д.Б. Кахута, Н.Д. Сільвейструк, Л.М. |
| citation_txt | Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування / Д.Б. Буй, Н.Д. Кахута, Л.М. Сільвейструк// Пробл. програмув. — 2010. — № 2-3. — С. 80-88. — Бібліогр.: 16 назв. — укр. |
| collection | DSpace DC |
| description | Досліджуються загальні властивості теоретико-множинних конструкцій, які використовуються, зокрема, в теорії реляційних баз
даних при дослідженні табличних алгебр, побудованих на основі класичних реляційних алгебр Кодда. Розглянуто повний образ
множини щодо бінарного відношення та розповсюдження унарних (бінарних) часткових операцій на множини за допомогою
повного образу, обмеження бінарного відношення за множиною, проекцію бінарного відношення та відношення сумісності
бінарних відношень.
The article is devoted research of general properties of set-theoretic constructions, which are used, in particular, in the theory of relational
databases at research of table algebra, which upbuild on the basis of classic Codd‟s relational algebra. The whole image of set relatively a
binary relation and of distribution of unary (binary) partial operations on the set with assistance whole image, restriction a binary relation
after set, projection of binary relation and consistency relation of binary relations are considered.
|
| first_indexed | 2025-11-26T01:39:39Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
© Д.Б. Буй, Н.Д. Кахута, Л.М. Сільвейструк, 2010
80 ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск
УДК 681.3.062
ЗАГАЛЬНОЗНАЧНІ ТЕОРЕТИКО-МНОЖИННІ
КОНСТРУКЦІЇ ПОВНОГО ОБРАЗУ, ОБМЕЖЕННЯ, СУМІСНОСТІ:
ВЛАСТИВОСТІ ТА ЗАСТОСУВАННЯ
Д.Б. Буй, Н.Д. Кахута, Л.М. Сільвейструк
Київський національний університет імені Тараса Шевченка,
03680, Київ, проспект Академіка Глушкова, 2, корп. 6, (044)521 3345
buy@unicyb.kiev.ua, v.kahuta@infoplus.com.ua, slm-klm@ukr.net
Досліджуються загальні властивості теоретико-множинних конструкцій, які використовуються, зокрема, в теорії реляційних баз
даних при дослідженні табличних алгебр, побудованих на основі класичних реляційних алгебр Кодда. Розглянуто повний образ
множини щодо бінарного відношення та розповсюдження унарних (бінарних) часткових операцій на множини за допомогою
повного образу, обмеження бінарного відношення за множиною, проекцію бінарного відношення та відношення сумісності
бінарних відношень.
The article is devoted research of general properties of set-theoretic constructions, which are used, in particular, in the theory of relational
databases at research of table algebra, which upbuild on the basis of classic Codd‟s relational algebra. The whole image of set relatively a
binary relation and of distribution of unary (binary) partial operations on the set with assistance whole image, restriction a binary relation
after set, projection of binary relation and consistency relation of binary relations are considered.
Загальні зауваження
Зафіксуємо універсум D , елементи якого позначимо x, y, z,... Підмножини універсуму позначимо X, Y …,
бінарні відношення на D (тобто множини пар, компоненти яких належать універсуму) – U, V,... .
Зазвичай бінарне відношення U назвемо функціональним, якщо для всіх елементів x, y, z виконується
імплікація zyUzxUyx ,&, .
Функціональні бінарні відношення (за іншою термінологією часткові функції) позначимо f, g,... .
Область означеності (рос. – “область определенности” [1], гл. 1, § 1, с. 20
1
) функції f позначимо domf , вона
збігається з проекцією функції (як бінарного відношення) за першою компонентою – fdomf 2
1 . Тут і далі
Ui
2 – проекція бінарного відношення за i -ю компонентою, 2,1i .
У літературі [2] поняття ін„єктивності застосовується до функцій, природно розповсюдимо його на
відношення: бінарне відношення U назвемо ін‘єктивним, якщо для всіх елементів x, y, z виконується імплікація
.,&, zxUyzUyx
Наступне очевидне твердження висвітлює природний тісний зв‟язок між властивостями
функціональності та ін‟єктивності за допомогою обернених відношень. Відношення, обернене до відношення U,
вводиться стандартно – },|,{1 UxyyxU
def
.
Твердження 1 (зв„язок між функціональністю та ін„єктивністю). Виконується еквівалентність
відношення U функціонально обернене відношення 1U ін‟єктивно.
Отже, с точністю до порядку компонент властивості функціональності та ін„єктивності еквівалентні. Цей
зв„язок стає особливо ясним, якщо бінарні відношення інтерпретувати як таблиці з стандартними іменами 2 ,1
(тобто відмовитися від порядку компонент) },|},2,,1{{)( UyxyxUt
def
та скористатися поняттям
функціональних залежностей в розумінні табличних (реляційних) баз даних. При цьому таблиці розуміються
в смислі [3], (підрозділ 2.1, с. 31), як множини функцій з однаковою областю означеності, а функціональні
залежності розуміються стандартно (див., наприклад, [3], підрозділ 2.10, с. 71 та наведену в цій роботі
бібліографію). Зв„язок розкривають дві наступні еквівалентності, які перевіряються безпосередньо: бінарне
відношення U функціонально на таблиці )(Ut виконується функціональна залежність }2{}1{ ; бінарне
відношення U ін„єктивно на таблиці )(Ut виконується функціональна залежність }1{}2{ .
З другого боку, цілком очевидно, що існують функціональні відношення, які не є ін„єктивними, та
навпаки – ін„єктивні відношення, які не є функціональними. Крім того, також очевидно, що існують
відношення, які не є функціональними та не є ін„єктивними. Нарешті, очевидно, що твердження 1 має
1
Зауважимо, що в другому видання монографії А.І. Мальцева використовується термін “область определения” [2], гл. 1, § 1, с. 19.
mailto:buy@unicyb.kiev.ua
mailto:slm-klm@ukr.net
Теоретичні та методологічні основи програмування
81
еквівалентне формулювання: відношення U – ін‟єктивно обернене відношення 1U функціонально; для
доведення треба тільки врахувати тривіальну рівність 11)( UU . Знак □ далі позначає кінець формулювання
твердження.
Повний образ
Зазвичай повним образом множини Х щодо відношення U (за іншою термінологією образом множини
щодо відношення) назвемо множину )},&(|{][ UyxXxxyXU
def
; композицією відношень U і V (взятих
саме в такому порядку) – відношення )},&,(|,{ UyzVzxzyxVU
def
. Порожнє відношення
(тобто порожню множину пар) позначимо . Відношення U назвемо тотальним (за іншою термінологією
всюди визначеним), якщо DU 2
1 . Під доповненням X множини X розуміємо доповнення до універсуму,
тобто XDX
def
\ .
Твердження 2 (властивості повного образу). Виконуються твердження.
1. ][][& 22112121 XUXUXXUU (монотонність за сукупністю аргументів).
2. ][])[(],[][ XUXUXUXU i
i
i
i
i
i
i
i
(дистрибутивність щодо об‟єднань).
3. ][][ i
i
i
i
XUXU (верхня оцінка повного образу перетину).
4. ])[(]][[ 2121 XUUXUU (повний образ щодо композиції відношень або повний образ повного
образу).
5. ][][ 2
1UXUXU .
6. UXXU 2
1][ (критерій порожності повного образу); зокрема, ][][ UX
(збереження повним образом порожнього відношення та порожньої множини) і, в припущенні тотальності
відношення U, – [ ] .U X X
7. ][]\[][\][ XUYXUYUXU (нижня та верхня оцінка повного образу різниці).
8. ][][\2
2 XUXUU (нижня оцінка повного образу доповнення).□
Пп. 3 та 7 (нижня оцінка) ставлять питання про природні достатні умови для дистрибутивності повного
образу щодо перетинів та різниці. Відповідь дає наступне твердження.
Нижче, зазвичай, обмеженням відношення U за множиною Х називається відношення
).()(| 2
2UXUDXUXU
def
Твердження 3 (достатні умови дистрибутивності повного образу щодо перетину та різниці). Повний
образ має властивості.
1. Обмеження i
Ii
XU
| ін‟єктивно [ ] [ ].i i
i I i I
U X U X
2.
1 1[ ] [ ].i i
i i
f X f X
3. Обмеження )(| YXU ін‟єктивно [ \ ] [ ] \ [ ].U X Y U X U Y
4. ].[\][]\[ 111 YfXfYXf □
Як демонструють прості приклади, умови твердження 3 є достатніми, але не необхідними. Дійсно,
розглянемо такі множини 21, XX та відношення U: },{},,{ 2211 zxXzxX
defdef
, де елементи zxx , , 21 попарно
різні, }.,,,,,{ 21 yxyzyxU
def
Очевидно, що ],[][}{}][{][ 2121 XUXUyzUXXU але обмеження 21| XXU не є ін‟єктивним
(див. рис. 1).
У наступному твердженні наведений формальний критерій дистрибутивності повного образу щодо
перетинів. Формальність проявляється в тому, що по суті спрощення відсутнє, але цей критерій висвітлює роль
ін„єктивності для достатніх умов дистрибутивності визначених в попередньому твердженні 3. Зважаючи на
загальнозначне включення ][][ i
i
i
i
XUXU (п. 3 твердження 2 про властивості повного образу), в
наступному критерії йдеться про обернене включення.
Теоретичні та методологічні основи програмування
82
.
z
. 1x
. 2x
. y
2X
1X
2X
1x
2x
z
y
Рис. 1. Приклад неін‟єктивного відношення U та множин iX , таких, що виконується рівність
][][ i
i
i
i
XUXU
Твердження 4 (критерій дистрибутивності повного образу щодо перетину). Виконується еквівалентність
][]\[][][ 000 XUXXUXUXU
Ii
i
Ii
i
, де
Ii
i
def
XX
0 ;
зокрема, для випадку перетину двох множин
][]\[]\[][][][ 2112212121 XXUXXUXXUXXUXUXU . □
Аналогічний підхід можна застосувати для отримання критерію дистрибутивності повного образу щодо
різниці. А саме виконується наступне твердження.
Твердження 5 (критерій дистрибутивності повного образу щодо різниці). Виконується еквівалентність
][]\[][\][]\[ YUYXUYUXUYXU . □
Твердження 4 та 5 ми називаємо критеріями дистрибутивності, хоча в них мова йде про відповідні
включення; справа в тому, що обернені включення були встановлені раніше (для перетину це п. 3 твердження 2,
а для різниці – п. 7 того ж твердження).
Для того, щоб висвітлити зв„язок між встановленими формальними критеріями дистрибутивності
(твердження 4, 5) та достатніми умовами дистрибутивності, що формулювалися в термінах ін„єктивності, треба
взяти до уваги наступний простий критерій ін„єктивності бінарних відношень.
Твердження 6 (критерій ін„єктивності відношення). Виконується еквівалентність
відношення U ін„єктивно )][][( YUXUYXYX . □
Таким чином, для ін„єктивного відношення U включення ][]\[]\[ 211221 XXUXXUXXU
з твердження 4 виконується автоматично, оскільки ліва частина просто порожня, згідно з твердженням 6;
аналогічно рівність ][]\[ YUYXU з твердження 5 також виконується автоматично.
Розповсюдження операцій з елементів на множини
Повний образ природно дозволяє унарні (бінарні) операції на універсумі розповсюджувати на булеан
універсуму. Позначимо ][ f унарну тотальну операцію на булеані універсуму D , яка індукується частковою
функцією f і задається рівністю ))}(~(|{][)]([ xfyXxxyXfXf
def
.
Нехай F – бінарна часткова операція на D; вона також індукує бінарну тотальну операцію ][F на
булеані D, яка задається рівністю ))},(~(|{][),]([ yxFzYyXxyxzYXFYXF
def
.
У наведених значеннях, з огляду на частковість функцій, замість стандартної рівності =
використовується узагальнена ~ (подробиці див. далі).
Очевидно, що операції ][ f та ][F зберігають порожню множину: )]([ f ,
),]([),]([ YFXF ; це випливає з збереження порожньої множини повним образом (п. 6 твердження 2)
та декартовим добутком.
Щоб продемонструвати природність саме таких розповсюджень унарних та бінарних операцій з
елементів на множини елементів (іншими словами з множини на булеан множини), покажемо, як на такому
шляху природно виникає відома сильна тризначна логіка Кліні [4], (част. III, розд. XII, § 64, с. 296–303), (див.,
також [5], розд. 4, § 4.1, с. 117; [6], § 4.2, табл. 4 на с. 127).
Теоретичні та методологічні основи програмування
83
Ця тризначна логіка була введена С. Кліні в теорії рекурсії як, зокрема, засіб побудови частково-
рекурсивних функцій; в системах алгоритмічних алгебр Глушкова логіка використовується при заданні умов;
нарешті, нині саме така логіка використовується в класі SQL-подібних мов для реляційних баз даних та в
сучасних мовах специфікацій UML/OCL (див., наприклад, [6]).
Отже, розглядаємо стандартну алгебру булівської логіки ,,};,{ FT , де FT , – логічні значення
істини та хиби відповідно. Результати розповсюдження операції кон„юнкції , диз„юнкції та заперечення
на булеан }),({ FTP наведені в табл. 1–3. В табл. 1–2 першому аргументу відповідають стовпці, другому –
рядки. Зауважимо, що ці розповсюдження є комутативними операціями, тому відповідні таблиці “симетричні”
та співставлення аргументам стовпців чи рядків не є суттєвим. Далі буде показано, що успадкування
комутативності (й асоціативності) в цьому конкретному випадку не є випадковим, а є наслідком загальних
властивостей нашої конструкції розповсюдження.
Таблиця 1. Операція ][ на булеані }),({ FTP
}{T }{F },{ FT
}{T }{T }{F },{ FT
}{F }{F }{F }{F
},{ FT },{ FT }{F },{ FT
Таблиця 2. Операція ][ на булеані }),({ FTP
}{T }{F },{ FT
}{T }{T }{T }{T
}{F }{T }{F },{ FT
},{ FT }{T },{ FT },{ FT
Таблиця 3. Операція ][ на булеані }),({ FTP
Аргумент }{T }{F },{ FT
Значення }{F }{T },{ FT
Розглянемо наступне відображення }),({},,{: FTPFT , де – третє логічне значення логіки Кліні:
}{)( TT , }{)( FF , },{)( FT . Домовимось також про однойменні операції: – ][ , – ][ , –
][ ; за операціями алгебри тризначної логіки Кліні залишимо ті ж позначення ,, .
Твердження 7 (про вкладення алгебри сильної тризначної логіки Кліні). Відображення є однозначним
гомоморфізмом алгебри сильної тризначної логіки Кліні ,,};,,{ FT в алгебру
][],[],[});,({ FTP , тобто це відображення є вкладенням алгебри сильної тризначної логіки Кліні в
алгебру ][],[],[});,({ FTP
1
. □
Таким чином, можна зробити висновок, що алгебра сильної тризначної логіки Кліні одержується шляхом
застосуватися до сигнатурних операцій алгебри класичної булівської логіки конструкції розповсюдження (в
термінах повного образу) унарних (заперечення) та бінарних операцій (кон„юнкція, диз„юнкція).
Зауважимо також, що зазначена конструкція розповсюдження, узагальнена природним чином, може
використовуватися і при розповсюдженні функцій та предикатів на NULL-значення в SQL-подібних мовах
2
.
Наведемо ще два приклади застосування конструкції розповсюдження (бінарних операцій) з елементів на
множини елементів.
1 Зауважимо: оскільки відображення не є сюр‟єкцією, то треба говорити саме про однозначний гомоморфізм.
2 В існуючих процесорах SQL-подібних мов підтримується інша конструкція розповсюдження функцій на Null-значення: якщо хоча б один
аргумент є Null, то результат також є Null (змістовно кажучи, функції зберігать Null). Зауважимо, що такий підхід реалізований в слабій
тризначній логіці Кліні – операції зберігать . Повертаючись до SQL, добуток Null0 можна було б покласти рівним 0, а не Null, як в
існуючих СУБД.
Теоретичні та методологічні основи програмування
84
Операція добутку формальних мов (див., наприклад, [7]) виникає, виходячи з бінарної операції
конкатенації слів: }|{),]([ 212121 LyLxyxLLLL .
Операція з‟єднання таблиць (див., [3], с. 32) випливає виходячи з бінарної операції об‟єднання
сумісних рядків ),](
~
[:
~
2121 ttUttU [3], (с. 49).
Повернемось до розгляду загальних властивостей розповсюдження операцій.
Часткову бінарну операцію F назвемо комутативною (асоціативною), якщо виконується узагальнена
рівність ),(~),( xyFyxF для всіх елементів yx , (відповідно )),(,(~)),,(( zyFxFzyxFF для всіх елементів
zyx ,, ). Тут і далі під узагальненою рівністю розуміється рівність, в якій обидві частини або невизначені, або
визначені та мають однакові значення [8], вступ, с. 11, (іноді цю узагальнену рівність називають сильною
рівністю, (див. наприклад, [9], c. 44). Перехід від стандартної рівності до узагальненої обумовлений розглядом
часткових операцій.
Зв‟язок між властивостями (ін„єктивність для унарних операцій, комутативність та асоціативність для
бінарних) вихідних та індукованих операцій на булеані розкривають три наступних твердження 8–10.
Твердження 8 (критерій ін„єктивності тотальної операції вигляду ][ f ). Виконується еквівалентність
функція f ін‟єктивна та тотальна операція [f] ін‟єктивна. □
Очевидно, що тотальність функції f суттєва для необхідності; тобто якщо часткова функція f ін‟єктивна,
то операція [f], взагалі кажучі, не є ін‟єктивною. Разом з тим, переходячи до відношень (тобто нехтуючи
функціональністю), необхідність в твердженні 8 можна узагальнити в наступному твердженні.
Твердження 8’ (достатня умова ін„єктивності тотальної операції вигляду ][U ). Виконується імплікація
відношення U ін‟єктивно та тотально операція [U] ін‟єктивна. □ (1)
В імплікації 1) відношення розповсюджується на булеан за тією ж самою схемою: ].[)]([ XUXU
def
Отже, функціональність відношення не суттєва для необхідності в формулюванні твердження 8.
Разом з тим, приклади для зліченого універсуму показують, що функціональність суттєва для
достатності. Відповідний приклад показано на рис. 2: операція [U] ін‟єктивна, але тотальне відношення U, яке
не є функціональним, не є й ін‟єктивним. Таким чином, імплікація 1), взагалі кажучи, не обертається.
…
xn
y1 y2
…
yn
z1 z2 z3
…
zn
…
…
…
x2
x1 x3
Рис. 2. Приклад неін‟єктивного тотального відношення U, такого, що операція [U] є ін‟єктивною
Наведемо таблицю успадкування властивості ін„єктивності при переході від відношення (зокрема,
функції) U на універсумі до тотальної унарної операції ][U на булеані універсуму. Стовпчики 1–3 наступної
табл. 4 відповідають властивостям функціональності, тотальності та ін„єктивності (саме у цьому порядку)
початкового відношення U , стовпчик 4 – властивості ін„єктивності похідної операції ][U (яка за означенням є
функціональною та тотальною). Вісім рядків табл. 4 відповідають всім можливим випадкам, коли вихідне
відношення має чи не має вказані три властивості. Знак “+” (“–“) в комірці означає, що відношення чи операція
має (не має) відповідної властивості. Нарешті, знак “ ” означає, що ніякого логічного зв„язку не має для
даного випадку.
Твердження 9 (успадкування ін„єктивності). Заповнення табл. 4 коректне. □
Прокоментуємо ще рядки 5, 6 табл. 5 з урахуванням критерію ін„єктивності відношень (твердження 6):
якщо ін„єктивне відношення U тотально, то операція ][U також ін„єктивна, тобто для всіх множин YX ,
виконується імплікація ][][ YUXUYX ; якщо ж ін„єктивне відношення U не є тотальним, то операція
][U не є ін„єктивною, але для всіх множин YX , виконується “більш сильна” імплікація
][][ YUXUYX (тобто обмеження вигляду LU |][ є ін„єктивним, де L – довільна підмножина
булеану )(DP , що складається з множин, які не перетинаються).
Теоретичні та методологічні основи програмування
85
Таблиця. 4. Логічний зв„язок між властивостями ін„єктивності відношення U
та індукованої операції ][U
№
п/п
Властивості відношення U Ін„єктивність операції
][U функціональність тотальність ін„єктивність
1 2 3 4
1. + + + +
2. + – + –
3. + + – –
4. + – – –
5. – + + +
6. – – + –
7. – – – –
8. – + –
Наступне твердження розкриває зв„язок між властивостями комутативності та асоціативності при
розповсюдженні бінарних операцій на множини. Основна ідея доведення (успадкування цих властивостей)
полягає в тому, що на одноелементних множинах розповсюдження по суті співпадає с початковою операцією.
Якщо уточнювати останнє твердження, то мова йде про те, що відображення }{xx
є однозначним
гомоморфізмом часткової алгебри (точніше групоїда за термінологією [10], розділ II, § 3, с. 89) FD;
в алгебру (групоїд) ][);( FDP , де )(DP – як і раніше, булеан універсуму D (тобто для всіх yx ,
виконується рівність ),]([),( yxFyxF за умови визначення лівої частини).
Твердження 10 (успадкування комутативності та асоціативності, критерії комутативності та
асоціативності операції вигляду ][F ). Виконується еквівалентність
бінарна часткова операція F комутативна (асоціативна) бінарна тотальна операція [F] комутативна
(асоціативна). □
Саме з останнього твердження випливає, зокрема, що розширення ][],[ , які виникаюь при розгляді
тризначної логіки Кліні, являються комутативними та асоціативними, успадковуючи ці властивості від
початкових операцій.
Обмеження
У наступному твердженні розглядаються властивості обмеження. Параметричний оператор XUU | ,
який відношенню ставить у відповідність його обмеження за множиною-параметром X , позначимо .X Далі
зазвичай, під оператором замикання на частково впорядкованій множині розуміється ідемпотентний,
монотонний та спадний (або зростаючий) оператор (див., наприклад, [11], § 3, с. 45).
Твердження 11 (властивості обмеження). Обмеження має властивості.
1. 22112121 ||& XUXUXXUU (монотонність обмеження за сукупністю аргументів; зокрема,
монотонність параметричного оператора X ).
2. XUXU 2
1
2
1 )|( , ][)(2
2 XUXU (проекція обмеження за першою та другою компонентою;
зв„язок між повним образом та обмеженням).
3. XUXU 2
1| (критерій порожності обмеження); зокрема, || UX (збереження
порожнього відношення та порожньої множини).
4. ;|),(|| 2
1
2
1 UUUUXUXU зокрема, 2
1 | .U X U X U
5. ),(||)|( YXUYXU або в операторному вигляді );( YXXY (композиція обмежень);
зокрема, XXX (ідемпотентність оператора X ).
6. UXU | (спадність оператора X );
7. Параметричний оператор X є оператором замикання щодо теоретико-множинного включення .
8. i
i
i
i
i
i
i
i
XUXUXUXU ||,||)( (дистрибутивність обмеження щодо об‟єднань);
)(|),(|)( i
ii
i
i
i
i
i XUXUXUXU (дистрибутивність обмеження щодо перетинів);
9. ;||& XgXfdomfXgf зокрема, ,| domfgfgf & .f g domf domg f g
10. ][])[|( YXUYXU (повний образ однієї множини щодо обмеження відношення за іншою
множиною). □
Теоретичні та методологічні основи програмування
86
З п. 2 доведеного твердження випливає рівність ][2
2 DUU , яка використовується при доведенні п. 8
твердження 2 про властивості повного образу; дійсно, використовуючи п. 4 твердження 11 маємо ланцюжок
рівностей ][)|(2
2
2
2 DUDUU .
Зауважимо, що п. 9 не виконується для відношень, взагалі кажучи; тобто функціональність тут суттєва;
наведемо відповідний приклад. Нехай відношення VU , та множина X наступні: },{ yxU
def
,
},,,{ zxyxV
def
, }{xX
def
, причому zy . Очевидно, що VU , UX 2
1 , але XVXU , тобто перша
імплікація не виконується. Також очевидно, що UVU 2
1 , тобто друга імплікація також не виконується.
Нарешті, очевидно, що VU 2
1
2
1 , але VU , отже і третя імплікація не виконується. Зауважимо: для цього
прикладу головне те, що VU , UXU та VXV .
Також відзначимо: останнє (третє) твердження п. 9 означає, що сім„я функцій з однаковою областю
означеності, впорядкованих за включенням їхніх графіків, є дискретною множиною (у звичайному розумінні,
див., наприклад, [11], § 1, с. 8).
Цей факт, в свою чергу, потрібен при розгляді піврешітки таблиць за з‟єднанням [3], (с. 56), а також для
достатніх умов, коли відношення конфінальності множин є частковим порядком [3], (с. 25).
Проекція та відношення сумісності
Виходячи з наступного очевидного зображення проекції відношення (за першою чи другою
компонентою) через повний образ відношення щодо селектора
][22 UIU ii , 2 ,1i ; (2)
де DDDIi :2 , yyxIxyxI ),( ,),( 2
2
2
1 – селектори, вкажемо загальнозначні властивості проекції; крім
того наведемо цікаві властивості проекції, що перевіряються безпосередньо.
1.
j
ji
j
jij
j
i
j
ji UUUU 2222 ; (верхня оцінка проекції перетину, дистрибутивність
проекції щодо об„єднань).
2. XYX )(2
1 , якщо Y ; YYX )(2
2 , якщо X (проекції декартова добутку).
3. UUi
2 (критерій порожності проекції).
4. )()( 2
2
2
1 UUU (верхня оцінка відношення).
5. ][2
2 DUU (вираз проекції за другою компонентою через повний образ).
6. )(\)()\( gdomfdomgfdomgf (достатня умова дистрибутивності проекції за першою
компонентою щодо різниці функцій).
7. 2
2
1
2
21 UUUU ii , де 2 ,1i (монотонність проекції за першою та другою компонентою).
Вище, в п. 6 – бінарне відношення сумісності відношень, зокрема функцій: ,|| XVXUVU
def
тут VUX
def
2
1
2
1 – перетин проекцій вихідних відношень за першою компонентою [3], (підрозд. 1.3, с. 25).
Очевидно, що відношення сумісності рефлексивне, симетричне (що випливає з однойменних
властивостей рівності), але не транзитивне (що показують прості приклади)
1
, взагалі кажучи; також очевидно,
що порожнє відношення сумісне з довільним відношенням – U , оскільки обмеження зберігає порожню
множину (твердження 11 про властивості обмеження, п. 3).
Властивості 1, 3, 7 випливають з зображення (2) та відповідних властивостей повного образу; властивості
2, 4, 5 перевіряються безпосередньо; далі зупинимось на доведенні властивості 6. Зауважимо, що саме ця
властивість у частковому випадку gf використовується в доведенні п. 9 твердження 11 про властивості
обмеження (очевидно, що з порівнянності функцій випливає їхня сумісність). Почнемо з леми про зв„язок між
функціональністю та ін„єктивністю, яка доповнює твердження 1.
Лема 1 (зв„язок між функціональністю та ін„єктивністю, критерій функціональності). Відношення U
функціонально обмеження UI 2
1 ін„єктивно. □
Наслідок 1. Виконується імплікація )(\)()\( gdomfdomgfdomgf .□
Далі буде показано, що імплікація останнього наслідку обертається. Почнемо з узагальнення доведеного
наслідку 1 для відношень.
1 Таким чином, сумісність є відношення толерантності.
Теоретичні та методологічні основи програмування
87
Твердження 12 (критерій дистрибутивності проекції за першою компонентою щодо різниці відношень).
Виконується еквівалентність VUVUVXU 2
1
2
1
2
1 \)\( , де VUX
def
2
1
2
1 . □
Наслідок 2 (характеристична властивість відношення сумісності, достатня умова дистрибутивності
проекції за першою компонентою щодо різниці). Виконується еквівалентність
UVUVVUVUVU 2
1
2
1
2
1
2
1
2
1
2
1 \)\(&\)\( . □
З останнього твердження випливає, зокрема, вищенаведений наслідок 1 та його наступне узагальнення.
Наслідок 1’ (характеристична властивість відношення сумісності функцій). Виконується еквівалентність
gf )(\)()\( gdomfdomgfdom . □
Як бачимо, характеристична властивість сумісності функцій (наслідок 1‟) виглядає більш просто ніж для
відношень загального виду (наслідок 2); справа в тому, що саме для функцій виконується п. 9 твердження 11
(про властивості обмеження). Зауважимо також, що прості приклади та врахування твердження 12 (критерій
дистрибутивності проекції за першою компонентою щодо різниці відношень) показують: спростити наслідок 2,
вилучаючи один з членів кон„юнкції в правій частині, не можна.
Наступне твердження 13 є аналогом твердження 12 та наслідку 2 для проекції перетину відношень.
У доведенні використовуються дві наступних леми (лема 2 потрібна для доведення леми 3). Далі для
спрощення запису повні образи синглітонів }{x (одноелементних множин) будемо позначати ][xU .
Лема 2. Виконуються такі твердження:
1)
Ux
xUxU
2
1
][}{
;
2) ])[][&(& 2
1
2
1
2
1 xVxUUxxVUVU . □
Лема 3 (критерій сумісності відношень). Виконується еквівалентність UVUVUUVU \&\ . □
Твердження 13 (достатня умова дистрибутивності проекції щодо перетину відношень, характеристична
ознака відношення сумісності функцій, критерій дистрибутивності проекції щодо перетину функцій). Для
відношень виконується імплікація VUVUVU 2
1
2
1
2
1 )( , яка в загальному випадку не обертається.
Для функцій виконується еквівалентність domgdomfgfdomgf )( . □
Основні результати
1. Встановлений зв„язок між функціональністю та ін„єктивністю.
2. Наведені основні властивості повного образу: монотонність, дистрибутивність щодо об‟єднань,
верхня оцінка повного образу перетину, повний образ щодо композиції відношень, критерій порожності
повного образу, збереження повним образом порожнього відношення та порожньої множини, нижня та верхня
оцінка повного образу різниці, нижня оцінка повного образу доповнення, критерій та достатні умови
дистрибутивності повного образу щодо перетину та різниці.
3. Побудовано вкладення алгебри (сильної) тризначної логіки Кліні.
4. Наведений критерій ін„єктивності тотальної операції вигляду ][ f , достатня умова ін„єктивності
тотальної операції вигляду ][U .
5. Досліджено логічний зв„язок між властивостями ін„єктивності відношення U та індукованої
операції ][U .
6. Встановлено успадкування комутативності та асоціативності, критерії комутативності та
асоціативності операції вигляду ][F .
7. Наведені основні властивості обмеження: монотонність, проекція обмеження за першою та другою
компонентами; зв„язок між повним образом та обмеженням, критерій порожності обмеження, збереження
порожнього відношення та порожньої множини обмеженням, композиція обмежень, ідемпотентність,
монотонність та спадність оператора X , дистрибутивність обмеження щодо об‟єднань та перетинів, повний
образ множини щодо обмеження відношення.
8. Встановлені критерій дистрибутивності проекції за першою компонентою щодо різниці відношень,
характеристична властивість відношення сумісності, достатня умова дистрибутивності проекції за першою
компонентою щодо різниці, характеристична властивість відношення сумісності функцій, достатня умова
дистрибутивності проекції щодо перетину відношень, характеристична ознака відношення сумісності функцій,
критерій дистрибутивності проекції щодо перетину функцій.
З наведених результатів випливає, що конструкції повного образу, обмеження та сумісності відношень
мають багату змістовну теорію; ця теорія успішно застосована при дослідженні табличних алгебр [3, 12 – 14].
Деякі з наведених результатів (з доведеннями) містяться в [15, 16].
Робота виконана за фінансової підтримки Міністерства освіти і науки України (МОН) в рамках
українсько-словацького проекту “Формальні специфікації програмних систем” (договір № М/29 –2008
від 28.03.2008 між Київським національним університетом імені Тараса Шевченка та МОН).
Теоретичні та методологічні основи програмування
88
1. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965. – 391 с.
2. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. – 367 с.
3. Редько В.Н., Брона Ю.Й., Буй Д.Б.,. Поляков С.А. Реляційні бази даних: табличні алгебри та SQL-подібні мови. – К.: Видавничий дім
„Академперіодика”, 2001. – 198 с.
4. Клини С.К. Введение в метаматематику. М.: “ИЛ”, 1957. – 526 с.
5. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. К.: Наук. думка, 1978. – 318 с.
6. Cook S., Kleppe A., Mitchell R., Rumpe B., Warmer J., Wills A. The Amsterdam Manifesto on OCL. – UML 2.0 Request for information
response: OMG Analysis & Design PTF, 1999 [Електронний ресурс]. – Точка доступу:
http://www.trireme.com/whitepapers/design/components/OCL_manifesto.PDF.
7. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. – М.: Мир, 1978. – 616 с.
8. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983. – 256 с.
9. Манна З. Теория неподвижной точки программ // Киб. сб. Нов. сер. – М.: Мир, 1978. – Вып. 15. – С. 38–100.
10. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. – 392 с.
11. Скорняков Л.А. Элементы теории структур. М.: Наука, 1982. – 158 с.
12. Редько В.Н., Буй Д.Б. К основаниям теории реляционных моделей баз данных // Кибернетика и системный анализ. – 1996. – № 4. –
С. 3–12.
13. Редько В.Н., Брона Ю.И., Буй Д.Б. Реляционные алгебры: операции проекции и соединения // Кибернетика и системный анализ. –
1997. – № 4. – С. 89–100.
14. Редько В.Н., Брона Ю.Й., Буй Д.Б. Реляционные алгебры: операции деления и переименования // Кибернетика и системный анализ. –
1997. – № 5. – С. 3–15.
15. Кахута Н.Д., Буй Д.Б. Властивості теоретико-множинних конструкцій повного образу та обмеження // Вісник Київського університету.
Сер. фіз.-мат. науки. – 2005. – Вип. 2. – С. 232–240.
16. Кахута Н.Д., Буй Д.Б. Властивості відношення конфінальності та устрій множини часткових функцій // Вісник Київського університету.
Сер. фіз.-мат. науки. – 2006. – Вип. 2. – С. 125–135.
http://www.trireme.com/
|
| id | nasplib_isofts_kiev_ua-123456789-14639 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-11-26T01:39:39Z |
| publishDate | 2010 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Буй, Д.Б. Кахута, Н.Д. Сільвейструк, Л.М. 2010-12-27T13:53:40Z 2010-12-27T13:53:40Z 2010 Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування / Д.Б. Буй, Н.Д. Кахута, Л.М. Сільвейструк// Пробл. програмув. — 2010. — № 2-3. — С. 80-88. — Бібліогр.: 16 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/14639 681.3.062 Досліджуються загальні властивості теоретико-множинних конструкцій, які використовуються, зокрема, в теорії реляційних баз даних при дослідженні табличних алгебр, побудованих на основі класичних реляційних алгебр Кодда. Розглянуто повний образ множини щодо бінарного відношення та розповсюдження унарних (бінарних) часткових операцій на множини за допомогою повного образу, обмеження бінарного відношення за множиною, проекцію бінарного відношення та відношення сумісності бінарних відношень. The article is devoted research of general properties of set-theoretic constructions, which are used, in particular, in the theory of relational databases at research of table algebra, which upbuild on the basis of classic Codd‟s relational algebra. The whole image of set relatively a binary relation and of distribution of unary (binary) partial operations on the set with assistance whole image, restriction a binary relation after set, projection of binary relation and consistency relation of binary relations are considered. uk Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування Generally valid set-theoretic constructions of whole image, restriction, consistency: properties and applications Article published earlier |
| spellingShingle | Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування Буй, Д.Б. Кахута, Н.Д. Сільвейструк, Л.М. Теоретичні та методологічні основи програмування |
| title | Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування |
| title_alt | Generally valid set-theoretic constructions of whole image, restriction, consistency: properties and applications |
| title_full | Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування |
| title_fullStr | Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування |
| title_full_unstemmed | Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування |
| title_short | Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування |
| title_sort | загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: властивості та застосування |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/14639 |
| work_keys_str_mv | AT buidb zagalʹnoznačníteoretikomnožinníkonstrukcíípovnogoobrazuobmežennâsumísnostívlastivostítazastosuvannâ AT kahutand zagalʹnoznačníteoretikomnožinníkonstrukcíípovnogoobrazuobmežennâsumísnostívlastivostítazastosuvannâ AT sílʹveistruklm zagalʹnoznačníteoretikomnožinníkonstrukcíípovnogoobrazuobmežennâsumísnostívlastivostítazastosuvannâ AT buidb generallyvalidsettheoreticconstructionsofwholeimagerestrictionconsistencypropertiesandapplications AT kahutand generallyvalidsettheoreticconstructionsofwholeimagerestrictionconsistencypropertiesandapplications AT sílʹveistruklm generallyvalidsettheoreticconstructionsofwholeimagerestrictionconsistencypropertiesandapplications |