Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок»
У статті розглядаються обмеження кардинальності, які застосовують до типів зв’язків у моделі „сутність-зв’язок”. Мета статті – встановити точну природу min та max обмежень кардинальності для бінарних типів зв’язків та дослідити логічний зв’язок між їх значеннями. Min та max обмежень кардинальності у...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2009
|
| Schriftenreihe: | Математичні машини і системи |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/47322 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» / Д.Б. Буй, Л.М. Сільвейструк // Мат. машини і системи. — 2009. — № 4. — С. 67-81. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-47322 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-473222013-07-12T03:07:15Z Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» Буй, Д.Б. Сільвейструк, Л.М. Нові інформаційні і телекомунікаційні технології У статті розглядаються обмеження кардинальності, які застосовують до типів зв’язків у моделі „сутність-зв’язок”. Мета статті – встановити точну природу min та max обмежень кардинальності для бінарних типів зв’язків та дослідити логічний зв’язок між їх значеннями. Min та max обмежень кардинальності уточнюються за допомогою поняття повного образу. В статье рассматриваются ограничения кардинальности, которые используются для типов связей в модели „сущность-связь”. Цель статьи – установить точную природу min и max ограничений кардинальности для бинарных типов связи и исследовать логическую связь между их значениями. Min и max ограничений кардинальности уточняются с помощью понятия полного образа. In the paper the constraints of cardinality which are used for types of connections in the entity-relationship model. The purpose of the paper is to define the exact nature of min and max constraints of cardinality for binary types of connections and to research the logical connection between their meanings. Min and max of constraints of cardinality are specified with the help of full pattern. 2009 Article Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» / Д.Б. Буй, Л.М. Сільвейструк // Мат. машини і системи. — 2009. — № 4. — С. 67-81. — Бібліогр.: 10 назв. — укр. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/47322 681.3.062 uk Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Нові інформаційні і телекомунікаційні технології Нові інформаційні і телекомунікаційні технології |
| spellingShingle |
Нові інформаційні і телекомунікаційні технології Нові інформаційні і телекомунікаційні технології Буй, Д.Б. Сільвейструк, Л.М. Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» Математичні машини і системи |
| description |
У статті розглядаються обмеження кардинальності, які застосовують до типів зв’язків у моделі „сутність-зв’язок”. Мета статті – встановити точну природу min та max обмежень кардинальності для бінарних типів зв’язків та дослідити логічний зв’язок між їх значеннями. Min та max обмежень кардинальності уточнюються за допомогою поняття повного образу. |
| format |
Article |
| author |
Буй, Д.Б. Сільвейструк, Л.М. |
| author_facet |
Буй, Д.Б. Сільвейструк, Л.М. |
| author_sort |
Буй, Д.Б. |
| title |
Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» |
| title_short |
Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» |
| title_full |
Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» |
| title_fullStr |
Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» |
| title_full_unstemmed |
Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» |
| title_sort |
уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2009 |
| topic_facet |
Нові інформаційні і телекомунікаційні технології |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/47322 |
| citation_txt |
Уточнення обмежень min та max простої кардинальності в моделі «сутність-зв'язок» / Д.Б. Буй, Л.М. Сільвейструк // Мат. машини і системи. — 2009. — № 4. — С. 67-81. — Бібліогр.: 10 назв. — укр. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT bujdb utočnennâobmeženʹmintamaxprostoíkardinalʹnostívmodelísutnístʹzvâzok AT sílʹvejstruklm utočnennâobmeženʹmintamaxprostoíkardinalʹnostívmodelísutnístʹzvâzok |
| first_indexed |
2025-07-04T07:06:03Z |
| last_indexed |
2025-07-04T07:06:03Z |
| _version_ |
1836699105284325376 |
| fulltext |
© Буй Д.Б., Сільвейструк Л.М., 2009 67
ISSN 1028-9763. Математичні машини і системи, 2009, № 4
УДК 681.3.062
Д.Б. БУЙ, Л.М. СІЛЬВЕЙСТРУК
УТОЧНЕННЯ ОБМЕЖЕНЬ MIN ТА MAX ПРОСТОЇ КАРДИНАЛЬНОСТІ В МОДЕЛІ
«СУТНІСТЬ-ЗВ'ЯЗОК»
Abstract: In the paper the constraints of cardinality which are used for types of connections in the entity-relationship
model. The purpose of the paper is to define the exact nature of min and max constraints of cardinality for binary
types of connections and to research the logical connection between their meanings. Min and max of constraints of
cardinality are specified with the help of full pattern.
Key words: constraints, cardinality constraints, entity-relationship model.
Анотація: У статті розглядаються обмеження кардинальності, які застосовують до типів зв’язків у
моделі „сутність-зв’язок”. Мета статті – встановити точну природу min та max обмежень
кардинальності для бінарних типів зв’язків та дослідити логічний зв’язок між їх значеннями. Min та max
обмежень кардинальності уточнюються за допомогою поняття повного образу.
Ключові слова: кардинальність, обмеження кардинальності, модель „сутність-зв’язок”.
Аннотация: В статье рассматриваются ограничения кардинальности, которые используются для типов
связей в модели „сущность-связь”. Цель статьи – установить точную природу min и max ограничений
кардинальности для бинарных типов связи и исследовать логическую связь между их значениями. Min и max
ограничений кардинальности уточняются с помощью понятия полного образа.
Ключевые слова: кардинальность, ограничения кардинальности, модель „сущность-связь”.
1. Вступ
Однією з найпопулярніших концептуальних моделей даних є модель „cутність-зв’язок” (російською –
„сущность-связь”), або ER-модель (Entity-Relationship model) [1]. На різновидах цієї моделі
базується більшість сучасних підходів до проектування моделей даних (головним чином,
реляційних або об’єктно-орієнтованих). У моделі „сутність-зв’язок” існують стандартні обмеження,
які застосовують до її елементів. Одне з таких обмежень – кардинальність (cardinality). Обмеження
кардинальності (cardinality constraints) застосовують до типів зв’язків. Існує декілька різновидів
вказаних обмежень, які можна знайти, наприклад, у роботах Ферга (Ferg) [2], Тхелхеіма (Thalheim)
[3], Лензеріні (Lenzerini) і Сантуккі (Santucci) [4].
Для бінарних типів зв’язків немає різниці між різновидами обмежень кардинальності [5].
Тому Ферг (Ferg) у роботі [2] запропонував розглядати для бінарних типів зв’язків єдиний вид
обмежень кардинальності – просту кардинальність (common cardinality).
Проста кардинальність – поняття, що залежить від зв’язків типу зв’язку для будь-якої
сутності, що належить деякому типу сутності даного типу зв’язку. При розгляді простої
кардинальності визначаються такі її характеристичні значення: min та max обмеження
кардинальності (обмежена кардинальність), min та max обмеження кардинальності (необмежена
кардинальність), mop обмеження кардинальності.
Питання, пов’язані з уточненнями понять обмежень кардинальності, можна знайти,
наприклад, у роботах [3–5]. Тхелхаім [3] та Хартманн (Hartmann) [5] використовують теорію
реляційних баз даних для уточнення обмежень кардинальності. Вони розглядають ці обмеження з
позиції функціональних залежностей, наголошуючи, що обмеження кардинальності – це
спеціальний вид функціональних залежностей. Ланзеріні в роботі [4] за допомогою спеціально
побудованої системи лінійних нерівностей вирішує проблему перевірки здійснення (анг. satisfiability)
схеми моделі „сутність-зв’язок”, тобто сумісності сутностей, зв’язків моделі і деякого виду min та
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 68
max обмежень кардинальності – обмеження співвідношення кардинальності (cardinality ratio
constraint). Також у даній роботі запропонована схема знаходження типів сутностей і типів зв’язків,
які порушують умови здійснимості схеми моделі „сутність-зв’язок” за допомогою теорії графів.
Обмеження кардинальності типів зв’язків можна уточнити на мові теорії відношень. У
роботах [6, 7] були розглянуті та уточнені такі поняття: max обмеження кардинальності (обмежена
кардинальність), mop обмеження кардинальності і min та max обмеження кардинальності
(необмежена кардинальність) для бінарних типів зв’язків; у згаданих роботах ці поняття мають такі
назви відповідно: показник кардинальності, степінь участі сутності у зв’язку і структурні обмеження
вигляду (min, max).
У цій роботі розглядається уточнення min та max обмежень кардинальності (необмежена
кардинальність) для бінарних типів зв’язків у моделі „сутність-зв’язок” з повним доведенням
відповідних лем та теореми. Всі невизначені тут поняття можна знайти у роботах [6, 7].
Символ □ позначає кінець формулювання твердження та кінець доведення, символ ▫ –
кінець логічної частини доведення.
2. Уточнення min та max обмежень кардинальності (необмежена кардинальність)
Уточнити min та max обмежень кардинальності для бінарного типу зв’язку можна за допомогою
стандартного поняття повного образу. Для адекватної формалізації понять типи сутностей E , F
інтерпретуються як множини E , F відповідно, елементи таких множин позначаються як ,..., yx .
Вимагається непорожність цих множин, суттєвість такого необтяжливого обмеження показано
нижче. Тип зв’язку R між типами сутностей E , F інтерпретується як бінарне відношення R на
множинах E , F , причому FER ×⊆ (порядок множин у декартовому добутку суттєвий). Як
звичайно, EFR 1 ×⊆− – відношення, обернене до відношення R .
Нехай Ex∈ , а ][xR – це повний образ одноелементної множини }{ x відносно
відношення R ; згідно з означенням },|{][ RyxFyyxR
def
>∈<∧∈= – множина всіх елементів
множини F , які знаходяться у відношенні R з елементом x [8].
Вважається, що множини E , F не більш, ніж злічені, а всі повні образі одноелементних
множин скінченні; з огляду на фінітність усіх об’єктів такі обмеження є природними.
Непорожню множину потужностей повних образів всіх елементів множини E позначено як
}][{)( ExxRRIm
def
∈= (саме тут суттєва непорожність множини E ). Зауважимо, що для
порожнього відношення R множина )(RIm непорожня, точніше }{)( 0RIm = .
Зрозуміло, що )(RIm – непорожня підмножина натуральних чисел, скінченна (тобто
обмежена зверху) або нескінченна (тобто необмежена зверху). В будь-якому випадку ця множина
має найменший елемент, який позначено як )(Rmin . Найбільшого ж елемента множина )(RIm
може і не мати, тому вводиться позначення, в якому ∞ – деякий елемент, що не належить множині
натуральних чисел:
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 69
∞
=
.,
,)(),(
)(
інакше
множина скінченна RIm якщо RIm множини елемент найбільший
Rmax
По суті множину натуральних чисел N зі стандартним порядком ≤ поповнили найбільшим
елементом ∞ та перетворили її в повну решітку ≤>′< ,N , де }{∞∪=′ NN
def
, причому ∞<n для
всіх Nn∈ .
Безпосередньо з означень випливають рівності:
∏=)(Rmin )(RIm , ∐=)(Rmax )(RIm , (*)
де символи ∐,∏ використовуються для позначення інфімумів та супремумів відповідно в повній
решітці N′ (при перевірці рівностей (*) для оператора )(Rmax треба розглянути випадки
скінченної та нескінченної множини )(RIm ).
Зауважимо: для виконання рівностей (*) також суттєва непорожність множини E , бо саме з
непорожності множини E випливає непорожність числової множини )(RIm , а зазначені рівності
для порожньої множини )(RIm (тобто для порожніх множин E , R ) згідно з стандартними
домовленостями щодо точних граней порожньої множини (супремум порожньої множини співпадає
с найменшим елементом, а інфімум – з найбільшим [10]) приймають вигляд ∞=)(Rmin ,
0Rmax =)( . Зрозуміло, що розумно інтерпретувати цей граничний випадок важко; крім того,
наприклад, п. 1 подальшої леми 1 просто не виконується для порожнього відношення на порожніх
множинах.
3. Логічний зв’язок між значеннями операторів min та max на взаємоінверсних відношеннях
Основна задача полягає в дослідженні логічного зв’язку між значеннями введених операторів на
вихідному відношенні ( )R та на відношенні, оберненому до вихідного (інверсному відношенні 1R− ).
Нехай R – тип зв’язку між типами сутностей E та F , )( 11 max,min і )( 22 max,min – пари
значень обмежень min та max простої кардинальності (для типів сутностей E та F відповідно.
Використовуючи графічну нотацію Чена [1], на рис. 1 зображено даний тип зв’язку.
R E F
(min1,max1) (min2,max2)
Рис. 1. Тип зв’язку R між типами сутностей E і F з відповідними значеннями min та max
простої кардинальності
При розгляді значень min та max простої кардинальності цікаво знайти логічні зв’язки між
парами значень )( 11 max,min і )( 22 max,min або довести зворотне (тобто підтвердити або
заперечити необхідність перевірки їх сумісності при побудові відповідного типу зв’язку).
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 70
Ця задача буде розв’язана в наступній теоремі, доведення якої спирається на леми про
властивості операторів maxmin, .
Лема 1. Для довільного бінарного відношення R та непорожньої множини E , такої, що
E)R(2
1 ⊆π , виконуються такі твердження:
1. )()( RmaxRmin ≤ ; більш того, 2|)(|)()( ≥⇔< RImRmaxRmin , зокрема,
)()()( RmaxRminRmax <⇒∞= .
2. 1|)(|)()( =⇔= RImRmaxRmin ; тобто ( )][][,)()( yRxREyxyxRmaxRmin =⇒∈∀⇔= .
3. Нехай k – таке натуральне число, що kRmaxRmin == )()( , тоді }{)( kRIm = , тобто
( )k]x[RExx =⇒∈∀ .
4. Нехай k – таке натуральне число, що }{)( kRIm = (тобто )][( kxRExx =⇒∈∀ ); тоді
kRmaxRmin == )()( .
5. 0)()( ==⇔∅= RmaxRminR ; більш того, 0)()()()( 11 ====⇔∅= −− RmaxRminRmaxRminR
характеристична ознака порожнього відношення).
6. 0)()(2
1 =⇔⊂ RminERπ , 0)()(2
1 >⇔= RminERπ .
7. 2)()()(0 2
1 ≥⇒<< RRmaxRmin π .
8. )(і)()( 2
2
2
1 RRRmax ππ⇒∞= злічені.
9. R – функціональне відношення ⇔ 1)( ≤Rmax (характеристична ознака функціональних
бінарних відношень). �
Доведення. Нерівність )()( RmaxRmin ≤ з п. 1 безпосередньо випливає з рівностей (*);
тому далі розглядається еквівалентність, почнемо з необхідності. Нехай виконується строга
нерівність )()( RmaxRmin < . Треба показати, що множина )(RIm містить щонайменше 2
елементи. Дійсно, ця множина непорожня, а якщо ж вона одноелементна, то, згідно з рівностями (*),
її точні грані збігаються з єдиним елементом множини, тобто )()( RmaxRmin = , що суперечить
припущенню. Розглянемо достатність: нехай множина )(RIm містить щонайменше 2 елементи.
Треба показати, що тоді )()( RmaxRmin < . Дійсно, нехай m,n різні елементи множини )(RIm ;
покладемо для визначеності, що mn < . Залишається врахувати очевидні нерівності
)()( RmaxmnRmin ≤<≤ .
Зауважимо: по суті, встановлена еквівалентність є наслідком наступної загальнозначної
характеристичної властивості одноелементних множин у частково впорядкованих множинах, що
містять щонайменше 2 елементи: 1=⇔∏= XXX∐ .
Нарешті остання імплікація п. 1 випливає з установленої еквівалентності, оскільки рівність
∞=)(Rmax означає, що множина )(RIm нескінченна. ▫
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 71
Перша еквівалентність п. 2 випливає з еквівалентності п. 1 з урахуванням непорожності
множини )(RIm (треба просто перейти до заперечень у кожній з частин еквівалентності п. 1).
Друга еквівалентність цього пункту випливає з першої, оскільки праві частини цих двох
еквівалентностей еквівалентні. ▫
Пп. 3, 4 випливають з п. 2 та означення операторів maxmin, (у випадку одноелементної
множини )(RIm дані оператори просто вибирають єдиний елемент цієї множини). ▫
Доведемо необхідність у першій еквівалентності п. 5: нехай ∅=R , тоді повний образ
вигляду ][xR для всіх елементів Ex∈ також порожній, тобто }0{)( =RIm ; залишається
застосувати п. 4. Розглянемо достатність: нехай 0)()( == RmaxRmin . Тоді, згідно з п. 3
( )0][ =⇒∈∀ xRExx , тобто повний образ ][xR для всіх елементів Ex∈ порожній, а це може
виконуватись тільки для порожнього відношення R .
Друга еквівалентність випливає з першої (бо інверсія порожнього відношення знову порожня).▫
Розгляд п. 6 почнемо з необхідності для першої еквівалентності. Нехай ER ⊂)(2
1π , тоді
найдеться елемент Ex∈ , такий, що )(2
1 Rx π∉ ; отже повний образ ][xR порожній, тобто
)(0 RIm∈ . Оскільки 0 найменший елемент, то ∏ == 0)()( RImRmin . Переходимо до
достатності: нехай 0)( =Rmin , тоді, оскільки повна решітка ≤>′< ,N цілком упорядкована (а
найменший елемент множини співпадає з інфімумом цієї ж множини), то )(0 RIm∈ . Звідси
випливає існування елемента Ex∈ , такого, що 0|][ =xR| , тобто повний образ ][xR порожній.
Очевидно, що )(2
1 Rx π∉ , тобто ER ⊂)(2
1π .
Друга еквівалентність пункту випливає з першої, в першій еквівалентності треба перейти до
заперечень в обох частинах (урахувавши, що завжди 0)( ≥Rmin ). ▫
Розглянемо п. 7. Так як )(0 Rmin< , то, згідно з другою еквівалентністю п. 6, ER =)(2
1π ;
оскільки ж )()( RmaxRmin < , то, згідно з еквівалентністю п. 1, 2|)(| ≥RIm . Оскільки за означенням
}][{)( ExxR
def
RIm ∈= , тобто в нашому випадку )}(][{)( 2
1 RxxRRIm π∈= , то, очевидно, що
22
1 ≥|)R(|π . Зауважимо, що обернути імплікацію пункту не можна, як показують прості приклади. ▫
Імплікація п. 8 доводиться від супротивного: нехай ∞=)(Rmax , але хоча б одна з проекцій
відношення )(2
1 Rπ , )(2
2 Rπ скінченна. У першому випадку, коли проекція )(2
1 Rπ скінченна,
треба застосувати кускову схему, яка випливає безпосередньо з означень (наприклад, в першому
рядку треба врахувати, що ∅=][xR для всіх )(\ 2
1 REx π∈ ):
=∈
⊂∈
=
.ER якщо RxxR
ER якщо RxxR
RIm
)()},(|][|{
,)(},0{)}(|][|{
)(
2
1
2
1
2
1
2
1
ππ
ππ ∪
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 72
Отже, якщо проекція )(2
1 Rπ скінченна, то і множина )(RIm скінченна, а, значить, )(Rmax
– натуральне число. Прийшли до протиріччя.
У другому випадку, коли проекція )(2
2 Rπ скінченна, треба застосувати включення
)(][ 2
2 RxR π⊆ для всіх Ex∈ , яке випливає безпосередньо з означень; з цього включення
випливає нерівність |)(||][ 2
2 RxR| π≤ для всіх Ex∈ . Таким чином, з скінченності множини )(2
2 Rπ
випливає скінченність і множини )(RIm ; значить, і для цього випадку )(Rmax – натуральне число.
Прийшли до протиріччя.
Зауважимо, що доведена імплікація не обертається в загальному випадку; найпростіший
приклад – бієкція між двома зліченими множинами (згідно з наступним пунктом оператор max
прийме одиничне значення для цього випадку). ▫
Нарешті, доведемо необхідність в еквівалентності п. 9. Нехай відношення R
функціональне, тоді повний образ вигляду ][xR для всіх Ex∈ містить щонайбільше один
елемент, тобто [ ] 1≤xR для всіх Ex∈ . Таким чином, }1,0{)( ⊆RIm , звідки випливає, що
1)( ≤Rmax .
Достатність доводиться від супротивного: нехай 1)( ≤Rmax , але відношення не є
функціональним. Тоді існує елемент Ex∈ , такий, що 2|][| ≥xR ; нехай |][| xRp
def
= , тоді
)(RImp∈ , причому 2≥p . Нарешті, з формул (*) випливає, що 2)( ≥≥ pRmax – прийшли до
протиріччя. ▫ �
Лема 2 (про значення операторів maxmin, на скінченному універсальному відношенні).
Нехай 0>= pE , 0>= kF , а FEkpU
def
×=),( – універсальне відношення на множинах E ,
F , тоді kRmaxRmin == )()( та pRmaxRmin == −− )()( 11 . �
Доведення. Згідно з означенням універсального відношення, має місце kxR =|][| для всіх
Ex∈ . Отже, рівності kRmaxRmin == )()( випливають з п. 4 попередньої леми 1. Рівності для
оберненого відношення доводяться повністю аналогічно. �
Значення операторів maxmin, залежать не тільки від аргументу-відношення (в попередніх
позначеннях R ), а й від параметра – множини, якій належать перші компоненти пар відношення
(множини E ); тому точніше було б писати, наприклад, )(RminE замість )(Rmin та )(RImE замість
)(RIm 1. Наступна лема уточнює залежність значень операторів maxmin, від вказаної множини-
параметра.
1 Якщо бути точним, то треба розглядати і бінарне відношення разом з відповідними множинами, з яких
обираються компоненти пар відношення.
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 73
Лема 3 (про залежність значень операторів maxmin, від множини-параметра). Нехай
відношення R та множини E , F , E′ такі, що FER ×⊆ та EE ′⊂ ; тоді 0=′ )R(minE та
)()( RmaxRmax EE ′= . �
Доведення. Так як ∅=][xR для всіх E\Ex ′∈ , то, очевидно, що }0{)()( ∪RImRIm EE =′ ;
тобто множина )(RImE поповнюється найменшим елементом відповідної решітки. Зрозуміло, що
таке поповнення не впливає на супремум множини (якщо бути більш точним, то треба спиратися на
те, що )(RImE є конфінальною підмножиною множини )(RImE′ , супремуми таких множин
співпадають [9, твердження 3]) та призводять до нульового значення інфімуму:
( ) ( )RImRIm E'E ∐∐ = , ( ) 0=∏ RIm 'E . Залишається застосувати рівності (*). �
Отже, власне розширення множини-параметра E впливає тільки на значення оператора
min , яке з можливо ненульового стає нульовим. Зауважимо, що розширення множини F взагалі
не впливає на значення операторів.
Наступна лема розглядає випадок, коли відношення має структуру об’єднання попарно
сумісних відношень; відношення сумісності ≈ розуміється, згідно з роботою [9], тобто в позначеннях
цієї роботи ,X|VX|UVU
def
=⇔≈ де VUX
def
2
1
2
1 ππ ∩= – перетин проекцій вихідних бінарних
відношень V ,U за першою компонентою, а X|V,X|U – обмеження бінарних відношень за
вказаною множиною.
У наступній лемі виражаються значення операторів maxmin, на вихідній множині через
значення тих самих операторів на множинах з об’єднання.
Лема 4 (про об’єднання попарно сумісних відношень). Нехай відношення R таке, що
i
Ii
RR
∈
= ∪ , причому всі відношення iR , Ii ∈ попарно сумісні та непорожні, тобто ji RR ≈ для всіх
Ij ,i ∈ 2. Тоді ( )iE
Ii
E RmaxRmax
i∈
= ∐)( , де множини iE,E такі, що ER ⊆)(2
1π , ii ER ⊆)(2
1π для
всіх Ii ∈ . Крім того, позначаючи проекції по першій компоненті відношень R та iR через G та iG
відповідно, маємо рівність ( )iG
Ii
G Rmin)R(min
i∈
∏= .�
Доведення. Для доведення встановимо допоміжну рівність:
][][ xRxR i= для всіх Ii ∈ та iGx∈ . (**)
Фіксуємо довільні Ii ∈ та елемент iGx∈ . Включення ][][ xRxR i⊇ випливає з монотонності
повного образу [8, твердження 2, п. 1] і тому залишається встановити обернене включення. Це
можна зробити безпосередньо: нехай ][xRy∈ ; оскільки повний образ є дистрибутивним відносно
об’єднань [8, твердження 2, п. 2], то існує індекс Ij ∈ , такий, що ][xRy j∈ . Залишається
2 З огляду на рефлексивність відношення сумісності немає потреби вимагати нерівність j ,i .
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 74
врахувати, по-перше, сумісність відношень iR , jR ; по-друге, належність jGx∈ , з якої випливає
належність )R()R(GGx ijij
2
1
2
1 ππ ∩=∩∈ ; та наступну загальнозначну властивість відношення
сумісності (точніше критерій сумісності відношень): ][][ xVxUVU =⇔≈ для всіх
)()( 2
1
2
1 VUx ππ ∩∈ (яка випливає безпосередньо з означення сумісності). Отже, ][][ xRxRy ij =∈ .
Включення ][][ xRxR i⊆ встановлено, а з ним встановлена і рівність (**).
Тепер встановимо рівність
( )RImRIm
iG
Ii
G
∈
= ∪)( . (***)
Дійсно,маємо такий ланцюжок рівностей:
∪
Ii
iG GxxRGxxRRIm
∈
∈=∈= }|][|{}|][|{)( = ∪∪
Ii
iG
Ii
ii RImGxxR
i
∈∈
=∈ )(}|][|{ .
Перша рівність випливає з означення множини )(RImG ; друга – з рівності i
Ii
GG
∈
= ∪ , яка, у
свою чергу, випливає з рівності i
Ii
RR
∈
= ∪ та дистрибутивності проекції відносно об’єднань; третя –
з раніше встановленої допоміжної рівності (**); нарешті, четверта, остання рівність, – з означення
множини )( iiG RIm .
Тепер встановимо шукану рівність ( )iG
Ii
G Rmin)R(min
i∈
∏= . Дійсно, з рівності (***) та
відомого твердження про точні грані об’єднання підмножин частково впорядкованої множини [10,
§ 1, теорема 9] та [9, лема 3 про супремум об‘єднання] випливають рівності
( ) ( ){ } ( )iG
Ii
iGGG RminIiRRRmin
ii ∈
∏=∈∏∏=∏= |ImIm)( .▫
Розглянемо другу шукану рівність ( )iE
Ii
E RmaxRmax
i∈
∏=)( . Рівність для супремумів
( )iG
Ii
G Rmax)R(max
i∈
∏= доводиться повністю аналогічно встановленій рівності для інфімумів.
Залишається врахувати включення EG ⊆ , ii EG ⊆ для всіх Ii ∈ та застосувати лему 3 про
залежність значень операторів від множини-параметра: == )()( RmaxRmax GE
( ) ( )iE
Ii
G
Ii
RmaxRmax
ii ∈∈
== ∐∐ . ▫�
Наступна теорема відповідає на питання сумісності значень операторів maxmin, на
вихідному (початковому) відношенні та на оберненому до нього відношенні.
Всі варіанти значень maxmin, , побудовані з урахуванням нерівності )R(max)R(min ≤
(лема 1, п. 1), наведені в нижчеподаній табл. 1, рядки якої відповідають вихідному відношенню R , а
стовпчики – оберненому відношенню 1−R . У цій таблиці випадки, коли значення оператора max
дорівнює ∞ , вказані явно; отже нерівність pp ′≥ означає, що не тільки p′ , а і p натуральне
число.
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 75
Таблиця 1. Всі варіанти значень maxmin, для відношень 1−R,R та їх сумісність
)Rmin(p -
def
1====′′′′ , )Rmax(p -
def
1====
0==′ pp 0>=′ pp
1
0
≥
=′
p
,p
∞=
=′
p
,p 0
pp
,p
′≥
≥′ 1
∞=
≥′
p
,p 1
0==′ kk + – – – – –
0>=′ kk – + + + + +
10 ≥=′ k,k – + + + + +
∞==′ k,k 0 – + + + + +
kk,k ′≥≥′ 1 – + + + + +
)(Rmin
def
k =′
)(Rmax
def
k =
∞=≥′ k,k 1 – + + + + +
Теорема 1 (про сумісність значень операторів maxmin, на взаємоінверсних відношеннях).
Для комірок таблиці, позначених + (–), існують (відповідно не існують) відношення з указаними
значеннями maxmin, . �
Доведення. Заповнення таблиці повинно бути симетричним відносно головної діагоналі,
оскільки в симетричних комірках відношення 1−R,R просто міняються ролями. Тому доведенню
підлягають тільки заповнення комірок, розташованих для визначеності на головній діагоналі та
вище неї. Номер варіанта (номер комірки) записується ),( ki , де i – номер рядка, а k – номер
стовпця.
Заповнення першого рядка випливає з п. 5 леми 1 про порожнє відношення. Очевидно, що в
першому рядку існує відповідне відношення (а саме порожнє відношення) тільки для випадку (1,1). ▫
Відношення для решти випадків будуються об’єднанням скінченних універсальних
відношень (лема 2) з використанням леми 4; причому бінарні відношення, які складають об’єднане
відношення в формулюванні цієї леми, взагалі не будуть перетинатися; тобто вимога попарної
сумісності буде автоматично виконуватися.
Надалі для кожного випадку будується відповідне відношення, а для деяких з них
(представницьких випадків) подаються графічні ілюстрації та проводяться доведення.
Для випадку (2,2), згідно з лемою 2, можна побудувати універсальне відношення
FER ×= , де }{ 21 px...,,x,xE
def
= та }...,,,{ 21 kyyyF
def
= , причому елементи p,...,xx1 та ky,...,y1
покладаються попарно різними. ▫
Для випадку (2, 3) будується відношення FER
def
′×= , де }{ 21 px...,,x,xE
def
= та
}{ 21 y,y...,,y,yF k
def
= , }{\}{ 21 yFy...,,y,yF k
def
==′ , причому елементи p,...,xx1 та ,y,...,yy k1
покладаються попарно різними (рис. 2).
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 76
Згідно з лемою 2 (про універсальне відношення) та
лемою 3 (про залежність від множини параметра, ця лема
застосовується для відношення 1−R ), відношення R
потрібне. ▫
Для випадку (2, 4) відношення будується так:
i
i
RR
def ∞
=
=
1
∪ , де }{}{),( 11
i
k
ii
i
i
і ,...,yy,...,xxkіUR
def
×== ,
причому елементи вигляду ,y,yx i
j
i
j покладаються попарно
різними; далі }{)( 21
2
2
2
1
1
1
2
1 ,...,...,x,x,...,x,x,xxRE i
i
ii
def
== π та
}{}{)( 1
22
1
11
1
2
2 ,...,y,...y,...,y,...y,y,...yyyRF i
k
i
kk
def
== ∪π (рис. 3). Покажемо, що це відношення R
шукане.
Нехай }{ 1
2
1
i
i
i
ii ,...,xxRE
def
== π для ,...,i 21= Так як
проекції за першою компонентою різних відношень вигляду
iR , де ,...,i 21= , не перетинаються, то, згідно з лемами 4 та
2, отримуються рівності ( ) ==
=
iE
i
E RmaxRmax
i,...2,1
)( ∐
kk
i
==
= ,...2,1
∐ . Аналогічно встановлюються рівності
( ) ==
=
iE
i
E RRmin
i
min)(
,...2,1
∐ kk
i
=
= ,...2,1
∐ .
Залишається показати, що обернене відношення 1−R
шукане. Нехай }{)( 1
2
2
i
k
i
ii ,...yyR
def
F == π для ,...,i 21= та
==′ )(2
2 RF
def
π =}{ 1
22
1
11
1 ,...,...y,...,y,...y,y,...yy i
k
i
kk }{\ yF . Тоді,
згідно з лемами 4, 2, отримуються рівності
( ) ∞===
=
−
=
′ iRmax)R(max
,...,i
iF
,...,i
-
F i 21
1
21
1
∐∐ . Нарешті, з леми
3 (нагадаймо, що FF ⊂′ ) випливають рівності
∞== ′ )()( 11 -
F
-
F RmaxRmax та 0)( 1 =-
F Rmin .▫
Для випадку (2, 5) відношення R будується так: ),(),( kpUkpU
def
R ∪′= , де
}{}{),( 11 kp ,...,yy,...,xx
def
kpU ×=′ ′ та }{}{),( 11 kp y,...,yx,...,x
def
kpU ′′×′′= ; далі покладаємо
E
F
1x
px
1y
2y
ky
y
...
Рис. 2. Відношення для
випадку (2, 3)
1
1x
1
1y
1
2y
1
ky
...
2
1x
іx1
іy1
іy2
i
ky
...
і
іx
...
),( kіU
2
1y
2
2y
2
ky
...
2
2x
),( kU 1
),( kU 2
..................................................
..........................................
Е
F
.y
Рис. 3. Відношення для
випадку (2, 4)
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 77
}{ 2121 pp x...,,x,x,x...,,x,xE
def
′′′= ′ та }{ 2121 kk y...,,y,y,y...,,y,yF
def
′′′= , причому елементи вигляду ji x,x ′
та ji y,y ′ попарно різні. Доведення завершується аналогічно попереднім випадкам. ▫
Для випадку (2, 6) відношення R будується так: i
i
RR
def ∞
=
=
1
∪ , де =−+′= ),1( kipUR
def
і
}{}{ 111
i
k
ii
ip
i ,...,yy,...,xx ×= −+′ , ,...,,i 321= , причому елементи вигляду i
j
i
j ,yx покладаються попарно
різними; далі }{)( 121
2
1
2
1
11
1
2
1 ,...,...,x,x,...,x,...,xx,...,xxRE i
ip
ii
pp
def
−+′+′′== π та == )(2
2 RF
def
π
}{ 1
22
1
11
1 ,...,...,y,...,y,...y,y,...yy i
k
i
kk= . Доведення завершується аналогічно попереднім випадкам. ▫
Для випадку (3,3), одного з найпростіших, відношення будується так:
}{}{),( 11 kp ,...,yy,...,xxkpUR
def
×== , ( ) { } }{ 1
2
1 ,x,...,xxxRE p
def
== ∪π та ( ) == }{2
2 yRF
def
∪π
}{ 1 ,y,...,yy k= , причому елементи ,x,y,...,y,y,...,xx kp 11 вважаються попарно різними. ▫
Для випадку (3, 4) відношення будується так: i
i
RRR
def ∞∞∞∞
====
∪∪∪∪====
1
0 ∪ , де
}{}{),1( 00
1
0
0 k,...,yyxkUR
def
×== та для ,...,,i 321= }{}{)1,( 1
ii
i
i
і y,...,xxiUR
def
×== , причому
елементи вигляду ,x,y,y,y,xx i
j
i
j
00 покладаються попарно різними; далі
}{}{)( 21
2
2
2
1
1
1
02
1 ,...,x,...,x,x,...,x,x,x,xxxR
def
E i
i
ii=∪= π та =∪= }{)(2
2 yR
def
F π
}{ 2100
1 ,...,y,...,y,y,y,...yy i
k= . Доведення завершується аналогічно попереднім випадкам. ▫
Для випадку (3, 5), який розглядається аналогічно
випадку (2,5), відношення R будується так:
)1,(),( pUkpUR
def
∪′= , де
def
kpU =′ ),(
}{}{ 11 kp ,...,yy,...,xx
def
×= ′ та }{}{)1,( yx,...,xpU lp
def
′×′′= ; далі
}{ 2121 ,xx...,,x,x,x...,,x,xE pp
def
′′′= ′ та }{ 21 y,y...,,y,yF k
def
′= ,
причому елементи вигляду y,,x,yx,x iji ′′ покладаються
попарно різними (рис. 4). Необхідно показати, що так
побудоване відношення R шукане.
Нехай }{ 11 p,...,xxE
def
′= , }{ 12 px,...,xE
def
′′= та
1x
1y
2y
ky
... ...
1x′
y ′
px′
...
)1,(pU
px ′ ),( kpU ′
Е
F
x
Рис. 4. Відношення R для
випадку (3, 5)
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 78
21 EEE ∪=′ , а також }{ 11 k,...,yyF
def
= та }{2 yF
def
′= . Так як проекції за першою компонентою
відношень ),( kpU ′ та )1,( pU не перетинаються, то, згідно з лемами 4, 2, отримуються рівності
====′′′′ )R(maxE
( )( ) ( )( ){ } { } k,kp,1Umax,k,pUmax E
'
E === 1
21
∐∐
(нагадаймо, що для випадку (3,5) виконується за припущенням нерівність 1≥k ). Аналогічно
встановлюються рівності )(RminE ∏∏ ==′= 1}1,{))}1,(()),,(({ kpUminkpUmin
21 EE (необхідно
зауважити, що насправді знайдене конкретне значення )(RminE несуттєве).
Застосовуючи лему 3 і враховуючи власне включення EE ⊂′ , отримуються рівності
kRmaxRmax EE == ′ )()( та 0)( =RminE .
Залишається показати, що обернене відношення 1−R шукане. Так як проекції за другою
компонентою відношень )( ,kpU ′ та )p,(U 1 не перетинаються, то, згідно з лемами 2, 4
(враховуючи очевидний факт, що відношення, обернене до універсального відношення, знову буде
універсальним), отримуються рівності
∐∐
∐
ppppUmaxpkUmax
pUmaxkpUmaxRmax
21
21
FF
FF
-1
F
=′=′=
=′= −−
},{))},1(()),,(({
}))1,((,)),(({)( 11
.
Аналогічно встановлюються рівності
∏∏
∏
=′=′=
=′= −−
ppppUminpkUmin
pUminkpUminRmin
21
21
FF
FF
-1
F
},{))},1(()),,(({
}))1,((,)),(({)( 11
. ▫
Для випадку (3, 6) відношення будується так: i
i
RR
def ∞
=
=
0
∪ , де
}{}{),( 00
1
00
10 kp ,...,yy,...,xxkpUR
def
×=′= ′ та }{}{1 1
ii
ip
i
і y,...,xx)i,pU(R
def
×=+′= +′ для ,...,,i 321= ;
причому елементи вигляду ,x,y,yx i
j
i
j
0 покладаються попарно різними; далі
}{}{)( 21
1
1
1
1
00
1
2
1 ,...,x,...,x,x,...,x,...,x,x,...,xxxRE i
ip
ii
pp
def
+′+′′== ∪π та == )(2
2 RF
def
π
}{ 2100
1 ,...,...,y,y,y,...yy i
k= . Доведення завершується аналогічно попереднім випадкам. ▫
Для випадку (4, 4) відношення будується так: i
i
RR
def ∞
=
=
1
∪ , де
}{}{)( 11
i
i
ii
i
i
і ,...,yy,...,xxi,iUR
def
×== для ,...,,i 321= , причому елементи вигляду ,x,y,yx i
j
i
j
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 79
покладаються попарно різними; далі }{}{)( 21
2
2
2
1
1
1
2
1 ,...,x,...,x,x,...,x,x,xxxRE i
i
ii
def
== ∪π та
F
def
==== (((( )))) {{{{ }}}} {{{{ }}}}y,...,y,...,y,...,y,y,yyR i
i
i
1
2
2
2
1
1
1
2
2 ====∪∪∪∪π . ▫
Для випадку (4, 5) відношення будується так: i
i
RR
def ∞∞∞∞
====
====
0
∪ , де
}{}{)1,( 000
10 y,...,xxpUR p
def
×=′= ′ та }{}{),( 11
i
i
ii
p
i
і ,...,yy,...,xxipUR
def
×== для ,...,,i 321==== , причому
елементи вигляду ,x,y,y,xx i
j
i
jj
00 покладаються попарно різними; далі
}{}{)( 2
11
1
00
1
2
1 ,...,x,...,x,x,...,x,...,x,x,...,xxxRE i
p
ii
plp
def
′== ∪π та ======== )R(F
def
2
2π
},{ 1
2
2
2
1
1
1
0 ,...,...,y,...,yy,y,yy i
i
i= . ▫
Для випадку (4, 6) відношення будується так: i
i
RR
def ∞∞∞∞
====
====
1
∪ , де
}{}{1 111
i
i
ii
ip
i
і ,...,yy,...,xx,i)ipU(R
def
×=−+′= −+′ , ,...,,i 321==== , причому елементи вигляду ,x,yx i
j
i
j
покладаються попарно різними; далі =∪= }{)(2
1 xRE
def
π
}{ 121
2
1
2
1
11
1 ,...,x,...,x,x,...,x,...,xx,...,xx i
ip
ii
pp −+′+′′= та }{)( 1
2
2
2
1
1
1
2
2 ,...,...,y,...,y,y,yyRF i
i
i
def
== π (рис. 5).
Необхідно показати, що так побудоване відношення R шукане.
Нехай ,...,,x,...,x,...,x,x,...,xxR
def
E ii
pp 21
2
1
2
1
11
1
2
1 {)( +′′==′ π
}1,...xi
ip −+′ та }{ 11
2
1
i
ip
i
ii ,...,xxRE
def
−+′== π для ...,,i 321==== Так як
проекції за першою компонентою різних відношень вигляду
iR , де ,...,i 21==== , не перетинаються, то, згідно з лемами 4, 2,
отримуються рівності =′ )(RmaxE ( ) =
=
iE
i
Rmax
i,...2,1
∐
∞==
=
i
i ,...2,1
∐ . Аналогічно встановлюються рівності
(((( )))) ====∏∏∏∏====
====
′′′′ iE
,...,i
E Rmin)R(min
i21
1
,...2,1
=∏
=
i
i
(треба зауважити,
що насправді знайдене конкретне значення )(RminE′
несуттєве).
Застосовуючи лему 3 і враховуючи власне включення EE ⊂⊂⊂⊂′′′′ , отримуються рівності
∞== ′ )()( RmaxRmax EE та 0)( =RminE .
1
1x
1
1y
...
1
px ′
)1,(pU ′
..................................................
..........................................
Е F
x
іx1
іy1
іy2
i
iy
і
ipx 1−+′
...
),1( iipU −+′
...
Рис. 5. Відношення для
випадку (4, 6)
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 80
Залишається показати, що обернене відношення 1−−−−R шукане. Нехай
}{)( 1
2
2
i
i
i
ii ,...,yyR
def
F == π для ...,,i 321==== ; тоді, згідно з тими самими лемами 4, 2, отримуються
рівності ( ) ( ) { } ∞=++=−+==
=
−
=
,...2,1,1)( ''''
,...2,1
1
,...2,1
1 pppipRmaxRmax
i
iF
i
-
F i
∐∐∐ .
Аналогічно встановлюються рівності
( ) ( ) { } '''''
,...2,1
1
,...2,1
1 ,...2,1,1)( ppppipRminRmin
i
iF
i
-
F i
=++∏=−+∏=∏=
=
−
=
. ▫
Для випадку (5, 5), подібного до випадку (2,5), відношення R будується так:
),(),( kpUkpU
def
R ∪′′= , де }{}{),( 11 kp ,...,yy,...,xx
def
kpU ′′ ×=′′ та
def
kpU =),(
}{}{ 11 kp y,...,yx,...,x
def
′′×′′= ; далі покладемо }{ 2121 pp x...,,x,x,x...,,x,x
def
E ′′′= ′ та
}{ 2121 kk y...,,y,y,y...,,y,y
def
F ′′′= ′ , причому елементи вигляду ji x,x ′′′′ та ji y,y ′′′′ вважаються попарно
різними. ▫
Для випадку (5, 6), подібного до випадку (3, 6), відношення будується так: i
i
R
def
R
∞∞∞∞
====
====
0
∪ , де
}{}{),( 00
1
00
10 kp ,...,yy,...,xxkpU
def
R ′′ ×=′′= та }{}{( 11
i
k
ii
ip
i
і ,...,yy,...,xxi,k)pU
def
R ×=+′= +′ для
,...3,2,1=i , причому елементи вигляду i
j
i
j ,yx покладаються попарно різними; далі
}{)( 21
1
1
1
1
00
1
2
1 ,...,...,x,x,...,x,...,x,x,...,xxRE i
ip
ii
pp
def
+′+′′== π та ======== )R(F
def
2
2π
}{ 1
11
1
00
1 ,...,...,y,...,y,...,y,y,...yy i
k
i
kk′= . ▫
Для випадку (6, 6) нехай ),( kpmaxi
def
max ′′= , тоді відношення побудуємо так: i
i
RR
def ∞∞∞∞
====
====
0
∪ , де
}{}{),( 00
1
00
10 kp ,...,yy,...,xxkpUR
def
′′ ×=′′= та =++= )( maxmax ii,iiUR
def
і
}{}{ 11
i
ii
ii
ii
i
maxmax
,...,yy,...,xx ++ ×= для ,...,,i 321==== , причому елементи вигляду i
j
i
j ,yx покладаються
попарно різними; далі }{)(
maxmax 21
1
1
1
1
00
1
2
1 ,...,...,x,x,...,x,...,x,x,...,xxRE i
ii
ii
ip
def
++′== π та == )(2
2 RF
def
π
}{ 1
1
1
1
1
00
1 ,...,...,y,...,y,...,y,y,...yy i
ii
i
ik maxmax ++′= . ▫ �
З цієї теореми випливає, що, за винятком спеціального випадку порожнього відношення
(дійсно, при ∅∅∅∅====R відношення 1−−−−R,R просто співпадають), немає логічного зв’язку між
значеннями операторів maxmin, на вихідному та оберненому відношеннях; більш точно: для
довільного розподілу значень операторів (крім розподілів, що відповідають коміркам табл. 1,
ISSN 1028-9763. Математичні машини і системи, 2009, № 4 81
заповненим –) існує відношення, на якому ці значення досягаються. Причина такого положення
полягає в тому, що повні образи одноелементних множин несуть не просто локальну інформацію
про відношення, а локальну числову інформацію.
Розглянемо це питання більш докладно. Добре відомий логічний зв’язок між відношенням та
відношенням, оберненим до нього: відношення функціонально (ін’єктивно) тоді і тільки тоді, коли
обернене відношення ін’єктивно (відповідно функціонально). Цей простий факт відмічений,
наприклад, в [8, твердження 1].
Згідно з п. 9 леми 1,
функціональність харак-
теризується значенням
оператора max, але для
ін’єктивності ситуація прин-
ципово інша: на рис. 6
наведені прості приклади
ін’єктивного та неін’єктивного
відношень, на яких опе-
ратори max, min мають однакові значення.
4. Висновки
Практичний результат даної теореми полягає у тому, що при побудові бінарного типу зв’язку (який
містить принаймні один зв’язок) та накладанні на нього min та max обмежень кардинальності
(необмежена кардинальність) не існує логічного зв’язку між значеннями даних обмежень.
Основне завдання подальшої роботи – отримання аналогу теореми 1 для багатосторонніх
типів зв’язків у моделі „сутність-зв’язок”.
СПИСОК ЛІТЕРАТУРИ
1. Chen P.P. The entity-relationship model – towards a unified view of data // ACM Transactions on Database
Systems. – 1976. – Vol. 1, N 1. – P. 9 – 36.
2. Ferg S. Cardinality concepts in entity-relationship modeling // Proceeding of the 10th International Conference on
Entity-Relationship Approach. – 1991. – Р. 1 – 30.
3. Thalheim B. Fundamentals of cardinality constraints // Proceeding of the 11th International Conference on the
Entity-Relationship Approach. – 1992. – Р. 7 – 23.
4. Lenzerini M., Santucci G. Cardinality constraints in the entity-relationship model // Proceeding of the International
Conference on the Entity-Relationship Approach to Software Engineering. – 1983. – Р. 529 – 549.
5. Hartmann S. Reasoning about participation constraints and Chen’s constraints // Conferences in Research and
Practice in Information Technology. – 2003. – Vol.17. – Р. 8 – 16.
6. Буй Д.Б., Сільвейструк Л.М. Модель „сутність-зв’язок”: формалізація сутностей та зв’язків // Вісник Київського
університету. Серія: фіз.-мат. науки. – 2006. – Вип. 3. – С. 143 – 152.
7. Buy D., Silveystruk L. Formalization of structural constraints of relationships in model „entity-relationship” //
International journal Information theories & applications. – Sofia. – 2007. – Vol. 14, N 4. – P. 343 – 349.
8. Буй Д.Б., Кахута Н.Д. Властивості теоретико-множинних конструкцій повного образу та обмеження // Вісник
Київського університету. Серія: фіз.-мат. науки. – 2005. – Вип. 2. – С. 232 – 240.
9. Буй Д.Б., Кахута Н.Д. Властивості відношення конфінальності та устрій множини часткових функцій // Вісник
Київського університету. Серія: фіз.-мат. науки. – 2006. – Вип. 2. – С. 125 – 135.
10. Скорняков Л.А. Элементы теории структур. – Москва: Наука, 1982. – 158 с.
Стаття надійшла до редакції 04.12.2008
E F
1x
2x
1y
2y
3y
E′ F′
1x′
2x ′
1y ′
2y ′
4y ′
3y ′
Pис. 6. Приклад ін’єктивного та неін’єктивного відношень, на яких
оператори min , maxмають однакові значення
|