Об инвариантности ключей относительно операций табличных алгебр
Исследована задача инвариантности ключей, в том числе и простых, относительно операций табличных алгебр — современного аналога классических реляционных алгебр Кодда. Показано, что ключи инвариантны относительно операций пересечения, разности, селекции, соединения и деления, при этом для простых ключ...
Saved in:
| Date: | 2015 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/124901 |
| 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: | Об инвариантности ключей относительно операций табличных алгебр / В.Н. Редько, Д.Б. Буй, А.С. Сенченко // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 3-12. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124901 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1249012017-10-12T03:02:42Z Об инвариантности ключей относительно операций табличных алгебр Редько, В.Н. Буй, Д.Б. Сенченко, А.С. Кибернетика Исследована задача инвариантности ключей, в том числе и простых, относительно операций табличных алгебр — современного аналога классических реляционных алгебр Кодда. Показано, что ключи инвариантны относительно операций пересечения, разности, селекции, соединения и деления, при этом для простых ключей инвариантность не выполняется, а также что относительно переименования инвариантны как ключи, так и простые ключи. Найдены необходимые и достаточные условия, при которых ключи, в том числе и простые, инвариантны относительно операций активного дополнения и проекции.Результаты работы представляют теоретический и практический интерес и могут использоваться для выбора оптимальных ключей при проектировании реляционных баз данных. Досліджено задачу інваріантності ключів, в тому числі і простих ключів, відносно операцій табличних алгебр — сучасного аналогу класичних реляційних алгебр Кодда. Показано, що ключі є інваріантними відносно операцій перетину, різниці, селекції, з’єднання і ділення, при цьому для простих ключів інваріантність не виконується, а також що відносно операції перейменування інваріантними є як ключі, так і прості ключі. Знайдено необхідні і достатні умови, за яких ключі, у тому числі і прості, є інваріантними відносно операцій активного доповнення та проекції. Результати роботи представляють теоретичний і практичний інтерес і можуть бути використані для вибору оптимальних ключів при проектуванні реляційних баз даних. The authors analyze the problem of the invariance of keys, including simple keys, with respect to operations of table algebras, a modern analog of classical relational Codd’s algebras. It is shown that the keys are invariant with respect to operations of intersection, difference, selection, join, and division, but for simple keys invariance does not hold. It is shown that keys, including simple keys, are invariant with respect to the operation of renaming. The necessary and sufficient conditions under which the keys, including simple keys, are invariant with respect to operations of projection and active supplement are established. The results of the study are of theoretical and practical interest and can be used to choose optimal keys in design of relational databases. 2015 Article Об инвариантности ключей относительно операций табличных алгебр / В.Н. Редько, Д.Б. Буй, А.С. Сенченко // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 3-12. — Бібліогр.: 9 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124901 004.655 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Редько, В.Н. Буй, Д.Б. Сенченко, А.С. Об инвариантности ключей относительно операций табличных алгебр Кибернетика и системный анализ |
| description |
Исследована задача инвариантности ключей, в том числе и простых, относительно операций табличных алгебр — современного аналога классических реляционных алгебр Кодда. Показано, что ключи инвариантны относительно операций пересечения, разности, селекции, соединения и деления, при этом для простых ключей инвариантность не выполняется, а также что относительно переименования инвариантны как ключи, так и простые ключи. Найдены необходимые и достаточные условия, при которых ключи, в том числе и простые, инвариантны относительно операций активного дополнения и проекции.Результаты работы представляют теоретический и практический интерес и могут использоваться для выбора оптимальных ключей при проектировании реляционных баз данных. |
| format |
Article |
| author |
Редько, В.Н. Буй, Д.Б. Сенченко, А.С. |
| author_facet |
Редько, В.Н. Буй, Д.Б. Сенченко, А.С. |
| author_sort |
Редько, В.Н. |
| title |
Об инвариантности ключей относительно операций табличных алгебр |
| title_short |
Об инвариантности ключей относительно операций табличных алгебр |
| title_full |
Об инвариантности ключей относительно операций табличных алгебр |
| title_fullStr |
Об инвариантности ключей относительно операций табличных алгебр |
| title_full_unstemmed |
Об инвариантности ключей относительно операций табличных алгебр |
| title_sort |
об инвариантности ключей относительно операций табличных алгебр |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2015 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124901 |
| citation_txt |
Об инвариантности ключей относительно операций табличных алгебр / В.Н. Редько, Д.Б. Буй, А.С. Сенченко // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 3-12. — Бібліогр.: 9 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT redʹkovn obinvariantnostiklûčejotnositelʹnooperacijtabličnyhalgebr AT bujdb obinvariantnostiklûčejotnositelʹnooperacijtabličnyhalgebr AT senčenkoas obinvariantnostiklûčejotnositelʹnooperacijtabličnyhalgebr |
| first_indexed |
2025-07-09T02:14:13Z |
| last_indexed |
2025-07-09T02:14:13Z |
| _version_ |
1837133732552638464 |
| fulltext |
Â.Í. ÐÅÄÜÊÎ, Ä.Á. ÁÓÉ, À.Ñ. ÑÅÍ×ÅÍÊÎ
ÓÄÊ 004.655 ÎÁ ÈÍÂÀÐÈÀÍÒÍÎÑÒÈ ÊËÞ×ÅÉ
ÎÒÍÎÑÈÒÅËÜÍÎ ÎÏÅÐÀÖÈÉ
ÒÀÁËÈ×ÍÛÕ ÀËÃÅÁÐ
Àííîòàöèÿ. Èññëåäîâàíà çàäà÷à èíâàðèàíòíîñòè êëþ÷åé, â òîì ÷èñëå è ïðîñòûõ, îòíîñè-
òåëüíî îïåðàöèé òàáëè÷íûõ àëãåáð — ñîâðåìåííîãî àíàëîãà êëàññè÷åñêèõ ðåëÿöèîííûõ
àëãåáð Êîääà. Ïîêàçàíî, ÷òî êëþ÷è èíâàðèàíòíû îòíîñèòåëüíî îïåðàöèé ïåðåñå÷åíèÿ, ðàç-
íîñòè, ñåëåêöèè, ñîåäèíåíèÿ è äåëåíèÿ, ïðè ýòîì äëÿ ïðîñòûõ êëþ÷åé èíâàðèàíòíîñòü íå
âûïîëíÿåòñÿ, à òàêæå ÷òî îòíîñèòåëüíî ïåðåèìåíîâàíèÿ èíâàðèàíòíû êàê êëþ÷è, òàê è
ïðîñòûå êëþ÷è. Íàéäåíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ, ïðè êîòîðûõ êëþ÷è, â òîì
÷èñëå è ïðîñòûå, èíâàðèàíòíû îòíîñèòåëüíî îïåðàöèé àêòèâíîãî äîïîëíåíèÿ è ïðîåêöèè.
Ðåçóëüòàòû ðàáîòû ïðåäñòàâëÿþò òåîðåòè÷åñêèé è ïðàêòè÷åñêèé èíòåðåñ è ìîãóò èñïîëüçî-
âàòüñÿ äëÿ âûáîðà îïòèìàëüíûõ êëþ÷åé ïðè ïðîåêòèðîâàíèè ðåëÿöèîííûõ áàç äàííûõ.
Êëþ÷åâûå ñëîâà: áàçà äàííûõ, òàáëè÷íàÿ àëãåáðà, êëþ÷.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ èíôîðìàöèîííûå ñèñòåìû øèðîêî èñïîëüçóþòñÿ ïðàêòè÷åñêè
âî âñåõ îáëàñòÿõ äåÿòåëüíîñòè ÷åëîâåêà. Áàçû äàííûõ ÿâëÿþòñÿ ÿäðîì äëÿ áîëü-
øèíñòâà èíôîðìàöèîííûõ ñèñòåì. Ïðè âñåì ðàçíîîáðàçèè òèïîâ áàç äàííûõ íàè-
áîëåå ðàñïðîñòðàíåíû ðåëÿöèîííûå (òàáëè÷íûå), ìàòåìàòè÷åñêóþ ìîäåëü êîòî-
ðûõ âïåðâûå ïðåäëîæèë Ý. Êîää [1, 2]. Ñ ìàòåìàòè÷åñêîé òî÷êè çðåíèÿ ðåëÿöè-
îííàÿ áàçà äàííûõ ÿâëÿåòñÿ êîíå÷íûì ìíîæåñòâîì êîíå÷íûõ îòíîøåíèé
ðàçëè÷íîé àðíîñòè ìåæäó çàðàíåå îïðåäåëåííûìè ìíîæåñòâàìè ýëåìåíòàðíûõ
äàííûõ, ò.å. ðåëÿöèîííàÿ áàçà äàííûõ — êîíå÷íàÿ ìîäåëü.
Òàáëè÷íûå àëãåáðû [3] ïîñòðîåíû íà îñíîâå ðåëÿöèîííûõ àëãåáð Êîääà è ñó-
ùåñòâåííî èõ ðàçâèâàþò. Îíè ñîñòàâëÿþò òåîðåòè÷åñêèé ôóíäàìåíò ÿçûêîâ çàïðîñîâ
ñîâðåìåííûõ òàáëè÷íûõ áàç äàííûõ. Ýëåìåíòû íîñèòåëÿ òàáëè÷íîé àëãåáðû óòî÷íÿ-
þò ðåëÿöèîííûå ñòðóêòóðû äàííûõ, à ñèãíàòóðíûå îïåðàöèè ïîñòðîåíû íà áàçå
îñíîâíûõ òàáëè÷íûõ ìàíèïóëÿöèé â ðåëÿöèîííûõ àëãåáðàõ è SQL-ïîäîáíûõ ÿçûêàõ.
 ðåëÿöèîííûõ áàçàõ äàííûõ âàæíóþ ðîëü èãðàþò êëþ÷è òàáëèöû — îäèí
èëè íåñêîëüêî åå àòðèáóòîâ, íà çíà÷åíèÿõ êîòîðûõ çàïèñè òàáëèöû îäíîçíà÷íî
èäåíòèôèöèðóþòñÿ. Ñ ïîìîùüþ êëþ÷åé (ïåðâè÷íûõ è âíåøíèõ) óñòàíàâëèâàþò-
ñÿ áèíàðíûå ñâÿçè òèïà «îäèí-êî-ìíîãèì», ïðåäíàçíà÷åííûå äëÿ ïîääåðæàíèÿ
öåëîñòíîñòè áàç äàííûõ. Êàê ïðàâèëî, êëþ÷è îïðåäåëÿþòñÿ òàêèì îáðàçîì, ÷òî-
áû îíè áûëè èíâàðèàíòíû ê ëþáûì èçìåíåíèÿì çàïèñåé â áàçå äàííûõ. Â íàñòî-
ÿùåé ðàáîòå ðàññìîòðåí âîïðîñ èíâàðèàíòíîñòè êëþ÷åé îòíîñèòåëüíî ñèãíàòóð-
íûõ îïåðàöèé òàáëè÷íûõ àëãåáð. Ïîëó÷åííûå ðåçóëüòàòû âàæíû äëÿ âûáîðà
îïòèìàëüíûõ êëþ÷åé ïðè ïðîåêòèðîâàíèè áàç äàííûõ [4, 5].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 3
© Â.Í. Ðåäüêî, Ä.Á. Áóé, À.Ñ. Ñåí÷åíêî, 2015
ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß
Çàôèêñèðóåì íåêîòîðîå íåïóñòîå ìíîæåñòâî àòðèáóòîâ A � { , ..., }A An1 . Ïðîèç-
âîëüíîå êîíå÷íîå ïîäìíîæåñòâî ìíîæåñòâà A íàçîâåì ñõåìîé, ïðè÷åì îíà ìî-
æåò áûòü ïóñòûì ìíîæåñòâîì. Ñòðîêîé s ñõåìû R íàçûâàåòñÿ ìíîæåñòâî ïàð
s A d A dk k� � �{( , ), ..., ( , )}1 1 , ïðîåêöèÿ êîòîðîãî ïî ïåðâîé êîìïîíåíòå ðàâíà R,
ïðè÷åì àòðèáóòû � �A Ak1, ..., ïîïàðíî ðàçëè÷íû, ò.å. ñòðîêà ÿâëÿåòñÿ ôóíêöèî-
íàëüíûì áèíàðíûì îòíîøåíèåì. Òàáëèöà T ñõåìû R ( ( ))T R — êîíå÷íîå ìíî-
æåñòâî ñòðîê ñõåìû R, êîëè÷åñòâî ñòðîê â òàáëèöå T îáîçíà÷èì T . Òàáëèöó
�T íàçîâåì ïîäòàáëèöåé òàáëèöû T , åñëè � �T T . Äàëåå ðàññìîòðèì òàáëèöû
ñõåìû R ñ êîëè÷åñòâîì àòðèáóòîâ k. Íà ìíîæåñòâå âñåõ òàêèõ òàáëèö ââåäå-
íû îïåðàöèè îáúåäèíåíèÿ ( )�
R
, ïåðåñå÷åíèÿ ( )�
R
è ðàçíîñòè ( )�
R
òàáëèö êàê
îãðàíè÷åíèÿ îäíîèìåííûõ òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé.
Äëÿ ââåäåíèÿ îïåðàöèè íàñûùåíèÿ îïðåäåëèì âñïîìîãàòåëüíîå ïîíÿòèå.
Àêòèâíûì äîìåíîì àòðèáóòà A îòíîñèòåëüíî òàáëèöû T íàçûâàåòñÿ ìíîæåñòâî
D d s T A d sA T, { | ( , ) }� � � � � [6], ñîñòîÿùåå èç âñåâîçìîæíûõ çíà÷åíèé àòðèáóòà
A â òàáëèöå T (åñëè àòðèáóò íå âõîäèò â ñõåìó òàáëèöû, òî åãî àêòèâíûé äîìåí
ïóñò). Àòðèáóòû òàáëèöû, ìîùíîñòü àêòèâíûõ äîìåíîâ êîòîðûõ áîëüøå åäèíè-
öû, íàçîâåì ìíîãîçíà÷íûìè, â ïðîòèâíîì ñëó÷àå — îäíîçíà÷íûìè.
Íàñûùåíèåì C T( ) íàçûâàåòñÿ òàáëèöà DA T
A R
,
�
, ãäå R — ñõåìà òàáëèöû,
à — îïåðàòîð îáîáùåííîãî ïðÿìîãî (äåêàðòîâîãî) ïðîèçâåäåíèÿ, ñîîòâåò-
ñòâóþùèé èíäåêñèðîâàíèþ A DA T� , , A R� [7]. Îòìåòèì, ÷òî â îáîçíà÷åíèÿõ
[3, 8] âûïîëíÿåòñÿ ðàâåíñòâî C T T
A R
A( ) ( ){ }�
�
� ; êðîìå òîãî, íàñûùåíèå ÿâëÿåò-
ñÿ àíàëîãîì ïðÿìîóãîëüíîãî çàìûêàíèÿ êîíå÷íîìåñòíîãî îòíîøåíèÿ [9].
Àêòèâíûì äîïîëíåíèåì òàáëèöû T íàçûâàåòñÿ òàáëèöà
~
( )T C T T
R
� � (îòìåòèì,
÷òî T C T� ( )).
Ïðîåêöèåé ïî ìíîæåñòâó àòðèáóòîâ X R� íàçûâàåòñÿ óíàðíàÿ ïàðàìåòðè÷åñêàÿ
îïåðàöèÿ � X , çíà÷åíèåì êîòîðîé ÿâëÿåòñÿ òàáëèöà, ñîñòîÿùàÿ èç îãðàíè÷åíèé ïî X
âñåõ ñòðîê èñõîäíîé òàáëèöû � X T s X s T( ) { | | }� � . Çäåñü îãðàíè÷åíèå ïîíèìàåòñÿ
ñòàíäàðòíî s X s X s| ( )� �� pr2 , ãäå pr2s — ïðîåêöèÿ ñòðîêè s ïî âòîðîé êîìïîíåíòå.
Ëþáîå îãðàíè÷åíèå �s ñòðîêè s áóäåì íàçûâàòü åå ïîäñòðîêîé, è î÷åâèäíî, ÷òî � �s s.
Ñåëåêöèåé ïî ïðåäèêàòó P S: { }� true, false , ãäå S — ìíîæåñòâî âñåõ ñòðîê,
íàçûâàåòñÿ óíàðíàÿ ïàðàìåòðè÷åñêàÿ îïåðàöèÿ � P , êîòîðàÿ òàáëèöå ñîïîñòàâëÿ-
åò åå ïîäòàáëèöó, ñîäåðæàùóþ ñòðîêè, íà êîòîðûõ ïðåäèêàò P ïðèíèìàåò èñòèí-
íûå çíà÷åíèÿ: � P T s s T P s( ) { | ( ) }� � � � true .
Äëÿ ââåäåíèÿ îïåðàöèè ñîåäèíåíèÿ îïðåäåëèì âñïîìîãàòåëüíîå ïîíÿòèå.
Áèíàðíûå îòíîøåíèÿ � è � íàçûâàþòñÿ ñîâìåñòíûìè � �
, åñëè � �| |X X� , ãäå
X � pr pr1 1� �� [8]. Ñîåäèíåíèåì íàçûâàåòñÿ áèíàðíàÿ îïåðàöèÿ
, çíà÷åíèåì
êîòîðîé ÿâëÿåòñÿ òàáëèöà, ñîñòîÿùàÿ èç âñåâîçìîæíûõ îáúåäèíåíèé ñîâìåñòíûõ
ñòðîê èñõîäíûõ òàáëèö, ò.å. T T s s s T s T s s1 2 1 2 1 1 2 2 1 2
� � � � �
{ | }� .
Äëÿ òàáëèöû T , âñå îäíîçíà÷íûå àòðèáóòû êîòîðîé îáðàçóþò ìíîæåñòâî
O O O z� { , ..., }1 , ïðè÷åì D o D oO T O T zz1 1, ,{ }, ..., { }� � , âûïîëíÿåòñÿ íåïîñðåä-
ñòâåííî ïðîâåðÿåìîå ðàâåíñòâî T T TY�
�� ( ) , ãäå Y R O� � è � �T
O O
o o
z
z
1
1
...
...
,
ò.å. � � �T O o i zi i{{( , )| , }}1 — ñîîòâåòñòâóþùàÿ îäíîñòðî÷íàÿ òàáëèöà.
Ïóñòü R1 — ñõåìà òàáëèöû T1, R2 — ñõåìà òàáëèöû T2 è R R2 1� . Äåëåíèå T1 íà
T2 — òàáëèöà ñõåìû R R1 2� òàêàÿ, ÷òî T
R
R
T s T s T TR R1
1
2
2 1 2 11 2
� � �
��{ ( )| { } }� .
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
Ïåðåèìåíîâàíèå — óíàðíàÿ ïàðàìåòðè÷åñêàÿ îïåðàöèÿ RT� , ãäå � — èíúåê-
òèâíîå îòîáðàæåíèå íà R, îñóùåñòâëÿþùàÿ ïåðåèìåíîâàíèå àòðèáóòîâ òàáëèöû
â ñîîòâåòñòâèè ñ �. Ïðèìåíåíèå ýòîé îïåðàöèè ñâîäèòñÿ ê ïåðåèìåíîâàíèþ ïåð-
âûõ êîìïîíåíò ïàð — ýëåìåíòîâ ñòðîê.
Òàáëè÷íîé àëãåáðîé íàçûâàåòñÿ ÷àñòè÷íàÿ àëãåáðà ñ íîñèòåëåì — ìíîæåñ-
òâîì âñåõ òàáëèö ïðîèçâîëüíîé ñõåìû, è ïðèâåäåííûìè ðàíåå îïåðàöèÿìè (íà-
ñûùåíèå ðàññìàòðèâàåòñÿ êàê âñïîìîãàòåëüíàÿ îïåðàöèÿ).
 êà÷åñòâå ñèãíàòóðíûõ â òàáëè÷íîé àëãåáðå âûäåëÿþò äâå îñîáûå òàáëèöû:
T� �� { }, ãäå � — ïóñòàÿ ñòðîêà (ïóñòîå ìíîæåñòâî, èíòåðïðåòèðóåìîå êàê âñþäó
íåîïðåäåëåííàÿ ôóíêöèÿ), à ñõåìà òàáëèöû T� — ïóñòîå ìíîæåñòâî; T� �� —
ïóñòîå ìíîæåñòâî ñòðîê ïðîèçâîëüíîé ñõåìû. Òàáëèöà T íå ÿâëÿåòñÿ îñîáîé è
íàçûâàåòñÿ íåíàñûùåííîé, åñëè âûïîëíÿåòñÿ íåðàâåíñòâî
~
T T� � (î÷åâèäíî, ýòî
ýêâèâàëåíòíî ñòðîãîìó âêëþ÷åíèþ T C T� ( )).
Ìíîæåñòâî àòðèáóòîâ K R� íàçûâàåòñÿ êëþ÷îì (òî÷íåå, ïåðâè÷íûì êëþ-
÷îì (primary key)) òàáëèöû T , åñëè äëÿ ëþáûõ ñòðîê s s T1 2, � âûïîëíÿåòñÿ èì-
ïëèêàöèÿ s K s K s s1 2 1 2| |� � � ; äðóãèìè ñëîâàìè, îãðàíè÷åíèÿ ïî àòðèáóòàì
êëþ÷à âñåõ ñòðîê òàáëèöû T ïîïàðíî ðàçëè÷íû.
Êëþ÷ K íàçûâàåòñÿ ïðîñòûì êëþ÷îì òàáëèöû T , åñëè íèêàêîå åãî ñîáñòâåí-
íîå ïîäìíîæåñòâî íå ÿâëÿåòñÿ êëþ÷îì T . Ïîñêîëüêó ñõåìà òàáëèöû òîæå ÿâëÿåòñÿ
åå êëþ÷îì, òî íàèáîëüøèé èíòåðåñ ïðåäñòàâëÿþò òàê íàçûâàåìûå íåòðèâèàëüíûå
êëþ÷è — ñîáñòâåííûå ïîäìíîæåñòâà ñõåìû òàáëèöû.
Êëþ÷îì òàáëèöû T� áóäåò ëþáîå ïîäìíîæåñòâî àòðèáóòîâ, à ïðîñòûì êëþ-
÷îì — ïóñòîå ìíîæåñòâî. Äëÿ òàáëèöû T� êëþ÷îì (â òîì ÷èñëå è ïðîñòûì) áóäåò
ïóñòîå ìíîæåñòâî (T� èìååò åäèíñòâåííûé êëþ÷�). Íà ïðàêòèêå â ðåàëüíûõ áàçàõ
äàííûõ îñîáàÿ òàáëèöà T� íå èñïîëüçóåòñÿ, ïîýòîìó äëÿ óäîáñòâà èçëîæåíèÿ è äî-
êàçàòåëüñòâà ðåçóëüòàòîâ ðàññìîòðèì òàáëèöû, êîòîðûå íå ÿâëÿþòñÿ îñîáûìè, ïðè
ýòîì áîëüøèíñòâî ðåçóëüòàòîâ ñïðàâåäëèâî è äëÿ òàáëèöû T� .
ÎÑÍÎÂÍÛÅ ÐÅÇÓËÜÒÀÒÛ
Ïîñêîëüêó êëþ÷è èãðàþò âàæíóþ ðîëü â ðåëÿöèîííûõ áàçàõ äàííûõ, åñòåñòâåíåí
âîïðîñ îá èíâàðèàíòíîñòè íåòðèâèàëüíûõ êëþ÷åé (â òîì ÷èñëå è ïðîñòûõ) îòíîñè-
òåëüíî îïåðàöèé òàáëè÷íûõ àëãåáð. Ñïðàâåäëèâî î÷åâèäíîå ïîëåçíîå óòâåðæäåíèå.
Ëåììà 1. Ïóñòü K — êëþ÷ òàáëèöû T . Òîãäà K — êëþ÷ ëþáîé òàáëèöû � �T T . �
Äàëåå ïåðåéäåì ê ðàññìîòðåíèþ èíâàðèàíòíîñòè êëþ÷åé îòíîñèòåëüíî êàæ-
äîé îïåðàöèè òàáëè÷íûõ àëãåáð.
Îïåðàöèè ïåðåñå÷åíèÿ, îáúåäèíåíèÿ, ðàçíîñòè, ñåëåêöèè è ïåðåèìåíîâàíèÿ.
Îïåðàöèÿ ïåðåñå÷åíèÿ ñîõðàíÿåò êëþ÷è, íî íå ñîõðàíÿåò ïðîñòûõ êëþ÷åé.
Ïðåäëîæåíèå 1 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî ïåðåñå÷åíèÿ). Ïóñòü
K — êëþ÷ òàáëèö T R1 ( ) è (èëè) T R2 ( ). Òîãäà K — êëþ÷ òàáëèöû T T
R
1 2� . Åñëè
K — ïðîñòîé êëþ÷ äëÿ T1 è T2 , òî K, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ ïðîñòûì êëþ-
÷îì òàáëèöû T T
R
1 2� . �
Îïåðàöèÿ îáúåäèíåíèÿ íå ñîõðàíÿåò êëþ÷åé, ò.å. â ñëó÷àå, êîãäà K — êëþ÷
òàáëèö T R1 ( ) è T R2 ( ), òî K ìîæåò íå ÿâëÿòüñÿ êëþ÷îì òàáëèöû T T
R
1 2� .
Îïåðàöèÿ ðàçíîñòè ñîõðàíÿåò êëþ÷è, íî íå ñîõðàíÿåò ïðîñòûõ êëþ÷åé.
Ïðåäëîæåíèå 2 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî ðàçíîñòè). Ïóñòü T1, T2 —
òàáëèöû ñõåìû R è K — êëþ÷ äëÿ T1. Òîãäà K — êëþ÷ òàáëèöû T T
R
1 2� . Åñëè K —
ïðîñòîé êëþ÷ äëÿ T1, òî K, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ ïðîñòûì êëþ÷îì äëÿ T T
R
1 2� . �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 5
Îïåðàöèÿ ñåëåêöèè ñîõðàíÿåò êëþ÷è, íî íå ñîõðàíÿåò ïðîñòûõ êëþ÷åé.
Ïðåäëîæåíèå 3 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî ñåëåêöèè). Ïóñòü K —
êëþ÷ òàáëèöû T . Òîãäà K — êëþ÷ òàáëèöû � P T( ). Åñëè K ÿâëÿåòñÿ ïðîñòûì êëþ-
÷îì òàáëèöû T , òî K, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ ïðîñòûì êëþ÷îì äëÿ � P T( ). �
 ïðåäëîæåíèÿõ 1 – 3 èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî îïåðàöèé ñëåäó-
åò èç ëåììû 1, à íåñîõðàíåíèå ïðîñòûõ êëþ÷åé íåñëîæíî ïîêàçàòü íà ïðèìåðàõ.
Ïîñêîëüêó îïåðàöèÿ ïåðåèìåíîâàíèÿ íå èçìåíÿåò çíà÷åíèÿ àòðèáóòîâ, îíà
ñîõðàíÿåò êëþ÷è è ïðîñòûå êëþ÷è.
Ïðåäëîæåíèå 4 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî ïåðåèìåíîâàíèÿ).
Ïóñòü K — êëþ÷ (ïðîñòîé êëþ÷) òàáëèöû T è ïóñòü � �� �[ ] ( )|K A A K� � . Òîãäà
�[ ]K ÿâëÿåòñÿ êëþ÷îì (ïðîñòûì êëþ÷îì) òàáëèöû RT� . �
Òàêèì îáðàçîì, ïîëíûé îáðàç êëþ÷à (ïðîñòîãî êëþ÷à) èñõîäíîé òàáëèöû
ÿâëÿåòñÿ êëþ÷îì (ïðîñòûì êëþ÷îì) ïåðåèìåíîâàííîé òàáëèöû.
Îïåðàöèÿ àêòèâíîãî äîïîëíåíèÿ. Íàéäåì (â òåðìèíàõ àêòèâíûõ äîìåíîâ
àòðèáóòîâ òàáëèö) íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ, ïðè êîòîðûõ íåòðèâè-
àëüíûå êëþ÷è äëÿ íåíàñûùåííûõ òàáëèö T è
~
T ñîâïàäàþò. Òðåáîâàíèå íåíàñû-
ùåííîñòè íåîáõîäèìî âî èçáåæàíèå ñëó÷àÿ
~
T T� � , ïðè êîòîðîì êëþ÷îì òàáëè-
öû T� ÿâëÿåòñÿ ëþáîå ìíîæåñòâî àòðèáóòîâ. Âíà÷àëå ñôîðìóëèðóåì ýòîò êðèòå-
ðèé äëÿ òàáëèö, ó êîòîðûõ âñå àòðèáóòû ìíîãîçíà÷íûå.
Òåîðåìà 1 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî àêòèâíîãî äîïîëíåíèÿ
äëÿ òàáëèö áåç îäíîçíà÷íûõ àòðèáóòîâ). Ïóñòü K K Kq� { , ..., }1 — íåòðèâèàëü-
íûé êëþ÷ äëÿ íåíàñûùåííîé òàáëèöû T R( ) ñ ìíîãîçíà÷íûìè àòðèáóòàìè. Ïðè
ýòîì K ÿâëÿåòñÿ êëþ÷îì òàáëèöû
~
T òîãäà è òîëüêî òîãäà, êîãäà îäíîâðåìåííî
âûïîëíÿþòñÿ òðè óñëîâèÿ:
à) âûïîëíÿåòñÿ ðàâåíñòâî | |R K� �1;
á) äëÿ åäèíñòâåííîãî àòðèáóòà B, ïðèíàäëåæàùåãî ìíîæåñòâó R K� , âûïîë-
íÿåòñÿ ðàâåíñòâî | |,DB T � 2 ;
â) äëÿ âñåõ d D d DK T q K Tq1 1
� �, ,,... , ñòðîêà � � �s K d K d Tq q K{( , ),... , ( , )} ( )1 1 � ,
ïðè÷åì ñóùåñòâóåò òîëüêî îäíà òàêàÿ ñòðîêà s T� , ÷òî � �s s K Kq|{ , ..., }1 .
Äîêàçàòåëüñòâî. Äîñòàòî÷íîñòü. Ïóñòü äëÿ òàáëèöû T îäíîâðåìåííî âûïîë-
íÿþòñÿ óñëîâèÿ à) – â). Îáîçíà÷èì R K B� � { }; D b bB T, { , }� 1 2 . Çàìåòèì òàêæå, ÷òî
ââèäó âûïîëíåíèÿ óñëîâèÿ à), âûïîëíÿåòñÿ ðàâåíñòâî q n� �1, ãäå n R� | | . Ïîñêîëü-
êó K — êëþ÷ òàáëèöû T , èç âûïîëíåíèÿ óñëîâèÿ â) ñëåäóåò, ÷òî òàáëèöà T ñîñòî-
èò èç ñòðîê âèäà {( , ), ..., ( , ), ( , )}K d K d B bn n1 1 1 1� � , ãäå d dn1 1, ..., � — âñåâîçìîæ-
íûå çíà÷åíèÿ àêòèâíûõ äîìåíîâ D DK T K Tn1 1, ,, ...,
�
, è äëÿ êàæäîãî òàêîãî íàáîðà
çíà÷åíèé d dn1 1, ..., � ýëåìåíò b ìîæåò ïðèíèìàòü òîëüêî îäíî çíà÷åíèå: b1 èëè
b2 . Ïðè ýòîì îòìåòèì, ÷òî ââèäó âûïîëíåíèÿ óñëîâèÿ á), ñóùåñòâóþò òàêèå
� �� � � �� �� � �
d d D d d DK T n n K Tn
, , ..., ,, ,1 11 1 , ÷òî {( , ), ..., ( , ), ( , )}K d K d B b Tn n1 1 1 1 1� � �� � è
{( ), ..., ( , ), ( , )}K d K d B b Tn n1 1 1 1 2�� �� �� � .  ýòîì ñëó÷àå ïî îïðåäåëåíèþ íàñûùå-
íèÿ C T( ) ñîñòîèò èç ñòðîê âèäà {( , ),... , ( , ), ( , )}K d K d B bn n1 1 1 1 1� � , {( , ), ...K d1 1
..., ( , ), ( , )}K d B bn n� �1 1 2 . Òîãäà
~
( )T C T T
R
� � ñîñòîèò èç âñåõ ñòðîê âèäà {( , ), ...K d1 1
..., ( , ), ( , )}K d B bn n� � �1 1 , ïðè÷åì åñëè â òàáëèöå T â ñòðîêå {( , ), ..., ( , ),K d K dn n1 1 1 1� �
( , )}B b çíà÷åíèå ýëåìåíòà b b� 1, òî � �b b2 , è íàîáîðîò, åñëè b b� 2 , òî � �b b1.
Ïðè ýòîì äëÿ êàæäîãî òàêîãî íàáîðà çíà÷åíèé d dn1 1, ..., � â òàáëèöå
~
T ýëåìåíò �b
ìîæåò ïðèíèìàòü òîëüêî îäíî çíà÷åíèå: b1 èëè b2 . Òàêèì îáðàçîì, îãðàíè÷åíèÿ
ïî K äëÿ âñåõ ñòðîê òàáëèöû
~
T ïîïàðíî ðàçëè÷íû, ñëåäîâàòåëüíî K ÿâëÿåòñÿ
êëþ÷îì òàáëèöû
~
T , ÷òî äîêàçûâàåò äîñòàòî÷íîñòü.
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
Äîêàæåì òåïåðü íåîáõîäèìîñòü óñëîâèé òåîðåìû. Ïóñòü K — íåòðèâèàëü-
íûé êëþ÷ òàáëèö T è
~
T . Ïîêàæåì, ÷òî â ýòîì ñëó÷àå äîëæíû îäíîâðåìåííî âû-
ïîëíÿòüñÿ óñëîâèÿ à) – â). Îò ïðîòèâíîãî, äîïóñòèì, ÷òî óñëîâèå à) íå âûïîëíÿ-
åòñÿ, ò.å. ìíîæåñòâî R K� ñîäåðæèò õîòÿ áû äâà ýëåìåíòà. Ïóñòü
R K B Bn q� � �{ , ..., }1 . Ïîñêîëüêó âñå àòðèáóòû òàáëèöû T ìíîãîçíà÷íû, êàæäûé
àêòèâíûé äîìåí êàæäîãî àòðèáóòà èç ìíîæåñòâà R K� ñîäåðæèò êàê ìèíèìóì
äâà ýëåìåíòà. Ïîëîæèì D b b b DB T p B Tn q1 11
1
2
1 1
, ,{ , ,... , },... ,� �
�
{ , , ..., }b b bn q n q
p
n q
n q1 2
� � �
�
.
Ïóñòü s K d K d B b B bq q x n q x
n
n q
� �
�
�
{( , ),...,( , ),( , ) ,..., ( ,1 1 1
1
1
q )}— ïðîèçâîëüíàÿ ñòðîêà òàáëè-
öû T . Ïîñêîëüêó êàæäîå ìíîæåñòâî D DB T B Tn q1, ,,...,
�
ñîäåðæèò áîëåå îäíîãî ýëå-
ìåíòà, ñóùåñòâóþò òàêèå b D b D
y B T y
n q
B T
n q n q1 1
1 � �
� �
�
, ,,..., , ÷òî b b b b
x y x
n q
y
n q
n q n q1 1
1 1� �
� �
� �,..., .
Ïðè ýòîì ñòðîêè � � �
�
�
�
�
� �
�
s K d K d B b B bq q y n q yn
( , ), ..., ( , ), , , ..., ,1 1 1
1
1 q
n q��
�
�
�
�
�
�
�
�
�
�
�
è
�� � �
�
�
�
�
�
�
�
�
�
�
s K d K d B b B bq q x y
( , ), ..., ( , ), , , ,1 1 1
1
1
2
1 2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
, ..., ,B bn q y
n q
n q
ïðèíàäëåæàò
íàñûùåíèþ C T( ). Îäíàêî ââèäó òîãî, ÷òî K — êëþ÷ òàáëèöû T ,
s K s K s K| | |� � � �� , � �s s è �� �s s, ñòðîêè �s è ��s íå ìîãóò ïðèíàäëåæàòü T . Òîãäà ïî
îïðåäåëåíèþ àêòèâíîãî äîïîëíåíèÿ � �� �s s T,
~
, ñëåäîâàòåëüíî, â ýòîì ñëó÷àå K íå
ÿâëÿåòñÿ êëþ÷îì òàáëèöû
~
T . Ïðîòèâîðå÷èå äîêàçûâàåò íåîáõîäèìîñòü óñëîâèÿ à).
Îò ïðîòèâíîãî, äîïóñòèì, ÷òî óñëîâèå á) íå âûïîëíÿåòñÿ, ò.å. àêòèâíûé äîìåí
õîòÿ áû îäíîãî àòðèáóòà ìíîæåñòâà R K� ñîäåðæèò áîëåå äâóõ ýëåìåíòîâ. Äëÿ óäîá-
ñòâà îáîçíà÷åíèé ââèäó äîêàçàííîé ðàíåå íåîáõîäèìîñòè óñëîâèÿ à) ïîëîæèì
R K B� � { } è D b b b bB T z, { , , , ..., }� 1 2 3 . Ïóñòü s K d K d B bq q� {( , ), ..., ( , ), ( , )}1 1 —
ïðîèçâîëüíàÿ ñòðîêà òàáëèöû T . Òîãäà ñóùåñòâóþò òàêèå ðàçëè÷íûå çíà÷åíèÿ
� �� �b b DB T, , , ÷òî b b� � è b b� ��. Ïðè ýòîì ñòðîêè � � �s K d K d B bq q{( , ), ..., ( , ), ( , )}1 1
è �� � � � ��s A d A d B bq q{( , ), ..., ( , ), ( , )}1 1 ïðèíàäëåæàò C T( ). Îäíàêî ââèäó òîãî, ÷òî K —
êëþ÷ äëÿ T , s K s K s K| | |� � � �� , � �s s è �� �s s, ñòðîêè �s è ��s íå ìîãóò ïðèíàäëåæàòü T ,
çíà÷èò, îíè ïðèíàäëåæàò
~
T , â ýòîì ñëó÷àå K íå ÿâëÿåòñÿ êëþ÷îì òàáëèöû
~
T . Ïðîòè-
âîðå÷èå äîêàçûâàåò íåîáõîäèìîñòü óñëîâèÿ á).
Îò ïðîòèâíîãî, äîïóñòèì, ÷òî íå âûïîëíÿåòñÿ óñëîâèå â). Äëÿ óäîáñòâà îáîçíà-
÷åíèé ââèäó äîêàçàííîé ðàíåå íåîáõîäèìîñòè óñëîâèé à) è á) ïîëîæèì R K B� � { }
è D b bB T, { , }� 1 2 , ïðè ýòîì çíà÷åíèå èíäåêñà q n� �1. Åñëè ñóùåñòâóþò òàêèå çíà-
÷åíèÿ d D d D
K T q K Tq1
1
� �
, ,, ..., , ÷òî s K d K d Tq q K� {( , ), ..., ( , )} ( )1 1 � , òî èç
îïðåäåëåíèÿ ïðîåêöèè s T ñëåäóåò s K d K d B b Tn n1 1 1 1 1 1� � �{( , ), ..., ( , ), ( , )} è
s K d K d B b Tn n2 1 1 1 1 2� � �{( , ), ..., ( , ), ( , )} . Òîãäà ââèäó s s C T1 2, ( )� âûïîëíÿåòñÿ
s s T1 2,
~
� . Îäíàêî èç òîãî, ÷òî � � ��s K s K| | è s s1 2� ñëåäóåò, ÷òî K íå ÿâëÿåòñÿ
êëþ÷îì äëÿ
~
T . Åñëè ñóùåñòâóþò òàêèå ñòðîêè s s1 2� , ÷òî s K s K1 2| |� , òî K íå
ÿâëÿåòñÿ êëþ÷îì äëÿ T . Ïðîòèâîðå÷èå äîêàçûâàåò íåîáõîäèìîñòü óñëîâèÿ â). �
Ïðèìåíèì êðèòåðèé èíâàðèàíòíîñòè êëþ÷åé äëÿ òàáëèö ñ îäíîçíà÷íûìè àò-
ðèáóòàìè. Ïóñòü O O O z� { , ..., }1 — ìíîæåñòâî âñåõ îäíîçíà÷íûõ àòðèáóòîâ òàá-
ëèöû T è ïóñòü D o D oO T O T zz1 1, ,{ }, ..., { }� � . Îáîçíà÷èì Y R O� � è
� �T
O O
o o
z
z
1
1
...
...
. Òîãäà èç îïðåäåëåíèÿ ñîåäèíåíèÿ è àêòèâíîãî äîïîëíåíèÿ î÷å-
âèäíî ñëåäóåò ðàâåíñòâî
~
( )
~
T T T
Y
� �
�
�
�
�
�
�� , ïîýòîìó îäíîçíà÷íûå àòðèáóòû íå
âëèÿþò íà óñëîâèå à) òåîðåìû 1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 7
Ñëåäñòâèå 1 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî àêòèâíîãî äîïîëíåíèÿ
äëÿ òàáëèö ñ îäíîçíà÷íûìè àòðèáóòàìè). Ïóñòü K K Kq� { , ..., }1 — íåòðèâèàëü-
íûé êëþ÷ äëÿ íåíàñûùåííîé òàáëèöû T R( ). Ïðè÷åì K ÿâëÿåòñÿ êëþ÷îì òàáëè-
öû
~
T òîãäà è òîëüêî òîãäà, êîãäà îäíîâðåìåííî âûïîëíÿþòñÿ òðè óñëîâèÿ:
— ìíîæåñòâî R K� ñîäåðæèò â òî÷íîñòè îäèí ìíîãîçíà÷íûé àòðèáóò;
— äëÿ åäèíñòâåííîãî ìíîãîçíà÷íîãî àòðèáóòà B R K� � âûïîëíÿåòñÿ ðàâåí-
ñòâî | |,DB T � 2 ;
— äëÿ âñåõ d D d DK T q K Tq1 1
� �, ,,... , ñòðîêà � � �s K d K d Tq q K{( , ),... , ( , )} ( )1 1 � ,
ïðè÷åì ñóùåñòâóåò òîëüêî îäíà òàêàÿ ñòðîêà s T� , ÷òî � �s s K Kq|{ , ..., }1 . �
Ñëåäñòâèå 2 (èíâàðèàíòíîñòü ïðîñòûõ êëþ÷åé îòíîñèòåëüíî àêòèâíîãî äî-
ïîëíåíèÿ). Ïðè âûïîëíåíèè óñëîâèÿ â) èç òåîðåìû 1 (ëèáî ïîñëåäíåãî óñëîâèÿ
èç ñëåäñòâèÿ 1) K ÿâëÿåòñÿ ïðîñòûì êëþ÷îì òàáëèö T è
~
T . �
Îïåðàöèÿ ïðîåêöèè. Ïóñòü K — êëþ÷ òàáëèöû T è X R� (îòìåòèì, ÷òî ñëó÷àé
X R� òðèâèàëüíûé, ïîñêîëüêó � R T T( ) � ) . Îïðåäåëèì, ÿâëÿåòñÿ ëè K êëþ÷îì òàáëè-
öû � X T( ). Ðàññìîòðèì âñå âîçìîæíûå ñëó÷àè îòíîñèòåëüíî âêëþ÷åíèÿ ìíîæåñòâ X è K
ñ òî÷êè çðåíèÿ ñîõðàíåíèÿ èíâàðèàíòíîñòè êëþ÷à îòíîñèòåëüíî ïðîåêöèè: 1) K X� ;
2) X K� ; 3) K X� ��; 4) íå âûïîëíÿåòñÿ íè îäèí èç ñëó÷àåâ 1–3.
 ñëó÷àå 1 ïîêàæåì, ÷òî K — êëþ÷ òàáëèöû � X T( ); â ñëó÷àå 2 î÷åâèäíî,
÷òî ìíîæåñòâî X — òðèâèàëüíûé êëþ÷ òàáëèöû � X T( ); â ñëó÷àå 3 íå ñóùåñòâó-
åò ëîãè÷åñêîé ñâÿçè ìåæäó êëþ÷àìè òàáëèö T è � X T( ); â ñëó÷àå 4 ìíîæåñòâî
K X� íå ÿâëÿåòñÿ êëþ÷îì òàáëèöû � X T( ), ÷òî ìîæíî ïîêàçàòü íà ïðèìåðå.
Ðàññìîòðèì ñëó÷àé 1, ïðè êîòîðîì âûïîëíÿåòñÿ âêëþ÷åíèå K X� , òîãäà ñî-
õðàíÿþòñÿ è êëþ÷è, è ïðîñòûå êëþ÷è. Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 2 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî ïðîåêöèè). Ïóñòü K —
êëþ÷ òàáëèöû T è K X� . Òîãäà K ÿâëÿåòñÿ êëþ÷îì òàáëèöû � X T( ).
Äîêàçàòåëüñòâî. Ïóñòü K X� . Òîãäà K ÿâëÿåòñÿ òðèâèàëüíûì êëþ÷îì òàá-
ëèöû � K T( ). Ïóñòü òåïåðü K X� , ò.å. K X� . Îò ïðîòèâíîãî, äîïóñòèì, ÷òî K
íå ÿâëÿåòñÿ êëþ÷îì äëÿ � X T( ), çíà÷èò, ñóùåñòâóþò òàêèå ñòðîêè
� �� �s s TX, ( )� , ÷òî � � ��s s è � � ��s K s K| | . Îáîçíà÷èì K K Kq� { , ..., }1 ,
X K X X p� � { , ..., }1 , R X B B z� � { , ..., }1 , ïðè ýòîì ìíîæåñòâà X K� è R X� íå-
ïóñòûå. Ïóñòü òàêæå � � � � � �s K k K k X x X xq q p p{( , ), ..., ( , ), ( , ), ..., ( , )}1 1 1 1 è
�� � �� �� �� ��s K k K k X x X xq q p{( , ), ..., ( , ), ( , ), ..., ( ,1 1 1 1 p )}. Òîãäà èç ðàâåíñòâà � � ��s K s K| |
ñëåäóåò âûïîëíåíèå ðàâåíñòâ � � �� � � ��k k k kq q1 1, ..., , à èç íåðàâåíñòâà � � ��s s — âû-
ïîëíåíèå õîòÿ áû îäíîãî èç íåðàâåíñòâ:
� � �� � � ��x x x xp p1 1, ..., . (1)
Ïî îïðåäåëåíèþ ïðîåêöèè ñóùåñòâóþò íåïóñòûå ìíîæåñòâà S s T s s1 1 1� � � �{ | }è
S s T s s2 2 2� � �� �{ | }. Ïóñòü s K k K k X x X x Bq q p p1 1 1 1 1� � � � �{( , ),... , ( , ), ( , ),... , ( , ), ( 1 1, ),...�b
...,( , )}B b Sz z� � 1 è s K k K k X x X xq q p p2 1 1 1 1� �� �� �� ��{( , ),...,( , ),( , ),...,( , ),( , ), ,( , )}B b B b Sz z1 1 2�� �� �� .
Èç ðàâåíñòâ � � �� � � ��k k k kq q1 1, ..., ñëåäóåò ðàâåíñòâî s K s K1 2| |� , à ïîñêîëüêó K —
êëþ÷ òàáëèöû T , èç s K s K1 2| |� ñëåäóåò s s1 2� , ïîýòîìó âûïîëíÿþòñÿ ðàâåíñòâà
� � �� � � ��x x x xp p1 1, ..., , ÷òî ïðîòèâîðå÷èò (1), ñëåäîâàòåëüíî, äîïóùåíèå íåâåðíî. �
Òåîðåìà 3 (èíâàðèàíòíîñòü ïðîñòûõ êëþ÷åé îòíîñèòåëüíî ïðîåêöèè). Ïóñòü K —
ïðîñòîé êëþ÷ òàáëèöû T è K X� . Òîãäà K ÿâëÿåòñÿ ïðîñòûì êëþ÷îì òàáëèöû � X T( ).
Äîêàçàòåëüñòâî. Òåîðåìà 2 ïîêàçûâàåò, ÷òî K — êëþ÷ òàáëèöû � X T( ).
Îò ïðîòèâíîãî, äîïóñòèì, ÷òî K íå ÿâëÿåòñÿ ïðîñòûì êëþ÷îì òàáëèöû � X T( ),
ò.å. ñóùåñòâóåò òàêîå � �K K , ÷òî �K — êëþ÷ òàáëèöû � X T( ). Îáîçíà÷èì
� �K M Mq{ ,... , }1 , K K K Kw� � � { ,... , }1 , X K X X p� � { ,... , }1 , R X B Bz� � { ,... , }1 , ïðè
ýòîì ìíîæåñòâà �K , K K� � è R X� íåïóñòûå. Ïîñêîëüêó K — ïðîñòîé êëþ÷ äëÿ T , òî
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
�K íå ÿâëÿåòñÿ êëþ÷îì äëÿ T , ñëåäîâàòåëüíî, ñóùåñòâóþò òàêèå ñòðîêè � �� �s s T, , ÷òî
� � � �� �s K s K| | è � � ��s s . Ïóñòü � � � � � �s M m M m K k K k Xq q w w{( , ),... , ( , ), ( , ),... , ( , ), (1 1 1 1 1 1, ),...�x
... , ( , ), ( , ),... , ( , )}X x B b B bp p z z� � �1 1 è �� � �� �� �� ��s M m M m K k K kq q w{( , ),... , ( , ), ( , ),... , ( ,1 1 1 1 w ),
( , ),... , ( , ), ( , ),... , ( , )}X x X x B b B bp p z z1 1 1 1�� �� �� �� . Òîãäà èç íåðàâåíñòâà � � ��s s ñëåäóåò âû-
ïîëíåíèå õîòÿ áû îäíîãî èç íåðàâåíñòâ:
� � �� � � �� � � �� � � �� � � ��m m m m k k k k xq q w w1 1 1 1 1,... , , ,... , , x x x b b b bp p z z1 1 1,... , , ,... ,� � �� � � �� � � ��. (2)
Èç ðàâåíñòâà � � � �� �s K s K| | ñëåäóåò âûïîëíåíèå âñåõ ðàâåíñòâ � � �� � � ��m m m mq q1 1, ..., .
Ïîñêîëüêó ïî ïðåäïîëîæåíèþ �K — ïðîñòîé êëþ÷ òàáëèöû � X T( ), à èç ðàâåíñòâ
� � �� � � ��m m m mq q1 1, ..., ñëåäóåò ( | )| ( | )|� � ��s X K s X K, äîëæíû âûïîëíÿòüñÿ ðàâåíñòâà
� � �� � � �� � � �� � � ��k k k k x x x xw w p p1 1 1 1, ..., , , ..., . Ïîñêîëüêó K — êëþ÷ äëÿ T , à èç âûïîëíåíèÿ
� � �� � � �� � � �� � � ��m m m m k k k kq q w w1 1 1 1, ..., , , ..., ñëåäóåò � � ��s K s K| | , äîëæíû âûïîëíÿòüñÿ
ðàâåíñòâà � � �� � � ��b b b bz z1 1, ..., , ÷òî ïðîòèâîðå÷èò (2), ïîýòîìó äîïóùåíèå íåâåðíî. �
Îïåðàöèÿ ñîåäèíåíèÿ. Ïîêàæåì, ÷òî îáúåäèíåíèå êëþ÷åé èñõîäíûõ òàá-
ëèö áóäåò êëþ÷îì èõ ñîåäèíåíèÿ.
Òåîðåìà 4 (èíâàðèàíòíîñòü îáúåäèíåíèÿ êëþ÷åé îòíîñèòåëüíî ñîåäèíåíèÿ).
Ïóñòü K1 — êëþ÷ òàáëèöû T1 è K2 — êëþ÷ òàáëèöû T2 . Òîãäà K K1 2� ÿâëÿåòñÿ
êëþ÷îì òàáëèöû T T1 2
. Åñëè K1 — ïðîñòîé êëþ÷ äëÿ T1 è K2 — ïðîñòîé êëþ÷
äëÿ T2 , òî K K1 2� , âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ ïðîñòûì êëþ÷îì äëÿ T T1 2
.
Äîêàçàòåëüñòâî. Ïóñòü R1 — ñõåìà òàáëèöû T1 è R2 — ñõåìà òàáëèöû T2 . Íà ðèñ. 1
ïîêàçàíû âñå âîçìîæíûå ñëó÷àè îòíîñèòåëüíî âêëþ÷åíèÿ ìíîæåñòâ R1, R2 , K1 è K2 .
Èç ðèñ. 1 ñëåäóåò, ÷òî K M M M1 1 3 5� � � , K M M M2 1 4 6� � � ,
R M M M M M1 1 2 3 5 7� � � � � , R M M M M M2 1 2 4 6 8� � � � � è K K M M1 2 1 3� � ��
� � �M M M4 5 6 , ïðè÷åì íåêîòîðûå èç ìíîæåñòâ M M1 8, ..., ìîãóò áûòü ïóñòû-
ìè (íåîáõîäèìî âûïîëíåíèå íåðàâåíñòâ K1 �� è K2 ��). Îò ïðîòèâíîãî, äîïóñ-
òèì, ÷òî K K1 2� íå ÿâëÿåòñÿ êëþ÷îì òàáëèöû T T1 2
, çíà÷èò, ñóùåñòâóþò òàêèå
ñòðîêè � �� �
s s T T, 1 2 , ÷òî � � ��s K K s K K| ( ) | ( )1 2 1 2� � è � � ��s s . Òîãäà èç � � ��s s
ñ ó÷åòîì ðàâåíñòâà � � ��s K K s K K| ( ) | ( )1 2 1 2� � ñëåäóåò èñòèííîñòü äèçúþíêöèè
� � �� ! � � �� ! � � ��s M s M s M s M s M s M| | | | | |2 2 7 7 8 8 . (3)
Ïîñêîëüêó � �� �
s s T T, 1 2 , ïî îïðåäåëåíèþ ñîåäèíåíèÿ ñóùåñòâóþò òàêèå ñòðîêè
� �s T1 1, �� �s T1 1 è � �s T2 2 , �� �s T2 2 , ÷òî �
�s s1 2 , ��
��s s1 2 , � � � �s s s1 2� è �� � �� ��s s s1 2� . Ïîñ-
êîëüêó K1 — êëþ÷ òàáëèöû T1, à èç ðàâåíñòâà � � ��s K K s K K| ( ) | ( )1 2 1 2� � ïðÿìî ñëå-
äóåò êîíúþíêöèÿ � � �� � � � �� � � � ��s M s M s M s M s M s M1 1 1 1 1 3 1 3 1 5 1 5| | | | | | , äîëæíû âûïîëíÿòüñÿ
ðàâåíñòâà � � ��s M s M1 2 1 2| | è � � ��s M s M1 7 1 7| | , ïîýòîìó � � �� � � � ��s M s M s M s M| | | |2 2 7 1 7.
Àíàëîãè÷íî, ïîñêîëüêó K2 — êëþ÷ äëÿ T2 , à èç � � ��s K K s K K| ( ) | ( )1 2 1 2� � ïðÿìî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 9
Ðèñ. 1. Âîçìîæíûå ñëó÷àè âçàèìíîãî âêëþ÷åíèÿ ìíîæåñòâ R1, R2, K1 è K2
M8
M2
K1
M3
R1
M5
M6
K2
M4
M1
M2
R2
M7
ñëåäóåò êîíúþíêöèÿ � � �� � � � �� � � � ��s M s M s M s M s M s M2 1 2 1 2 4 2 4 2 6 2 6| | | | | | , äîëæíî
òàêæå âûïîëíÿòüñÿ ðàâåíñòâî � � ��s M s M2 8 2 8| | , ïîýòîìó � � ��s M s M| |8 8 , ÷òî ïðîòèâî-
ðå÷èò (3), ïîýòîìó äîïóùåíèå íåâåðíî.
Âòîðàÿ ÷àñòü òåîðåìû äîêàçûâàåòñÿ ñ ïîìîùüþ êîíòðïðèìåðà. �
Èç òåîðåìû 4 ñëåäóåò, ÷òî â ñëó÷àå, êîãäà îáå èñõîäíûå òàáëèöû èìåþò îäè-
íàêîâûé êëþ÷, ïîñëåäíèé òàêæå ÿâëÿåòñÿ êëþ÷îì ñîåäèíåíèÿ èñõîäíûõ òàáëèö.
Ñëåäñòâèå 3 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî ñîåäèíåíèÿ). Ïóñòü K –
êëþ÷ òàáëèö T1 è T2 . Òîãäà K — êëþ÷ òàáëèöû T T1 2
. Åñëè K — ïðîñòîé êëþ÷
òàáëèö T1 è T2 , òî K, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ ïðîñòûì êëþ÷îì äëÿ T T1 2
. �
Îïåðàöèÿ äåëåíèÿ. Ðàññìîòðèì èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî äå-
ëåíèÿ òîëüêî â òîì ñëó÷àå, êîãäà çíà÷åíèå T
R
R
T1
1
2
2� íåïóñòîå (òàê êàê èíà÷å
èìååì òðèâèàëüíûé ñëó÷àé). Ïîñêîëüêó ñõåìà ðåçóëüòàòà åñòü ìíîæåñòâî
R R1 2� , ãäå R1 — ñõåìà òàáëèöû T1, R2 — ñõåìà òàáëèöû T2 , ðàññìîòðèì ñëåäó-
þùèå ñèòóàöèè âçàèìíîãî âêëþ÷åíèÿ êëþ÷à òàáëèöû T1 è ñõåìû R2 :
1) êëþ÷ òàáëèöû T1 íå ïåðåñåêàåòñÿ ñî ñõåìîé R2 ;
2) êëþ÷ òàáëèöû T1 ïåðåñåêàåòñÿ ñî ñõåìîé R2 , íî ïðè ýòîì îí ïîëíîñòüþ
íå âõîäèò â ñõåìó òàáëèöû T2 .
Âàðèàíò, ïðè êîòîðîì êëþ÷ òàáëèöû T1 ïîëíîñòüþ âõîäèò â ñõåìó R2 , ñ òî÷êè
çðåíèÿ ñîõðàíåíèÿ êëþ÷à îïåðàöèåé T
R
R
T1
1
2
2� ðàññìàòðèâàòü íåöåëåñîîáðàçíî, òàê
êàê íå ñóùåñòâóåò ëîãè÷åñêîé ñâÿçè ìåæäó êëþ÷àìè òàáëèö-àðãóìåíòîâ è ðåçóëüòàòà.
Ïîêàæåì, ÷òî â ïåðâîì ñëó÷àå îïåðàöèÿ äåëåíèÿ òàáëèö ñîõðàíÿåò êëþ÷,
íî íå ñîõðàíÿåò ïðîñòîãî êëþ÷à, à âî âòîðîì ñëó÷àå ÷àñòü êëþ÷à, íå âõîäÿùàÿ
â ñõåìó òàáëèöû T2 , áóäåò ÿâëÿòüñÿ êëþ÷îì òàáëèöû T
R
R
T1
1
2
2� .
Ðàññìîòðèì ïåðâûé ñëó÷àé è ïîêàæåì, ÷òî îïåðàöèÿ äåëåíèÿ òàáëèö ñîõðà-
íÿåò êëþ÷, íî íå ñîõðàíÿåò ïðîñòîãî êëþ÷à.
Òåîðåìà 5 (èíâàðèàíòíîñòü êëþ÷åé îòíîñèòåëüíî äåëåíèÿ). Ïóñòü R1 — ñõåìà òàá-
ëèöû T1, R2 — ñõåìà òàáëèöû T2 , T
R
R
T T1
1
2
2� � � , K K Kq� { , ..., }1 — êëþ÷ òàáëèöû
T1 è K R� 2 ��. Òîãäà K — êëþ÷ òàáëèöû T
R
R
T1
1
2
2� . Åñëè ïðè ýòîì K — ïðîñòîé
êëþ÷ äëÿ T1, òî K, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ ïðîñòûì êëþ÷îì òàáëèöû T
R
R
T1
1
2
2� .
Äîêàçàòåëüñòâî. Îò ïðîòèâíîãî, äîïóñòèì, ÷òî K íå ÿâëÿåòñÿ êëþ÷îì òàáëèöû
T
R
R
T1
1
2
2� , çíà÷èò, ñóùåñòâóþò òàêèå � �� � �s s T
R
R
T, 1
1
2
2 , ÷òî � � ��s K s K| | è � � ��s s .
Îáîçíà÷èì R A Az2 1� { , ..., } è R K X X p1 1� � { , ..., }, ïðè÷åì ìíîæåñòâî R K1 �
ìîæåò áûòü ïóñòûì. Ïóñòü � � � � � �s K k K k X x X xq q p q{( , ), ..., ( , ), ( , ), ..., ( , )}1 1 1 1 è
�� � �� �� �� ��s K k K k X x X xq q p p{( , ), ..., ( , ), ( , ), ..., (1 1 1 1 )}. Òîãäà èç ðàâåíñòâà � � ��s K s K| |
ñëåäóåò âûïîëíåíèå ðàâåíñòâ � � �� � � ��k k k kq q1 1, ..., , ñëåäîâàòåëüíî, íåðàâåíñòâî
� � ��s s âëå÷åò âûïîëíåíèå õîòÿ áû îäíîãî èç íåðàâåíñòâ:
� � �� � � ��x x x xp p1 1, ..., . (4)
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
Ïîñêîëüêó ïî îïðåäåëåíèþ îïåðàöèè äåëåíèÿ òàáëèö âûïîëíÿþòñÿ ïðè-
íàäëåæíîñòè � �� � �s s TR R, ( )�
1 2 1 , ïî îïðåäåëåíèþ ïðîåêöèè ñóùåñòâóþò íåïóñòûå
ìíîæåñòâà S s T s s1 1 1 1� � � �{ | }è S s T s s2 2 1 2� � �� �{ | }. Ïóñòü � � � �s K k K kq q1 1 1{( , ),... , ( , ) ,
( , ),... , ( , ), ( , ),... , ( , )}X x X x A a A a Sp p z z1 1 1 1 1� � � � � è �� � �� �� ��s K k K k X xq q1 1 1 1 1{( , ),... , ( , ), ( , ),...
..., ( , ), ( , ), ..., ( , )}X x A a A a Sp p z z�� �� �� �1 1 2 . Ïîñêîëüêó K — êëþ÷ òàáëèöû T1 è ðàâå-
íñòâà � � �� � � ��k k k kq q1 1, ..., ýêâèâàëåíòíû ðàâåíñòâó � � ��s K s K1 1| | , äîëæíî âûïîëíÿòüñÿ
ðàâåíñòâî � � ��s s1 1, ïîýòîìó òàêæå äîëæíû âûïîëíÿòüñÿ ðàâåíñòâà � � �� � � ��x x x xp p1 1, ..., ,
÷òî ïðîòèâîðå÷èò (4). Ïîýòîìó äàííîå äîïóùåíèå íåâåðíî.
Âòîðàÿ ÷àñòü òåîðåìû äîêàçûâàåòñÿ ñ ïîìîùüþ êîíòðïðèìåðà. �
Ðàññìîòðèì òåïåðü âòîðîé ñëó÷àé, ïðè êîòîðîì êëþ÷ òàáëèöû T1 ïåðåñåêà-
åòñÿ ñî ñõåìîé òàáëèöû T2 , íî ïðè ýòîì îí ïîëíîñòüþ íå âõîäèò â ñõåìó òàáëè-
öû T2 . Ïîêàæåì, ÷òî îïåðàöèÿ äåëåíèÿ òàáëèö â ýòîì ñëó÷àå ñîõðàíÿåò êëþ÷, íî
íå ñîõðàíÿåò ïðîñòîãî êëþ÷à. Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 6 (èíâàðèàíòíîñòü ÷àñòè êëþ÷à îòíîñèòåëüíî äåëåíèÿ). Ïóñòü R1 — ñõåìà
òàáëèöû T1, R2 — ñõåìà òàáëèöû T2 , T
R
R
T T1
1
2
2� � �, K — êëþ÷ òàáëèöû T1,
K R� 2 � � è � � � � �K K R2 . Òîãäà �K — êëþ÷ äëÿ T
R
R
T1
1
2
2� . Åñëè ïðè ýòîì K —
ïðîñòîé êëþ÷ äëÿ T1, òî �K , âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ ïðîñòûì êëþ÷îì äëÿ T
R
R
T1
1
2
2� .
Äîêàçàòåëüñòâî. Ïóñòü � �K K Kq{ , ..., }1 . Îáîçíà÷èì K R X X p� 2 1� { , ..., },
R K R B B R R K A Ay z2 2 1 1 2 1� � � � �( ) { , ..., }, ( ) { , ..., }� , ïðè÷åì ìíîæåñòâà
R K R2 2� ( )� è ( )R R K1 2� � ìîãóò áûòü ïóñòûìè íåçàâèñèìî îäèí îò äðóãîãî.
Åñëè ìíîæåñòâî ( )R R K1 2� � ïóñòîå, òî �K — ñõåìà òàáëèöû T
R
R
T1
1
2
2� , ñëåäîâà-
òåëüíî, �K ÿâëÿåòñÿ òðèâèàëüíûì êëþ÷îì äëÿ T
R
R
T1
1
2
2� . Ïóñòü ìíîæåñòâî
( )R R K1 2� � íåïóñòîå. Îò ïðîòèâíîãî, äîïóñòèì, ÷òî �K íå ÿâëÿåòñÿ êëþ÷îì òàáëè-
öû T
R
R
T1
1
2
2� , ñëåäîâàòåëüíî, ñóùåñòâóþò òàêèå ñòðîêè � �� � �s s T
R
R
T, 1
1
2
2 , ÷òî
� � � �� �s K s K| | è � � ��s s . Îáîçíà÷èì � � � � � �s A a A a K k K kz z q q{( , ),... , ( , ), ( , ),... , ( , )}1 1 1 1 è
�� � �� �� �� ��s A a A a K k K kz z q{( , ),... , ( , ), ( , ),... , ( ,1 1 1 1 q )}. Èç ðàâåíñòâà � � � �� �s K s K| | è íåðà-
âåíñòâà � � ��s s ñëåäóåò, ÷òî âûïîëíÿåòñÿ õîòÿ áû îäíî èç íåðàâåíñòâ:
� � �� � � ��a a a az z1 1, ..., . (5)
Ïóñòü s X x X x B b B b Tp p y y� �{( , ),...,( , ),( , ),...,( , )}1 1 1 1 2. Òîãäà ïî îïðåäåëåíèþ
îïåðàöèè äåëåíèÿ òàáëèö ñóùåñòâóþò ñòðîêè � � � �s A a A az z1 1 1{( , ), ..., ( , ) ,
( , ),...K k1 1� , ( , ), ( , ),... , ( , ), ( , ),... , ( , )}K k X x X x B b B bq q p p y y� 1 1 1 1 �T1 è �� � ��s A a1 1 1{( , ),...
..., ( , )A az z�� , ( , ),...,( , ),( , ),...,( , ),( ,K k K k X x X x B bq q p p1 1 1 1 1 1�� �� ),...,( , )}B b Ty y � 1. Èç ðàâåí-
ñòâà � � � �� �s K s K| | ñëåäóåò âûïîëíåíèå ðàâåíñòâ � � �� � � ��k k k kq q1 1, ..., , ïîýòîìó âûïîëíÿ-
åòñÿ ðàâåíñòâî � � ��s K s K1 1| | . Ïîñêîëüêó K — êëþ÷ òàáëèöû T1, èç ðàâåíñòâà
� � ��s K s K1 1| | ñëåäóåò ðàâåíñòâî � � ��s s1 1, ïîýòîìó âûïîëíÿþòñÿ ðàâåíñòâà
� � �� � � ��a a a az z1 1, ..., , ÷òî ïðîòèâîðå÷èò (5). Òàêèì îáðàçîì, äàííîå äîïóùåíèå íå-
âåðíî.
Âòîðàÿ ÷àñòü òåîðåìû äîêàçûâàåòñÿ ñ ïîìîùüþ êîíòðïðèìåðà. �
Ðåçóëüòàòû ðàáîòû ñâåäåíû â òàáë. 1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 11
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå èññëåäîâàíà èíâàðèàíòíîñòü êëþ÷åé, â ÷àñòíîñòè è ïðîñòûõ, îòíîñèòåëüíî
ñèãíàòóðíûõ îïåðàöèé òàáëè÷íûõ àëãåáð. Ïîêàçàíî, ÷òî êëþ÷è èíâàðèàíòíû îòíîñè-
òåëüíî îïåðàöèé ïåðåñå÷åíèÿ, ðàçíîñòè è ñåëåêöèè (ñì. ïðåäëîæåíèÿ 1–3), ïðè ýòîì
äëÿ ïðîñòûõ êëþ÷åé èíâàðèàíòíîñòü íå âûïîëíÿåòñÿ, è ÷òî îòíîñèòåëüíî ïåðåèìå-
íîâàíèÿ èíâàðèàíòíû êàê êëþ÷è, òàê è ïðîñòûå êëþ÷è (ñì. ïðåäëîæåíèå 4). Íàéäå-
íû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ, ïðè êîòîðûõ êëþ÷è èíâàðèàíòíû îòíîñè-
òåëüíî àêòèâíîãî äîïîëíåíèÿ (ñì. òåîðåìó 1, ñëåäñòâèÿ 1, 2). Òàêæå íàéäåí êðèòå-
ðèé, ïðè êîòîðîì êëþ÷è (â òîì ÷èñëå è ïðîñòûå) èíâàðèàíòíû îòíîñèòåëüíî
ïðîåêöèè (ñì. òåîðåìû 2, 3). Ïîêàçàíî, ÷òî îáúåäèíåíèå êëþ÷åé òàáëèö ÿâëÿåòñÿ
êëþ÷îì èõ ñîåäèíåíèÿ, â ÷àñòíîñòè, åñëè äâå òàáëèöû èìåþò îäèíàêîâûå êëþ÷è, òî
èõ ñîåäèíåíèå ñîõðàíÿåò êëþ÷ (ñì. òåîðåìó 4, ñëåäñòâèå 3). Äîêàçàíî, ÷òî êëþ÷è
èíâàðèàíòíû îòíîñèòåëüíî äåëåíèÿ (ñì. òåîðåìû 5, 6), ïðè ýòîì äëÿ ïðîñòûõ êëþ-
÷åé èíâàðèàíòíîñòü íå âûïîëíÿåòñÿ. Ðåçóëüòàòû ðàáîòû ïðåäñòàâëÿþò òåîðåòè÷åñêèé
è ïðàêòè÷åñêèé èíòåðåñ è èõ ìîæíî èñïîëüçîâàòü äëÿ âûáîðà îïòèìàëüíûõ êëþ÷åé
ïðè ïðîåêòèðîâàíèè ðåëÿöèîííûõ áàç äàííûõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ o d d E . F . A relational model of data for large shared data banks // Communications of the ACM. —
1970. — 13, N 6. — P. 377–387.
2. C o d d E . F . The relational model for database management: version 2. — Reading: Addison-Wesley,
1990. — 538 p.
3. Ð å ä ü ê î Â . Í . , Á ó é Ä . Á . Ê îñíîâàíèÿì òåîðèè ðåëÿöèîííûõ ìîäåëåé áàç äàííûõ // Êèáåðíåòèêà
è ñèñòåìíûé àíàëèç. — 1996. — ¹ 4. — Ñ. 3–12.
4. Ê î í í î ë è Ò . , Á å ã ã Ê . Áàçû äàííûõ. Ïðîåêòèðîâàíèå, ðåàëèçàöèÿ è ñîïðîâîæäåíèå. Òåîðèÿ è
ïðàêòèêà. — Ì.: Èçä. äîì «Âèëüÿìñ», 2003. — 1440 ñ.
5. Ä å é ò Ê . Ä æ . Ââåäåíèå â ñèñòåìû áàç äàííûõ, 8-å èçäàíèå.: Ïåð. ñ àíãë. — Ì.: Èçä. äîì «Âèëü-
ÿìñ», 2005. — 1328 ñ.
6. Ì å é å ð Ä . Òåîðèÿ ðåëÿöèîííûõ áàç äàííûõ.: Ïåð. ñ àíãë. — Ì.: Ìèð, 1987. — 608 ñ.
7. Ê ó ð à ò î â ñ ê è é Ê . Òîïîëîãèÿ. Ò. 1. – Ì.: Ìèð, 1966. — 594 ñ.
8. Ð å ä ü ê î  . Í . , Á ð î í à Þ . É . , Á ó é Ä . Á . , Ï î ë ÿ ê î â Ñ . À . Ðåëÿö³éí³ áàçè äàíèõ: òàáëè÷í³
àëãåáðè òà SQL-ïîä³áí³ ìîâè. — Êè¿â: ÂÄ «Àêàäåìïåð³îäèêà», 2001. — 198 ñ.
9. Ð è ã å Æ . Áèíàðíûå îòíîøåíèÿ, çàìûêàíèÿ, ñîîòâåòñòâèÿ Ãàëóà // Êèáåðíåòè÷åñêèé ñáîðíèê: ñáîð-
íèê ïåðåâîäîâ. — Ì.: ÈË, 1963. — Âûï. 7. — Ñ. 129–185.
Ïîñòóïèëà 06.02.2015
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
Ò à á ë è ö à 1
Îïåðàöèÿ Ñîõðàíåíèå êëþ÷åé
Ñîõðàíåíèå ïðîñòûõ
êëþ÷åé
Óòâåðæäåíèå
�
R
Äà Íåò Ïðåäëîæåíèå 1
�
R Äà Íåò Ïðåäëîæåíèå 2
�
R Íåò Íåò Î÷åâèäíî
� p Äà Íåò Ïðåäëîæåíèå 3
RT� Äà Äà Ïðåäëîæåíèå 4
~
T
Íàéäåíû êðèòåðèè —
Òåîðåìà 1,
ñëåäñòâèå 1
— Íàéäåíû êðèòåðèè Ñëåäñòâèå 2
� X
Íàéäåíî äîñòàòî÷íîå
óñëîâèå
— Òåîðåìà 2
—
Íàéäåíî äîñòàòî÷íîå
óñëîâèå
Òåîðåìà 3
Äà Íåò
Òåîðåìà 4,
ñëåäñòâèå 3
T
R
R
T1
1
2
2� Íàéäåíî äîñòàòî÷íîå
óñëîâèå
Íåò
Òåîðåìà 5,
òåîðåìà 6
|