Каркасное проектирование доменно-ключевой схемы реляционной базы данных
Запропоновано новий підхід до синтезу ДКНФ для довільної предметної області. Досліджено частковий випадок многозначної залежності — декартова залежність. Доведено лему про безаномальність окремого реляційного відношення і теорему про безаномальність актуальної частини реляційного каркасу. Дано новий...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84118 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Каркасное проектирование доменно-ключевой схемы реляционной базы данных / Б.Е. Панченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 174-187. — Бібліогр.: 20 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84118 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-841182025-02-09T22:26:02Z Каркасное проектирование доменно-ключевой схемы реляционной базы данных Каркасне проектування доменно-ключової схеми реляційної бази даних Framework design of a domain-key scheme of a relational database Панченко, Б.Е. Новые средства кибернетики, информатики, вычислительной техники и системного анализа Запропоновано новий підхід до синтезу ДКНФ для довільної предметної області. Досліджено частковий випадок многозначної залежності — декартова залежність. Доведено лему про безаномальність окремого реляційного відношення і теорему про безаномальність актуальної частини реляційного каркасу. Дано новий критерій приналежності схеми баз даних до ДКНФ. Зроблено висновок про можливість застосування даного підходу до проектування схем інформаційних сховищ. A new approach to the DK/NF synthesis for an arbitrary domain is proposed. The Cartesian dependency as a special case of multivalued dependency is investigated. The lemma about the non-abnormality of special relational and the theorem about the non-abnormality of the actual part of the relational frame are proved. A new criterion for the database scheme’s appurtenance to DK/NF is given. The conclusion about the possibility of applying this approach to the design of information warehouse schemes is made. 2012 Article Каркасное проектирование доменно-ключевой схемы реляционной базы данных / Б.Е. Панченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 174-187. — Бібліогр.: 20 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84118 004.652 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
2012 |
| topic_facet |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84118 |
| citation_txt |
Каркасное проектирование доменно-ключевой схемы реляционной базы данных / Б.Е. Панченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 174-187. — Бібліогр.: 20 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT pančenkobe karkasnoeproektirovaniedomennoklûčevoishemyrelâcionnoibazydannyh AT pančenkobe karkasneproektuvannâdomennoklûčovoíshemirelâcíinoíbazidanih AT pančenkobe frameworkdesignofadomainkeyschemeofarelationaldatabase |
| first_indexed |
2025-12-01T10:36:28Z |
| last_indexed |
2025-12-01T10:36:28Z |
| _version_ |
1850301889799782400 |
| fulltext |
ÓÄÊ 004.652
Á.Å. ÏÀÍ×ÅÍÊÎ
ÊÀÐÊÀÑÍÎÅ ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ ÄÎÌÅÍÍÎ-ÊËÞ×ÅÂÎÉ ÑÕÅÌÛ
ÐÅËßÖÈÎÍÍÎÉ ÁÀÇÛ ÄÀÍÍÛÕ
Êëþ÷åâûå ñëîâà: ñõåìà ðåëÿöèîííîé áàçû äàííûõ, ðåëÿöèîííûé êàðêàñ, äî-
ìåííî-êëþ÷åâàÿ íîðìàëüíàÿ ôîðìà, ïðîèçâîëüíàÿ ïðåäìåòíàÿ îáëàñòü, ñèíòåç
ÄÊÍÔ-ñõåìû.
ÂÂÅÄÅÍÈÅ
Ïðè ðàçðàáîòêå ïðèëîæåíèé è ñèíòåçå ñõåìû áàçû äàííûõ (ÁÄ), ìîäåëèðóþ-
ùèõ ðàçíûå ïðåäìåòíûå îáëàñòè (ÏðÎ) â ðàìêàõ êëàññè÷åñêîé ðåëÿöèîííîé ìî-
äåëè (ÐÌÄ), âîçíèêàþò ñòðóêòóðû äàííûõ, êîòîðûå ïðèíÿòî óïðîùàòü. Â [1]
ïðèâåäåí ñïèñîê òàêèõ ñòðóêòóð: ñâÿçè òèïà F H: , n-àðíûå è ðåêóðñèâíûå
ñâÿçè ñóùíîñòåé-îáúåêòîâ, àòðèáóòû ñâÿçåé, èåðàðõè÷åñêèå çàâèñèìîñòè («ñëà-
áîñòü») ñóùíîñòåé-îáúåêòîâ, ìíîæåñòâåííûå àòðèáóòû, à òàêæå îáñóæäåíà
åùå îäíà íåìàëîâàæíàÿ ïðîáëåìà, êàñàþùàÿñÿ íå ñòîëüêî ïðîåêòèðîâàíèÿ,
ñêîëüêî ýêñïëóàòàöèè ÁÄ, — ìîäèôèöèðóåìîñòü ðåëÿöèîííîé ñõåìû.
Èçâåñòíî, ÷òî ñî âðåìåíåì ëþáóþ ñõåìó ÁÄ, íå îòâå÷àþùóþ íîâûì òðåáî-
âàíèÿì, íåîáõîäèìî îáíîâëÿòü, ÷òî îáû÷íî ñóùåñòâåííî ïîâûøàåò ñòîèìîñòü
ñîïðîâîæäåíèÿ. Ïîýòîìó ÷àñòîå ïåðåïðîåêòèðîâàíèå ñõåìû ÁÄ ïðèâîäèò ê ðå-
èíæèíèðèíãó ïðèëîæåíèé, ÷òî íåæåëàòåëüíî äëÿ ïîëüçîâàòåëåé ââèäó áîëüøèõ
âðåìåííûõ è ôèíàíñîâûõ çàòðàò. Ïîýòîìó ìîäèôèöèðóåìîñòü ñõåìû ÁÄ ñòàíî-
âèòñÿ îäíèì èç ñàìûõ âàæíûõ êðèòåðèåâ êà÷åñòâà ïðèëîæåíèÿ. Ïîíÿòèå «ìîäè-
ôèöèðóåìîñòü» êàê çíà÷èìûé ôàêòîð êà÷åñòâà ñõåìû ÁÄ âïåðâûå ââåäåíî â [2]
è ÷àñòè÷íî ôîðìàëèçîâàíî â [3].  ýòèõ ðàáîòàõ ïîä ìîäèôèöèðóåìîñòüþ ñõåìû
ÁÄ ïîíèìàåòñÿ òàêîå äîáàâëåíèå äîïîëíèòåëüíûõ èëè óäàëåíèå ñóùåñòâóþùèõ
ïîäñõåì ÁÄ, à òàêæå âíåñåíèå èçìåíåíèé â ñõåìó ëþáîãî îòíîøåíèÿ, êîòîðîå íå
çàòðàãèâàåò èíûå îòíîøåíèÿ. Òàêæå ïðåäëîæåí àëãîðèòì ñèíòåçà ìîäèôèöèðóå-
ìûõ ñõåì ÁÄ, ïîêàçàíà çíà÷èìîñòü ñâîéñòâà ìîäèôèöèðóåìîñòè ñõåìû ÁÄ äëÿ
ñîïðîâîæäåíèÿ ïðèëîæåíèé.
 [4] âïåðâûå ñôîðìóëèðîâàíà ãèïîòåçà î òîì, ÷òî ìàêñèìàëüíî âîçìîæíàÿ
ñòåïåíü ìîäèôèöèðóåìîñòè îáåñïå÷åíà òîëüêî ñõåìîé ÁÄ, íàõîäÿùåéñÿ â äî-
ìåííî-êëþ÷åâîé íîðìàëüíîé ôîðìå (ÄÊÍÔ) [5]. Íî äàëåå â ðàáîòàõ àâòîðà [4]
ýòà ãèïîòåçà äîëæíûì îáðàçîì íå ôîðìàëèçîâàíà, àëãîðèòì ñòðîãî íå
îáîñíîâàí, à ïðîöåäóðà ñèíòåçà íå ÿâëÿåòñÿ åäèíñòâåííîé è ïîëíîé.
Ñõåìà ÁÄ, ïîëó÷åííàÿ â ðåçóëüòàòå ðåøåíèÿ îïèñàííûõ ïðîáëåì, äîëæíà
óäîâëåòâîðÿòü â èòîãå äâóì êðèòåðèÿì — êðîññïëàòôîðìíîñòè è èíòåðîïåðà-
áåëüíîñòè [6]. Ïîä «êðîññïëàòôîðìíîñòüþ» ïîíèìàåòñÿ íåçàâèñèìîñòü ïðèëîæå-
íèé êàê îò àïïàðàòíîãî, òàê è îò îïåðàöèîííîãî ïðîãðàììíîãî îáåñïå÷åíèÿ: «íà-
ïèñàííîå îäíàæäû âûïîëíÿåòñÿ âåçäå». Ïîä «èíòåðîïåðàáåëüíîñòüþ» ïîíèìàåò-
ñÿ ñïîñîáíîñòü ïðèëîæåíèé, èíòåðôåéñû êîòîðûõ ïîëíîñòüþ îòêðûòû,
âçàèìîäåéñòâîâàòü è ôóíêöèîíèðîâàòü ñ äðóãèìè ïðèëîæåíèÿìè áåç êàêèõ-ëèáî
îãðàíè÷åíèé äîñòóïà è ðåàëèçàöèè, à òàêæå ñïîñîáíîñòü ïðèëîæåíèÿ âûïîëíÿòü
íàáîð ôóíêöèé, îïðåäåëåííûõ â åãî âíåøíåì îïèñàíèè è óäîâëåòâîðÿþùèõ
çàäàííûì èëè ïîäðàçóìåâàåìûì ïîòðåáíîñòÿì ïîëüçîâàòåëåé.
Èñõîäÿ èç îïðåäåëåíèÿ ñõåìû ÁÄ, ýòè ñâîéñòâà, ïðåæäå âñåãî, ñâîäÿòñÿ ê
òîìó, ÷òî ðàçíûå ïðèëîæåíèÿ ÁÄ, ðàáîòàþùèå íà ðàçíûõ ïëàòôîðìàõ, èíòåãðè-
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
© Á.Å. Ïàí÷åíêî, 2012
ðóþòñÿ â îäíî. Ïðè ýòîì ÁÄ âîñïðèíèìàåòñÿ êàê åäèíîå öåëîå. Îáåñïå÷èò ýòî
ñâîéñòâî óíèâåðñàëüíîñòü ñõåìû ÁÄ äëÿ ðàçíûõ ÏðÎ. Äàëåå áóäåò ïîêàçàíî, ÷òî
ñõåìà ÁÄ, îáëàäàþùàÿ óíèâåðñàëüíîñòüþ è ïîäîáèåì, ïðè îïðåäåëåííûõ óñëî-
âèÿõ óäîâëåòâîðÿåò êðèòåðèÿì áåçàíîìàëüíîñòè è ìîäèôèöèðóåìîñòè.
Íî, êàê ïîêàçûâàåò îïûò ïðàêòè÷åñêîé ýêñïëóàòàöèè, âñå ñóùåñòâóþùèå íà
ðûíêå èíñòðóìåíòàëüíûå ñðåäñòâà ñèíòåçà ïðèëîæåíèé, à òàêæå âñå ñåðâåðû ÁÄ
ïðåäëàãàþò ïîëüçîâàòåëþ ñàìîñòîÿòåëüíî îïðåäåëèòüñÿ ñ âûáîðîì ñõåìû ÁÄ —
òî ëè â ÐÌÄ, òî ëè â ìîäåëè îáúåêòíî-îðèåíòèðîâàííîé áàçû äàííûõ (ÎÎÁÄ).
Ïðè ýòîì äëÿ áîëüøèíñòâà ñåðâåðîâ ÁÄ, ðàçðàáîòàííûõ â ñîîòâåòñòâèè ñ ÐÌÄ,
íå íàêëàäûâàåòñÿ ñóùåñòâåííûõ îãðàíè÷åíèé íà íîðìàëüíîñòü îòíîøåíèé.
À çíà÷èò, è íà èòîãîâóþ ñõåìó ÁÄ. Îäíàêî òàêàÿ «ìàðêåòèíãîâàÿ» êîíöåïöèÿ
èíñòðóìåíòàëüíûõ ñðåäñòâ, êàê ïðàâèëî, ïðèâîäèò ê ïîëíîé íåñîâìåñòèìîñòè
ïðèëîæåíèé äàæå â ðàìêàõ îäíîé ïëàòôîðìû è ê íåâûñîêîìó êîýôôèöèåíòó ïî-
ëåçíîãî äåéñòâèÿ (ÊÏÄ) ïðèëîæåíèÿ.
Äëÿ ðåøåíèÿ óêàçàííûõ ïðîáëåì ñóùåñòâóåò äâà ïîäõîäà. Ïåðâûé — ýòî
ðàçðàáîòêà ïðèëîæåíèé íà áàçå ñóùåñòâóþùèõ íà ðûíêå èíñòðóìåíòàëüíûõ
ñðåäñòâ è ñåðâåðîâ ÁÄ, îäíàêî ñ èñïîëüçîâàíèåì âûñîêîíîðìàëèçîâàííîé
(è äàæå áåçàíîìàëüíîé) ñõåìû ÁÄ. Îïûò ðàçðàáîòîê ïîçâîëÿåò óòâåðæäàòü, ÷òî
ýêñïëóàòàöèîííûå õàðàêòåðèñòèêè ïðèëîæåíèé (ñêîðîñòü äîñòóïà ê äàííûì,
ñêîðîñòü âíåñåíèÿ ìîäèôèêàöèé â ñõåìó ÁÄ è â ñàìî ïðèëîæåíèå â äèíàìè÷åñ-
êîì ðåæèìå, êðîññïëàòôîðìíîñòü è èíòåðîïåðàáåëüíîñòü ïðèëîæåíèé) ñóùåñò-
âåííî ïîâûøàþòñÿ. Âòîðîé ïîäõîä — ýòî ðàçðàáîòêà óíèêàëüíîãî èíñòðóìåí-
òàëüíîãî ñðåäñòâà, íåïîñðåäñòâåííî èñïîëüçóþùåãî âñå óêàçàííûå ïðåèìóùåñò-
âà èìåííî áåçàíîìàëüíîé ñõåìû ÁÄ, â òîì ÷èñëå è ìèíèìàëüíî íåîáõîäèìîå
÷èñëî îïåðàöèé ñîåäèíåíèé äëÿ îòâåòîâ íà çàïðîñû ïîëüçîâàòåëåé.
Àíàëèç ÏðÎ, îñíîâàííûé íà êëàññè÷åñêîì ìåòîäå äåêîìïîçèöèè [7], ïðèâî-
äèò ê ñõåìàì ÁÄ, ñóùåñòâåííî îòëè÷àþùèìñÿ îäíà îò äðóãîé â çàâèñèìîñòè îò
ñïåöèôèêè ÏðÎ. Áîëåå òîãî, ñóáúåêòèâíûé ôàêòîð ïðîåêòèðîâàíèÿ ÿâëÿåòñÿ ðå-
øàþùèì. Ýòî ïðèâîäèò ê áîëüøîé çàâèñèìîñòè ïðèëîæåíèÿ îò âñåâîçìîæíûõ
ìîäèôèêàöèé.
Õîòÿ êëàññè÷åñêàÿ ÐÌÄ îñíîâàíà íà î÷åíü æåñòêîì àëãîðèòìå, ñëàáî ïîääà-
þùåìñÿ óíèôèêàöèè, èäåÿ óíèâåðñàëüíîñòè íå íîâà. Åå ïðîÿâëåíèå ñîñòîèò â àë-
ãîðèòìå ñèíòåçà ñõåìû îòíîøåíèÿ, ïðåäëîæåííîì Ô.À. Áåðíøòåéíîì [8]. Ýòà
èäåÿ åñòü êàê â âûâîäàõ ðàáîòû Ï. ×åíà [9], òàê è â ñàìîì åå íàçâàíèè. Ïîýòîìó
ðàçðàáîòêà íîâîé, áîëåå óíèâåðñàëüíîé ìåòîäèêè àíàëèçà ÏðÎ, ïîçâîëÿþùåé
ñèíòåçèðîâàòü òàêèå áåçàíîìàëüíûå ñõåìû ÁÄ, êîòîðûå îáëàäàëè áû ïðè ýòîì
åùå è âûñîêîé ñòåïåíüþ ìîäèôèöèðóåìîñòè è ïîäîáèÿ äëÿ ðàçíûõ ÏðÎ, ÿâëÿ-
åòñÿ âàæíîé çàäà÷åé. Êàê èçâåñòíî, äî ïóáëèêàöèè [10] íå ñóùåñòâîâàëî ñòðîãî
îáîñíîâàííîãî àëãîðèòìà ñèíòåçà ÄÊÍÔ, ÷òî è îòìå÷åíî â [10]. Ñåé÷àñ íà ýòó
ðîëü ïðåòåíäóåò ñïîñîá [3], îñíîâàííûé íà ðåëÿöèîííîì êàðêàñå è êàðêàñíîé
ìîäåëè äàííûõ. Âïåðâûå îí îôèöèàëüíî ïðåäëîæåí â 2001 ã. [2].
Îòìåòèì, ÷òî â [11] ÷àñòè÷íî îïèñàíà ìîäåëü ïîâåäåíèÿ ñèñòåì [12], òàêæå
îñíîâàííàÿ íà ìíîæåñòâå âñåõ ïîäìíîæåñòâ (áóëåàíå) ñâÿçåé. Îäíàêî àâ-
òîð [11] â ñâîèõ äàëüíåéøèõ ðàáîòàõ ýòîò ìåòîä íå ðàçâèâàë. Äî ïóáëèêàöèè
ðàáîòû [2] áûëà ïðåäïðèíÿòà ïîïûòêà (ñì. [13]) èñïîëüçîâàòü áóëåàí êàê ñå-
ìàíòè÷åñêîå ðàñøèðåíèå ðåëÿöèîííîé ìîäåëè. Îäíàêî ýòîò ïîäõîä íå áûë ðàç-
âèò äî àëãîðèòìà ïðîåêòèðîâàíèÿ îïòèìàëüíûõ ñõåì ðåëÿöèîííûõ ÁÄ.
ÍÎÂÛÉ ÏÎÄÕÎÄ Ê ÀÍÀËÈÇÓ ÌÍÎÃÎÇÍÀ×ÍÎÉ ÇÀÂÈÑÈÌÎÑÒÈ Â ÑÕÅÌÀÕ ÐÁÄ
Âîïðîñ ðàçðàáîòêè åäèíîãî àëãîðèòìà ñèíòåçà ÄÊÍÔ, ââåäåííîé Ð. Ôåéäæè-
íûì â 1981 ã. [5], ìàëî èññëåäîâàí. Ñóùåñòâóþò íåêîòîðûå ðàáîòû äðóãèõ àâ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 175
òîðîâ, ãäå îáñóæäàþòñÿ êàê çíà÷èòåëüíûå ïðåèìóùåñòâà áåçàíîìàëüíîé ñõåìû
ÁÄ [4], òàê è åå ãèïîòåòè÷åñêèå íåäîñòàòêè [14–16].
 ðàáîòå Ï. ×åíà [9] ïðåäëîæåí àëãîðèòì èññëåäîâàíèÿ ÏðÎ ïóòåì îòäåëå-
íèÿ ñóùíîñòåé-îáúåêòîâ â ñòàòè÷åñêîì ñîñòîÿíèè îò èõ ñâÿçåé. Îäíàêî âîïðîñ
íîðìàëèçàöèè îòíîøåíèé, êàæäîå èç êîòîðûõ îòäåëüíî ìîäåëèðóåò êàæäóþ ñâÿçü,
íå áûë èçó÷åí. Àëãîðèòì, ïðåäëîæåííûé â ñåðèè ðàáîò àâòîðà [4], òàêæå îñíîâàí-
íûé íà èäåå ×åíà, ñòðîãî íå îáîñíîâàí. È âîïðîñ èñêëþ÷åíèÿ ìíîãîçíà÷íûõ çàâè-
ñèìîñòåé (ÌÇ), à òàêæå çàâèñèìîñòåé ïðîåêöèè ñîåäèíåíèÿ (ÇÏÑ), ÿâíî ïðèñóò-
ñòâóþùèõ â îòíîøåíèÿõ äëÿ ñâÿçåé áîëåå âûñîêîé àðíîñòè, â ðàáîòå [4] íå ðàñ-
ñìîòðåí. Õîòÿ îáùèé âûâîä î òîì, ÷òî ñõåìà ÁÄ, êàæäîå îòíîøåíèå êîòîðîé
íàõîäèòñÿ â ÄÊÍÔ, îáëàäàåò åùå è ìàêñèìàëüíîé ñòåïåíüþ ìîäèôèöèðóåìîñòè
è ïîýòîìó «ìîæåò ñëóæèòü îñíîâîé òèïèçàöèè è óíèôèêàöèè â ïðîåêòèðîâà-
íèè» [4], ÷àñòè÷íî ñîâïàäàåò ñ âûâîäàìè, ïîëó÷åííûìè ðàíåå [1, 2], îäíàêî
ëèøü äëÿ åäèíñòâåííîé ñîâîêóïíîñòè îòíîøåíèé — êàðêàñíîé.
Âèäèìî, òî îáñòîÿòåëüñòâî, ÷òî Ð. Ôåéäæèí íå ðàññìîòðåë îäèí âàæíûé ÷àñò-
íûé ñëó÷àé, êîãäà êîíêàòåíàöèÿ àòðèáóòîâ ñ ÌÇ èëè ÇÏÑ [5, 17] ÿâëÿåòñÿ äåòåð-
ìèíàíòîì íåïóñòîãî ìíîæåñòâà íåêëþ÷åâûõ àòðèáóòîâ, è ñëóæèò ïðè÷èíîé òîãî,
÷òî ÄÊÍÔ, ïî ñëîâàì Ä. Êðåíêå [10], «äî íàñòîÿùåãî âðåìåíè ÿâëÿåòñÿ ñêîðåå èñ-
êóññòâîì, ÷åì íàóêîé». Çàïîëíåíèþ ýòîãî ïðîáåëà è ïîñâÿùåíà äàííàÿ ðàáîòà.
Èññëåäîâàíèÿ ïîêàçûâàþò, ÷òî ðåëÿöèîííûé êàðêàñ [1] — ýòî ôîðìàëèçî-
âàííûé íîñèòåëü ïîëíîãî ìíîãîîáðàçèÿ ñâÿçåé àòîìàðíûõ ñóùíîñòåé-îáúåêòîâ,
êàæäàÿ àêòóàëüíàÿ ÿ÷åéêà êîòîðîãî ïðè îïðåäåëåííûõ óñëîâèÿõ ñòðîãî ñîîòâåò-
ñòâóåò êðèòåðèÿì áåçàíîìàëüíîñòè [5]. Ïðîàíàëèçèðóåì áîëåå ïîäðîáíî ÌÇ. Äëÿ
ýòîãî ðàññìîòðèì îäíó èç òåîðåì Ôåéäæèíà [17].
Òåîðåìà 1 (òåîðåìà Ôåéäæèíà î ÌÇ). ÌÇ X Y� � âûïîëíÿåòñÿ äëÿ îòíî-
øåíèÿ R X Y Z( , , ) òîãäà è òîëüêî òîãäà, êîãäà R ÿâëÿåòñÿ ñîåäèíåíèåì ñâîèõ ïðî-
åêöèé R X Y1 ( , ) è R X Z2 ( , ) .
 ðàáîòå [17] àâòîð ïðèâîäèò íåñòðîãîå äîêàçàòåëüñòâî ýòîé òåîðåìû. Ïðî-
ñòîé ïðîâåðêîé òîãî ôàêòà, ÷òî R X Y Z( , , ) ÿâëÿåòñÿ ñîåäèíåíèåì ñâîèõ ïðîåê-
öèé R X Y1 ( , ) è R X Z2 ( , ), îáîñíîâûâàåòñÿ óòâåðæäåíèå, ÷òî ýòî óñëîâèå âûïîëíÿ-
åòñÿ. «Âñÿêèé ðàç, êîãäà R ñîäåðæèò ( , , )x y z è ( , , )x y z� � , îáÿçàòåëüíî áóäóò ïðè-
ñóòñòâîâàòü è êîðòåæè ( , , )x y z� è ( , , )x y z� . Ýòî ïîñëåäíåå óñëîâèå âûïîëíÿåòñÿ
òîãäà è òîëüêî òîãäà, êîãäà â îòíîøåíèè êîðòåæè òîæäåñòâåííû Y Yxz xz� ' . Òåî-
ðåìà ñëåäóåò èç îïðåäåëåíèÿ ÌÇ». �
Îïèøåì îäèí âàæíûé ÷àñòíûé ñëó÷àé. Äëÿ ýòîãî íà áàçå òåîðåìû Ôåéäæè-
íà î ÌÇ ñôîðìóëèðóåì íîâîå óòâåðæäåíèå.
Ëåììà 1.  îòíîøåíèè ñî ñõåìîé R X Y Z( , , ), êîòîðîå ïîëó÷åíî îïåðàöèåé äå-
êàðòîâà ïðîèçâåäåíèÿ óíàðíûõ îòíîøåíèé R X R Y R Z1 2 3( ) ( ) ( )� � , ãäå X Y Z, , —
â îáùåì ñëó÷àå íåïóñòûå ñîñòàâíûå àòðèáóòû, äëÿ ëþáûõ ( , , )X Y Z âñåãäà ñó-
ùåñòâóþò êîðòåæè: r x y z1 � ( , , ) , r x y z2 1� ( , , ), r x y z3 1� ( , , ), r x y z4 1 1� ( , , ).
Îáðàòíîå óòâåðæäåíèå, âîîáùå ãîâîðÿ, íåâåðíî. Îòëè÷èå — âîçìîæíîñòü
ñóùåñòâîâàíèÿ â R X Y Z( , , ) ôóíêöèîíàëüíûõ çàâèñèìîñòåé (ÔÇ) ìåæäó àòðèáó-
òàìè, êîòîðûå ëèøü ñîêðàùàþò ýêñòåíñèîíàë îòíîøåíèÿ, îäíàêî íå èñêëþ÷àþò
îãîâàðèâàåìûõ ëåììîé çàêîíîìåðíîñòåé â êîðòåæàõ.
Ïðèâåäåì òàêæå íåñòðîãîå äîêàçàòåëüñòâî ýòîé ëåììû. Äîñòàòî÷íî ðàññìîò-
ðåòü îïåðàöèþ äåêàðòîâà ïðîèçâåäåíèÿ. Äåéñòâèòåëüíî, ïóòåì ïðÿìîãî ïðèìåíå-
íèÿ îïåðàöèè íàä òðåìÿ ïðîèçâîëüíûìè îäíîìåñòíûìè ìíîæåñòâàìè, â êàæäîì
èç êîòîðûõ èìååòñÿ íå ìåíüøå äâóõ ýëåìåíòîâ (òðèâèàëüíûé ñëó÷àé, êîãäà ìíî-
æåñòâà ïóñòû èëè ñîñòîÿò èç îäíîãî ýëåìåíòà, íå ðàññìàòðèâàåòñÿ), íåìåäëåííî
ïîëó÷èì âûïîëíåíèå óòâåðæäåíèÿ ëåììû. �
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Òîò ôàêò, ÷òî ê àíàëîãè÷íîìó ÷åðåäîâàíèþ ýëåìåíòîâ èòîãîâîãî ìíîæåñòâà
ïðèâîäèò è ÌÇ, êîãäà â ðåçóëüòèðóþùåì îòíîøåíèè êàê îãðàíè÷åíèå [5] ñóùåñ-
òâóþò åùå ÔÇ ìåæäó îäíèì èç àòðèáóòîâ (íàïðèìåð, X ) è êàæäûì èç äâóõ äðó-
ãèõ — è Y , è Z (íî òåì íå ìåíåå ìåæäó àòðèáóòàìè Y è Z íèêàêîé çàâèñèìîñòè
íå ñóùåñòâóåò), ãîâîðèò î òîì, ÷òî îïèñàííàÿ çàâèñèìîñòü ÿâëÿåòñÿ ÷àñòíûì ñëó-
÷àåì ÌÇ. Ïî àíàëîãèè ñ ìíîãîçíà÷íîé â äàëüíåéøåì áóäåì íàçûâàòü åå äåêàðòî-
âîé çàâèñèìîñòüþ (ÄÇ), ïîíèìàÿ òîò ôàêò, ÷òî ÄÇ ìîäåëèðóåò ïîëíóþ íåçàâèñè-
ìîñòü àòðèáóòîâ ìåæäó ñîáîé è îáåñïå÷èâàåò ïîëíîòó íàáîðà êîðòåæåé â ðåçóëü-
òèðóþùåì îòíîøåíèè.
Íèæå äàíî ñòðîãîå îïðåäåëåíèå ÄÇ è åå ñâîéñòâ. Â ñîîòâåòñòâèè ñ óòâåðæäå-
íèåì ëåììû 1 è ÌÇ, è ÇÏÑ áóäåì íàçûâàòü îáîáùåíèåì ÄÇ, ïîñêîëüêó èìåííî
ïðè òàêîé ôîðìóëèðîâêå ïîíÿòíûì ñòàíîâèòñÿ ôèçè÷åñêèé ñìûñë è ÌÇ, è ÇÏÑ.
Èìååò ìåñòî ñëåäóþùåå óòâåðæäåíèå.
Ëåììà 2. Äåêàðòîâà çàâèñèìîñòü àòðèáóòîâ â îòíîøåíèè R X Y Z( , , ) ìîäåëè-
ðóåò ïîëíóþ ñîâîêóïíîñòü ñâÿçåé ìåæäó àòðèáóòàìè X Y, è Z ýòîãî îòíîøåíèÿ R.
Äîêàçàòåëüñòâî íå ïðîâîäèì â ñâÿçè ñ åãî î÷åâèäíîñòüþ.
Íà îñíîâàíèè ýòèõ ëåìì ïðîåêòèðîâùèê ïîëó÷àåò âîçìîæíîñòü èñïîëüçî-
âàòü îòíîøåíèå, â îñíîâå êîòîðîãî ëåæàò îáîáùåíèÿ ÄÇ (èëè ÌÇ, èëè ÇÏÑ), êî-
òîðûå òàêæå ìîäåëèðóþò ñâÿçü ñòåïåíè F H: , íî íå ìåæäó ïîëíûì ñî÷åòàíèåì
âñåõ àòðèáóòîâ, à ëèøü ìåæäó ñî÷åòàíèåì ÷àñòè èç íèõ.
Òàêèì îáðàçîì, îòíîøåíèå R X Y Z( , , ), ãäå ïî àíàëîãèè ñ [17] ïîä X â îáùåì
ñëó÷àå ïîíèìàåòñÿ ñîâîêóïíîñòü { }x xn1,� , ïîä Y — { }y ym1,� , à ïîä Z —
{ }z zl1,� , êîòîðîå ñîäåðæèò ÄÇ, ÿâëÿåòñÿ ïðåäåëüíûì ñëó÷àåì îòíîøåíèÿ, ìî-
äåëèðóþùåãî ïîëíóþ ñâÿçü ìåæäó ñîîòâåòñòâóþùèìè ñóùíîñòÿìè-îáúåêòàìè
ÏðÎ. Ïðè ýòîì åäèíñòâåííîå îòíîøåíèå ìîäåëèðóåò îäíó ñâÿçü óêàçàííîé ñòå-
ïåíè, à ïîëíàÿ ñîâîêóïíîñòü òàêèõ îòíîøåíèé ìîäåëèðóåò âñþ ïîëíîòó ñâÿçåé.
Íà ýòîì ïðèíöèïå è ïîñòðîåíà êàðêàñíàÿ ìîäåëü äàííûõ.
Çàìåòèì, ÷òî âî ìíîãèõ êëàññè÷åñêèõ ìîíîãðàôèÿõ ïî ÁÄ, áîëüøîé îáçîð
êîòîðûõ ïðèâåäåí â ñåðèè ó÷åáíûõ ïîñîáèé àâòîðà [18], íå ïîÿñíÿþò ïðîåêòè-
ðîâùèêó ôèçè÷åñêèé ñìûñë ÇÏÑ. À ìåæäó òåì èìåííî ÄÇ äàåò íåôîðìàëüíîå
ïðåäñòàâëåíèå è î ÌÇ, è î ÇÏÑ êàê î ïîäìíîæåñòâå êîðòåæåé èç îòíîøåíèÿ ñ ÄÇ.
Äåéñòâèòåëüíî, åñëè â îòíîøåíèè R X Y Z( , , ) ñóùåñòâóåò ÌÇ X Y Z�� / ,
òî ïðè ïîëíîì íàáîðå êîðòåæåé ÌÇ òîæäåñòâåííà ÄÇ.
 îòíîøåíèè R X Y Z( , , ) ìîæåò îòñóòñòâîâàòü ÌÇ X Y Z�� / , íî ñóùåñò-
âîâàòü ÇÏÑ *[ ( , ), ( , ), ( , )]R X Y R X Z R Y Z1 2 3 , ò.å. òàêàÿ çàâèñèìîñòü, ÷òî îïåðà-
öèÿ ñîåäèíåíèÿ ëþáîé ïàðû èç òðåõ ïðîåêöèé R X Y R X Z R Y Z1 2 3( , ), ( , ), ( , )
âîçâðàùàåò îòíîøåíèå R X Y Z' ( , , ) , ñòðîãî òîæäåñòâåííîå R X Y Z( , , ) . Ýòî îçíà-
÷àåò, ÷òî â ñîåäèíåííîì îòíîøåíèè êîðòåæåé íå áîëüøå, è íå ìåíüøå, ÷åì â èñ-
õîäíîì. Ýòî, â ñâîþ î÷åðåäü, ãîâîðèò î òîì, ÷òî èç ïîëíîãî îòíîøåíèÿ, îáëàäàâ-
øåãî ÄÇ, «âû÷åðêíóëè» êîðòåæè òàê, ÷òî îñòàëàñü òîëüêî ÇÏÑ.
Åäèíñòâî ÌÇ è ÇÏÑ â [5, 17] ïîêàçàíî â âèäå íåîáõîäèìîãî óñëîâèÿ âûïîë-
íåíèÿ â îòíîøåíèè R U( ) ÇÏÑ*[ , ]R R R p1 2 � �� , ãäåU — ìíîæåñòâî âñåõ àòðèáó-
òîâ îòíîøåíèÿ R (U R R R p� 1 2 ... ).
Ñîãëàñíî [5, 17, 19] îòíîøåíèå R óäîâëåòâîðÿåò ÌÇ X Y Z�� / òîãäà è
òîëüêî òîãäà, êîãäà R äåêîìïîçèðóåòñÿ áåç ïîòåðü íà R X Y1 ( , ) è R X Z2 ( , ) , ãäå
Z R X Y� � ( , ) . Êàê âèäíî, ýòî óñëîâèå ñîâïàäàåò ñ óñëîâèåì çàâèñèìîñòè ñîåäè-
íåíèÿ *[ , ]XY YZ . Èíà÷å çàâèñèìîñòü ñîåäèíåíèÿ *[ , ]R R1 2 èìååò òîò æå ñìûñë,
÷òî è ÌÇ: R R R1 2 1� �� .
Äëÿ ÇÏÑ ìîæíî ïðèâåñòè îïðåäåëåíèå, àíàëîãè÷íîå îïðåäåëåíèþ ÌÇ.
Ïóñòü R óäîâëåòâîðÿåò çàâèñèìîñòè ñîåäèíåíèÿ *[ , ]R R R p1 2 � �� . Åñëè R
ñîäåðæèò êîðòåæè t t t p1 2, � �� òàêèå, ÷òî äëÿ âñåõ ( , )i j t R R t R Ri i j j i j( ) ( )� �� ,
òî R ñîäåðæèò è êîðòåæ t òàêîé, ÷òî t R t Ri i i( ) ( )� , ãäå 1 � �i p.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 177
Îãðàíè÷åíèÿ ÏðÎ ñîêðàùàþò ïîëíîòó îòíîøåíèÿ, ìîäåëèðóþùåãî ñâÿçü.
Ýòî âàæíîå îáñòîÿòåëüñòâî íåîáõîäèìî äëÿ ïîíèìàíèÿ ðîëè ÄÇ â ñèíòåçå ÄÊÍÔ.
Ïîñêîëüêó ÄÇ — ÷àñòíûé ñëó÷àé è ÌÇ, è ÇÏÑ, ñïðàâåäëèâî ñëåäóþùåå
óòâåðæäåíèå: åñëè îòíîøåíèå îáëàäàåò ÄÇ, îíî àâòîìàòè÷åñêè îáëàäàåò è ÌÇ,
è ÇÏÑ. Î÷åâèäíî, ÷òî îáðàòíîå — íåâåðíî.
Óíèêàëüíîñòü ÄÇ äëÿ ìîäåëèðîâàíèÿ ñâÿçåé ìåæäó ñóùíîñòÿìè-îáúåêòàìè
çàêëþ÷àåòñÿ â ñëåäóþùåì. Ñàìà çàâèñèìîñòü ÿâëÿåòñÿ ìèíèìàëüíî âîçìîæíûì
«ìíîãîçíà÷íûì» ÷àñòíûì ñëó÷àåì ÌÇ. Íî îòíîøåíèå ñ ÄÇ îáëàäàåò ìàêñèìàëü-
íî âîçìîæíûì íàáîðîì êîðòåæåé. ÇÏÑ, íàîáîðîò, — ïðåäåëüíûé ñëó÷àé ìíîãî-
çíà÷íîãî îáîáùåíèÿ ÔÇ, à îòíîøåíèå ñ ÇÏÑ — ÷àñòíûé ñëó÷àé íàáîðà êîðòå-
æåé. Èç ýòîãî ñëåäóåò, ÷òî äëÿ ìîäåëèðîâàíèÿ ïðîèçâîëüíûõ ñâÿçåé â ÏðÎ íåîá-
õîäèìî â êà÷åñòâå øàáëîíà èñïîëüçîâàòü òîëüêî îòíîøåíèÿ ñ ÄÇ.
Äðóãèìè ñëîâàìè, åñëè â îòíîøåíèè ñ ÄÇ ÏðÎ «ïðîèçâîëüíî âû÷åðêèâàåò»
íåêîòîðûå íàáîðû êîðòåæåé, òî â îòíîøåíèè âîçíèêàåò èëè ÔÇ, èëè ÌÇ, èëè
ÇÏÑ. Ïî àíàëîãèè ñ ðàáîòîé [17] íà îñíîâàíèè ëåììû 1 äàäèì ñòðîãîå îïðåäåëå-
íèå ÄÇ.
Îïðåäåëåíèå ÄÇ. Ïóñòü R — ðåëÿöèîííàÿ ñõåìà, X è Y — íåïåðåñåêàþùè-
åñÿ ïîäìíîæåñòâà R , ïðè÷åì òàê, ÷òî Z R X Y� � ( ) , à òàêæå òàêàÿ ñõåìà, ÷òî
ìåæäó àòðèáóòàìè X Y Z, , îòñóòñòâóåò ÔÇ. Îòíîøåíèå R óäîâëåòâîðÿåò ÄÇ
X Y Z�� // , åñëè äëÿ ëþáûõ äâóõ êîðòåæåé: r x y z1 � ( , , ) , r x y z2 1 1� ( , , ), â R
îáÿçàòåëüíî íàéäóòñÿ è êîðòåæè r x y z3 1� ( , , ), r x y z4 1� ( , , ).
Áóäåì îáîçíà÷àòü ÄÇ äîïîëíèòåëüíîé íàêëîííîé ÷åðòîé ìåæäó èìåíàìè àò-
ðèáóòîâ, ïîä÷åðêèâàÿ òåì ñàìûì, ÷òî â êîíòåêñòå ÐÌÄ ÄÇ ÿâëÿåòñÿ ÷àñòíûì
ñëó÷àåì ÌÇ. Òîãäà äëÿ îòíîøåíèÿ R, ñîäåðæàùåãî ÄÇ, ñïðàâåäëèâî ñëåäóþùåå
ñâîéñòâî.
Òåîðåìà 2. Äåêàðòîâà çàâèñèìîñòü (ÄÇ) X Y Z�� // âûïîëíÿåòñÿ äëÿ îòíî-
øåíèÿ R X Y Z( , , ) òîãäà è òîëüêî òîãäà, êîãäà R ÿâëÿåòñÿ ñîåäèíåíèåì áåç ïîòåðü
ïðîåêöèé ïî âñåì ñâîèì àòðèáóòàì: R X1 ( ), R Y2 ( ) è R Z3 ( ).
Äîêàçàòåëüñòâî ïðîâåäåì ïî àíàëîãèè ñ [19].
Íåîáõîäèìîñòü. Ïóñòü èìååòñÿ ÄÇ X Y Z�� / / . Äîêàæåì, ÷òî äåêîìïîçè-
öèÿ îòíîøåíèÿ R íà ïðîåêöèè R X1 ( ), R Y2 ( ) è R Z3 ( ) ÿâëÿåòñÿ äåêîìïîçèöèåé
áåç ïîòåðü. Íóæíî äîêàçàòü, ÷òî R R X R Y R Z� � �1 2 3( ) ( ) ( ) äëÿ ëþáîãî ñîñòîÿ-
íèÿ îòíîøåíèÿ R . Ïóñòü êîðòåæ r x y z R X R Y R Z( , , ) ( ) ( ) ( )
� �1 2 3 . Ýòî îçíà÷à-
åò, ÷òî â ïðîåêöèè R X1 ( ) ñîäåðæèòñÿ êîðòåæ � �r x1 , â ïðîåêöèè R Y2 ( ) — êîðòåæ
� �r y2 , à â ïðîåêöèè R Z3 ( ) — êîðòåæ � �r z3 . Ïî îïðåäåëåíèþ ïðîåêöèè íàéäåòñÿ
òàêîå çíà÷åíèå z1 àòðèáóòà Z , ÷òî îòíîøåíèå R ñîäåðæèò êîðòåæ r x y z1 1� ( , , ).
Àíàëîãè÷íî íàéäåòñÿ òàêîå çíà÷åíèå y1 àòðèáóòà Y , ÷òî îòíîøåíèå R ñîäåðæèò
êîðòåæ r x y z2 1� ( , , ) . Òîãäà ïî îïðåäåëåíèþ ÄÇ êîðòåæ r x y z R( , , )
.
Äîñòàòî÷íîñòü. Ïóñòü äåêîìïîçèöèÿ îòíîøåíèÿ R íà ïðîåêöèè R X1 ( ) ,
R Y2 ( ) è R Z3 ( ) ÿâëÿåòñÿ äåêîìïîçèöèåé áåç ïîòåðü. Äîêàæåì ÷òî îòíîøåíèå ñî-
äåðæèò ÄÇ X Y Z�� // . Ïðåäïîëîæèì, ÷òî îòíîøåíèå R ñîäåðæèò êîðòåæè
r x y z1 1� ( , , ) è r x y z2 1� ( , , ). Íåîáõîäèìî äîêàçàòü, ÷òî êîðòåæ r x y z3 � ( , , ) òàêæå
ñîäåðæèòñÿ â R. Ïî îïðåäåëåíèþ ïðîåêöèé êîðòåæ � �r x1 ñîäåðæèòñÿ â R X1 ( ),
êîðòåæ � �r y2 — â R Y2 ( ), à êîðòåæ � �r z3 — â R Z3 ( ) . Òîãäà êîðòåæ r x y z3 � ( , , )
ñîäåðæèòñÿ â äåêàðòîâîì ïðîèçâåäåíèè R X R Y R Z1 2 3( ) ( ) ( )� � , à â ñèëó òîãî, ÷òî
äåêîìïîçèöèÿ ÿâëÿåòñÿ äåêîìïîçèöèåé áåç ïîòåðü, ýòîò êîðòåæ ñîäåðæèòñÿ è â R. �
Âûøå îòìå÷àëîñü, ÷òî ïîñêîëüêó ÄÇ ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì ÌÇ, îòíîøå-
íèå R , îáëàäàþùåå ÄÇ, òàêæå îáëàäàåò è ÌÇ, è ÇÏÑ. Ïîýòîìó ñàìî îòíîøåíèå R
ÿâëÿåòñÿ îáîáùåíèåì îòíîøåíèÿ �R , îáëàäàþùåãî òîëüêî ÌÇ (à çíà÷èò, è ÇÏÑ),
à òàêæå îòíîøåíèÿ ��R , îáëàäàþùåãî òîëüêî ÇÏÑ.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ïðèâåäåì ýòî óòâåðæäåíèå â âèäå òåîðåìû.
Òåîðåìà 3. Îòíîøåíèå R X Y Z( , , ), â êîòîðîì ñîäåðæèòñÿ ÄÇ X Y Z�� // , ÿâ-
ëÿåòñÿ ñîåäèíåíèåì áåç ïîòåðü âñåõ òèïîâ ïðîåêöèé: èëè ïðîåêöèé òîëüêî ïî
âñåì ñâîèì àòðèáóòàì R X1 ( ), R Y2 ( ), R Z3 ( ), èëè äâóõ ïðîåêöèé òîëüêî ïî ïàðå
àòðèáóòîâ: R X Y4 ( , ), R X Z5 ( , ) , èëè ïðîåêöèé ïî âñåì ïàðàì àòðèáóòîâ:
R X Y4 ( , ), R X Z5 ( , ), R X Z6 ( , ) . Äîêàçàòåëüñòâî íå ïðèâîäèì â ñâÿçè ñ åãî î÷å-
âèäíîñòüþ.
Ïðèìåíÿÿ ñëåäóþùóþ òåîðåìó î øóíòèðîâàíèè ÄÇ (ÌÇ, ÇÏÑ) [1], ïðîåêòè-
ðîâùèê èçáàâëÿåòñÿ îò àíîìàëèé â óêàçàííîì îòíîøåíèè R .
Òåîðåìà 4. Åñëè â îòíîøåíèè R X Y Z( , , ) èìååòñÿ íåòðèâèàëüíàÿ ÄÇ
X Y Z�� // , ïðè÷åì X Y Z, , ìîãóò áûòü ñîñòàâíûìè ìíîæåñòâàìè, ò.å.
X X� { }, Y Y� { }, Z Z� { }, òî ïðè äîáàâëåíèè â ýòî îòíîøåíèå äîïîëíèòåëüíûõ
íåêëþ÷åâûõ àòðèáóòîâ { }A , ïðè÷åì òàê, ÷òî ( )X Y Z A � , çàâèñèìîñòü â îò-
íîøåíèè R X Y Z A( , , , ) ñòàíîâèòñÿ ôóíêöèîíàëüíîé.
Äîêàçàòåëüñòâî ïðèâåäåíî â [1]. Èç íåãî ñëåäóåò, ÷òî åñëè îòíîøåíèå èìååò
ÄÇ (ÌÇ, ÇÏÑ), åå ìîæíî «øóíòèðîâàòü», ò.å. ïåðåêðûòü åå âëèÿíèå äîáàâëåíèåì
íîâîãî ýëåìåíòà — åñòåñòâåííîãî èëè ñóððîãàòíîãî àòðèáóòà, «ôèçè÷åñêèé»
ñìûñë êîòîðîãî — õàðàêòåðèñòèêà ñâÿçè. Ïîýòîìó â äàëüíåéøåì áóäåì íàçûâàòü
äîêàçàííîå â [1] óòâåðæäåíèå «òåîðåìîé î øóíòèðîâàíèè ÄÇ (ÌÇ, ÇÏÑ)», à îòíî-
øåíèÿ ñ «ïåðåêðûòîé» ÄÇ (ÌÇ, ÇÏÑ) — øóíòèðîâàííûìè îòíîøåíèÿ.
Çàìåòèì, îäíàêî, ÷òî àíîìàëèÿ â ïîíèìàíèè Ð. Ôåéäæèíà [17] çàêëþ÷àåòñÿ
â òîì, ÷òî ïîñëå ñîåäèíåíèÿ ïðîåêöèé ïîÿâëÿþòñÿ èçáûòî÷íûå êîðòåæè, ÷òî íà-
çâàíî «ïîòåðåé èíôîðìàöèè». Òåì ñàìûì îáåñïå÷èâàåòñÿ êîððåêòíîñòü ðàáîòû
SQL-çàïðîñà ê ñõåìå ÁÄ, à ïîëüçîâàòåëü ìîòèâèðóåòñÿ äåêîìïîçèðîâàòü îòíîøå-
íèÿ, ìîäåëèðóþùèå ìíîãîàðíûå ñâÿçè ÏðÎ.
 [1] ïðèâåäåí ïðèìåð îòíîøåíèÿ R X Y Z A( , , , ) , â êîòîðîì íèêàêàÿ ÷àñòü íå-
êëþ÷åâîãî àòðèáóòà À íå çàâèñèò íè îò êàêîé êîìáèíàöèè ÷àñòåé êëþ÷à, êðîìå
êàê îò ñàìîãî êëþ÷à, è ñàì êëþ÷ — òàê æå. Ïîëó÷åíà ôîðìà, ïîäîáíàÿ ÍÔÁÊ [19],
íî áåç ÌÇ. Êàê èçâåñòíî [17], ýòî 4ÍÔ (ÍÔ — íîðìàëüíàÿ ôîðìà). Íî â ñèëó
òîãî, ÷òî ïîëó÷åííîå îòíîøåíèå èìååò åäèíñòâåííóþ ÔÇ, ïîëíîñòüþ ïîêðûâàþ-
ùóþ âåñü êîðòåæ ýòîãî îòíîøåíèÿ, îïåðàöèÿ ïðîåêöèè íàä íèì íå âûïîëíèìà.
Çíà÷èò, â îòíîøåíèè R X Y Z A( , , , ) îòñóòñòâóåò òàêæå è ÇÏÑ [5]. Ïîýòîìó ïîëó-
÷åííîå îòíîøåíèå îòíîñèòñÿ ê 5ÍÔ. À òîò ôàêò, ÷òî ñîâîêóïíîñòü øóíòèðîâàííûõ
5ÍÔ-îòíîøåíèé, ñôîðìèðîâàííàÿ íà ðåëÿöèîííîì êàðêàñå è ìîäåëèðóþùàÿ íåêóþ
ÏðÎ, ïðè îïðåäåëåííûõ îãðàíè÷åíèÿõ îòíîñèòñÿ ê ÄÊÍÔ [5], ïîêàçàí íèæå.
Òàêèì îáðàçîì, èñõîäÿ èç êîíöåïöèè ìîäåëèðîâàíèÿ âñåãî ðàçíîîáðàçèÿ è
ñòàòè÷åñêèõ, îñîáåííî äèíàìè÷åñêèõ ñâÿçåé ìåæäó àòîìàðíûìè ñóùíîñòÿìè-îáú-
åêòàìè â ÏðÎ ïîñðåäñòâîì ëèøü çàïðîñîâ ïîëüçîâàòåëåé, à íå ïóòåì õðàíåíèÿ
â æåñòêîé ïàìÿòè ìàêñèìàëüíî âîçìîæíîãî ÷èñëà àòðèáóòîâ òàêèõ ñâÿçåé, ïðîåê-
òèðîâùèê âûíóæäåí ïîëüçîâàòüñÿ èñêëþ÷èòåëüíî áèíàðíûìè îòíîøåíèÿìè
(ê ýòîìó, ïî ñóòè, è ïðèâîäèò ìåõàíèçì çàïðîñîâ).
Ïðîòèâîïîëîæíàÿ êîíöåïöèÿ ïîçâîëÿåò ïðîåêòèðîâùèêó ìèíèìèçèðîâàòü è
ëèñòèíãè áóäóùèõ çàïðîñîâ ïîëüçîâàòåëåé, è ëèñòèíã ïðèëîæåíèé; è, ñïðîåêòè-
ðîâàâ ìàêñèìàëüíî âîçìîæíîå ÷èñëî ìîäåëåé ñâÿçåé, çàðàíåå ïðåäóñìîòðåòü
áîëüøèíñòâî çàïðîñîâ. À ñîîòâåòñòâóþùèå äàííûå, ïîñêîëüêó îíè ÿâëÿþòñÿ
çíà÷åíèÿìè àòðèáóòîâ ýòèõ ñâÿçåé, õðàíèòü â ñîîòâåòñòâóþùèõ øóíòèðîâàííûõ,
ò.å. âûñîêîíîðìàëèçîâàííûõ îòíîøåíèÿõ, â æåñòêîé ïàìÿòè è ðåãóëÿðíî èñïîëü-
çîâàòü èõ êàê äëÿ OLTP-, òàê è äëÿ OLAP-ïîòðåáíîñòåé îäíîâðåìåííî.
Ýòî îçíà÷àåò, ÷òî àíîìàëèÿ «ïîòåðè èíôîðìàöèè» [5,17] â ðåçóëüòèðóþùèõ
îòíîøåíèÿõ, êîòîðûå ïîñòðîåíû íà îáîáùåíèÿõ ÄÇ, — íå ÷òî èíîå, êàê ðåçóëü-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 179
òàò íåêîððåêòíûõ ñîåäèíåíèé ïðè âûïîëíåíèè çàïðîñîâ ïîëüçîâàòåëåé. Íî èñ-
ïîëüçîâàíèå òàêèõ ñîåäèíåíèé ìîæåò áûòü ìèíèìèçèðîâàíî. È êàê ïîêàçàíî
íèæå, àíîìàëèè âñòàâêè è óäàëåíèÿ â ñîâîêóïíîñòè îòíîøåíèé–ñâÿçåé è îòíî-
øåíèé–ñóùíîñòåé íå âîçíèêàþò ëèøü ïðè îïðåäåëåííûõ îãðàíè÷åíèÿõ. Ýòî çíà-
÷èòåëüíî óòî÷íÿåò âûâîäû ñåðèè ðàáîò àâòîðà [4].
ÒÅÎÐÈß ÊÀÐÊÀÑÍÎÉ ÌÎÄÅËÈ ÄÀÍÍÛÕ
 [1] äàíî îïðåäåëåíèå ðåëÿöèîííîãî êàðêàñà êàê ñîâîêóïíîñòè îòíîøåíèé,
ïîëó÷åííûõ ñî÷åòàíèåì äåêàðòîâûõ ïðîèçâåäåíèé óíàðíûõ êëþ÷åâûõ àòðèáó-
òîâ ñîâîêóïíîñòè ñóùíîñòåé-îáúåêòîâ ìîäåëèðóåìîé ÏðÎ. Âûïèøåì èç [1]
áåç äîêàçàòåëüñòâ îñíîâíûå òåîðåìû êàðêàñíîé ìîäåëè äàííûõ.
Òåîðåìà 5 (î ïîëíîòå è åäèíñòâåííîñòè ðåëÿöèîííîãî êàðêàñà). Ñîâî-
êóïíîñòü îòíîøåíèé, ïîðîæäàåìàÿ ñî÷åòàíèåì äåêàðòîâûõ ïðîèçâåäåíèé êîíå÷-
íîãî ìíîæåñòâà àòîìàðíûõ àòðèáóòîâ ñóùíîñòåé-îáúåêòîâ, íàçûâàåìàÿ ðåëÿöè-
îííûì êàðêàñîì, åäèíñòâåííà è ïîëíà.
Åäèíñòâåííîñòü è ïîëíîòà òàêîé ñîâîêóïíîñòè îòíîøåíèé óêàçûâàåò íà èñ-
êëþ÷èòåëüíîå ïîëîæåíèå ðåëÿöèîííîãî êàðêàñà â ïðîöåññå ðàçðàáîòêè ñõåìû
ÁÄ. Äåéñòâèòåëüíî, ëþáîå îòíîøåíèå íà çàäàííîì ìíîæåñòâå àòðèáóòîâ ïðè-
íàäëåæèò êàðêàñó. Áîëåå òîãî, ðåçóëüòàò îïåðàöèé íàä ýëåìåíòàìè êàðêàñà òàêæå
áóäåò ýëåìåíòîì êàðêàñà. Ýòî ñâîéñòâî çàìêíóòîñòè íåïîñðåäñòâåííî ñëåäóåò èç
ñâîéñòâà ïîëíîòû, ïîýòîìó êàðêàñ ÿâëÿåòñÿ âïîëíå åñòåñòâåííûì (õîòÿ è ôîð-
ìàëüíûì) êîìïîíåíòîì ïðè ïîñòðîåíèè óíèôèöèðîâàííîãî àëãîðèòìà ñèíòåçà
ñõåì ÁÄ.
Îòìåòèì, ÷òî ñàì êàðêàñ êàê ñòðóêòóðèðîâàííàÿ ñîâîêóïíîñòü âñåõ âîçìîæ-
íûõ ìíîæåñòâ àòðèáóòîâ (êàê óæå óïîìèíàëîñü, â àëãåáðàè÷åñêîì ñìûñëå êàðêàñ
ÿâëÿåòñÿ áóëåàíîì ñâÿçåé ñóùíîñòåé-îáúåêòîâ) ïðåäåëüíî èçáûòî÷åí. Ïîýòîìó
äëÿ åãî ýôôåêòèâíîãî èñïîëüçîâàíèÿ íåîáõîäèì èíñòðóìåíòàðèé «íàâèãàöèè ïî
êàðêàñó», ïðåîáðàçîâàíèé, ðåäóêöèé, ëîêàëèçàöèé è îïåðèðîâàíèÿ â öåëîì. Îäíà-
êî àêòóàëèçàöèÿ ÿ÷ååê êàðêàñà, ò.å. øóíòèðîâàíèå ÄÇ, ïîçâîëÿåò èñïîëüçîâàòü ñî-
âîêóïíîñòü àêòóàëèçèðîâàííûõ ÿ÷ååê êàðêàñà êàê íåïîñðåäñòâåííóþ ñõåìó ÁÄ.
Òåîðåìà 6 (î çàìêíóòîñòè ïóòåé íîðìàëèçàöèè). Äëÿ çàäàííîãî ìíîæåñ-
òâà óíàðíûõ êëþ÷åâûõ àòðèáóòîâ K ñóùíîñòåé-îáúåêòîâ è ñîâîêóïíîñòè { }�k
çàâèñèìîñòåé ìåæäó àòðèáóòàìè â ýêçåìïëÿðàõ [ ]Ck êàðêàñà îòíîøåíèé ñóùåñò-
âóåò ïóòü íîðìàëèçàöèè D D k( ) ( )0
� �� , ðåøåíèå êîòîðîãî íàõîäèòñÿ â òðåáó-
åìîé ÍÔ max { }�k èç ñîâîêóïíîñòè K . Ýòî óòâåðæäåíèå íåïîñðåäñòâåííî ñëå-
äóåò èç ïîëíîòû êàðêàñà îòíîøåíèé è ñõåìû ÁÄ.
Êàê óêàçûâàëîñü ðàíåå, äëÿ ïðîåêòèðîâùèêà âàæíà ìîäèôèöèðóåìîñòü ëî-
ãè÷åñêèõ ñõåì ÁÄ ïðè èçìåíåíèè ÏðÎ, íàïðèìåð, ïðè äîáàâëåíèè íîâûõ ñóù-
íîñòåé-îáúåêòîâ (íî íå èõ ýêçåìïëÿðîâ) èëè óäàëåíèè ñóùåñòâóþùèõ, ÷òî âñòðå-
÷àåòñÿ ðåæå. Äëÿ èññëåäîâàíèÿ ýòîãî ñâîéñòâà ðåëÿöèîííîãî êàðêàñà â [20] ââå-
äåíî ïîíÿòèå ñåìàíòè÷åñêèé àòîì. Ïîä ñåìàíòè÷åñêèì àòîìîì, èëè ïðîñòî
àòîìîì A i jx( ) ïîíèìàåì âñÿêèé ôàêò â ÁÄ, ñïðàâåäëèâûé äëÿ àòîìàðíîãî ïðåäè-
êàòà, ò.å. A j
n
i A i jP x x( ( ) )� �1. Çäåñü èíäåêñ i â îáîçíà÷åíèè ñåìàíòè÷åñêîãî
àòîìà — ýòî ãëîáàëüíûé (âçÿò ïî âñåé ÏðÎ) èäåíòèôèêàòîð àðãóìåíòà, à èíäåêñ
j — èäåíòèôèêàòîð ïðåäèêàòà. Íà ÿçûêå ðåëÿöèîííûõ ñõåì ñåìàíòè÷åñêèé àòîì
åñòü íå ÷òî èíîå, êàê îòäåëüíûé êîðòåæ â îòíîøåíèè, ýêâèâàëåíòíîì àòîìàðíî-
ìó ïðåäèêàòó. Àòîìû A i jx( ) êàæäîãî j-ïðåäèêàòà A j
n
iP x( ) óäîáíî ïðîèíäåê-
ñèðîâàòü; ñîîòâåòñòâóþùèé èíäåêñ A j� ÿâëÿåòñÿ êëþ÷îì ñåìàíòè÷åñêîãî àòîìà
(äàëåå � j âìåñòî A j� ). Íà ÿçûêå ðåëÿöèîííûõ ñõåì ýòî îçíà÷àåò ââåäåíèå ÔÇ
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
( )� � xi j , ÷òî ýôôåêòèâíåå, ïîñêîëüêó êëþ÷ ñåìàíòè÷åñêîãî àòîìà ÿâëÿåòñÿ
óíàðíûì (ïðèíèìàþùèì öåëûå ïîëîæèòåëüíûå çíà÷åíèÿ), à êëþ÷ ñîîòâåòñòâóþ-
ùåãî àòîìàðíîãî ïðåäèêàòà A j
n
iP x( ) — ñòðîãî n-àðíûì (ïðè÷åì íå âñåãäà ÷èñ-
ëîâûì)
Ââåäåì âàæíîå óòî÷íåíèå ê îïðåäåëåíèþ ñåìàíòè÷åñêè àòîìàðíîãî ïðåäè-
êàòà: ïðåäèêàò áóäåò àòîìàðíûì òîãäà, êîãäà íèêàêèå ïîäìíîæåñòâà åãî àðãó-
ìåíòîâ íå ôèãóðèðóþò íè â êàêèõ çàâèñèìîñòÿõ: êàê îäíî ñ äðóãèì, òàê è ñ ïîä-
ìíîæåñòâàìè àðãóìåíòîâ äðóãèõ ïðåäèêàòîâ (ïðàâèëî âçàèìíîé ñåìàíòè÷åñêîé
àòîìàðíîñòè). Â ýòîì êîíòåêñòå âàæíà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 7 (îá óñòîé÷èâîñòè ðåëÿöèîííîãî êàðêàñà ê ìîäèôèêàöèè).
Åñëè âûïîëíÿåòñÿ ïðàâèëî âçàèìíîé ñåìàíòè÷åñêîé àòîìàðíîñòè, òî èçìåíåíèå
áàçîâîãî ìíîæåñòâà àòîìàðíûõ ïðåäèêàòîâ íà åäèíèöó íå âëèÿåò íà èñõîäíóþ
ñõåìó ðåëÿöèîííîãî êàðêàñà.
Ïðèíöèïèàëüíîå îòëè÷èå ðåëÿöèîííîãî êàðêàñà, ñèíòåçèðóåìîãî íà ñåìàí-
òè÷åñêè àòîìàðíûõ ïðåäèêàòàõ, îò ìíîæåñòâà ñóùåñòâóþùèõ êîíöåïöèé îðãàíè-
çàöèè äàííûõ (â êîòîðûõ òðàäèöèîííî ôîðìèðóåòñÿ ñîâîêóïíîñòü ñóùíîñ-
òåé-îáúåêòîâ ñ ïðèñóùèìè èì àòðèáóòàìè, çàòåì äëÿ íèõ îïðåäåëÿåòñÿ ìíîæåñ-
òâî îòíîøåíèé-ñâÿçåé, ïîñëå ÷åãî çàäàåòñÿ íåêîòîðàÿ «íà÷àëüíàÿ» ñõåìà ÁÄ,
àíîìàëèè êîòîðîé óñòðàíÿþòñÿ ïóòåì äåêîìïîçèöèè), çàêëþ÷àåòñÿ â òîì, ÷òî
äëÿ ðåëÿöèîííîãî êàðêàñà ïðåæäå âñåãî ôîðìèðóåòñÿ ÏðÎ (êàê ìíîæåñòâî àðãó-
ìåíòîâ ïðåäèêàòîâ) è çàäàåòñÿ åå ñåìàíòèêà (êàê ìíîæåñòâî çàâèñèìîñòåé ìåæäó
ýòèìè àðãóìåíòàìè).
Íà ýòîé îñíîâå îïðåäåëÿåòñÿ ìíîæåñòâî ñåìàíòè÷åñêè àòîìàðíûõ ïðåäèêà-
òîâ. Ðåëÿöèîííûé êàðêàñ, ñèíòåçèðóåìûé (åäèíñòâåííûì îáðàçîì) íà áàçîâîì
ìíîæåñòâå àòîìàðíûõ ïðåäèêàòîâ, âûñòóïàåò â êà÷åñòâå «íîñèòåëÿ» äàííûõ î
ôàêòàõ ÏðÎ. Òàêîå ñâîéñòâî êàðêàñà, êàê åãî ïîëíîòà, ãàðàíòèðóåò, ÷òî âñå (àêòó-
àëüíûå è ïîòåíöèàëüíûå) îòíîøåíèÿ ìåæäó ïàðàìè, òðîéêàìè, ÷åòâåðêàìè è ò.ä.
àòîìàðíûõ ïðåäèêàòîâ ìîæíî åäèíîîáðàçíî îïèñàòü â ðàìêàõ îäíîé ñîâîêóïíîñ-
òè — ðåëÿöèîííîãî êàðêàñà. À òàêàÿ óñòîé÷èâîñòü êàðêàñà ê ìîäèôèêàöèÿì áà-
çîâîãî ìíîæåñòâà àòîìàðíûõ ïðåäèêàòîâ ãàðàíòèðóåò, ÷òî ïðè èçìåíåíèè ÏðÎ
(äîáàâëåíèè íîâûõ àòîìàðíûõ ïðåäèêàòîâ èëè óñòðàíåíèè ñóùåñòâóþùèõ) íå
âîçíèêíåò ïîòðåáíîñòü â òîòàëüíîé ðåîðãàíèçàöèè âñåé ñîâîêóïíîñòè. Ïîýòîìó
ñåìàíòè÷åñêè àòîìàðíûå ïðåäèêàòû èãðàþò ðîëü îïòèìàëüíûõ «ñóùíîñòåé-îáú-
åêòîâ» äëÿ ïðåäñòàâëåíèÿ äàííûõ èç ÏðÎ, à ñàì ðåëÿöèîííûé êàðêàñ ÿâëÿåòñÿ
îïòèìàëüíûì «íîñèòåëåì» äàííûõ î âçàèìîñâÿçÿõ ìåæäó ýòèìè ñóùíîñòÿìè-
îáúåêòàìè.
Íà ðèñ. 1 ïîêàçàíà îáùàÿ ñõåìà ðåëÿöèîííîãî êëþ÷åâîãî êàðêàñà. Î÷åâèä-
íî, â êîíòåêñòå êîíêðåòíûõ ñõåì ÁÄ áîëüøèíñòâî îòíîøåíèé íåàêòóàëüíû, íî
èõ àêòóàëèçàöèÿ, ïî ñóòè, ìîäèôèöèðóåò ýòè ñõåìû ÁÄ. Îòñþäà ñëåäóåò, ÷òî ìî-
äèôèêàöèÿ ñõåìû ÁÄ ñâîäèòñÿ ê äâóì òèïàì îïåðàöèé: àêòóàëèçàöèÿ–àííóëèðî-
âàíèå îòíîøåíèÿ è àêòóàëèçàöèÿ–àííóëèðîâàíèå ïðîèçâîëüíîãî ìíîæåñòâà íå-
êëþ÷åâûõ àòðèáóòîâ â ïðîèçâîëüíîé ãðóïïå îòíîøåíèé. Ïðè ýòîì öåëîñòíîñòü
ÁÄ ñâîäèòñÿ, ïðåæäå âñåãî, ê óíèêàëüíîñòè ñîâîêóïíîñòè êëþ÷åâûõ àòðèáóòîâ è
èõ ñòðîãîãî ñîîòâåòñòâèÿ â ëîãè÷åñêè ñâÿçàííûõ îòíîøåíèÿõ. Ïðèñâîèâ ãðóïïå
îòíîøåíèé ñòàòóñ íåàêòóàëüíûõ, ïðîåêòèðîâùèê ñíèæàåò êîëè÷åñòâî
èñïîëüçóåìûõ îòíîøåíèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 181
ÄÎÌÅÍÍÎ-ÊËÞ×ÅÂÀß ÑÕÅÌÀ ÁÄ
Ïî àíàëîãèè ñ [5] ââåäåì ïîíÿòèå îãðàíè÷åíèÿ ñõåìû îòíîøåíèÿ. Z-îãðàíè÷å-
íèåì (èëè ïðîñòî îãðàíè÷åíèåì, åñëè ïîäðàçóìåâàåòñÿ ñîâîêóïíîñòü Z îòíî-
øåíèé) áóäåì íàçûâàòü îòîáðàæåíèå íàáîðà âñåõ Z-îòíîøåíèé íà äîìåí {true,
false}. Òàêèå îãðàíè÷åíèÿ íà îòíîøåíèÿ ââîäÿòñÿ, êàê ïðàâèëî, ñ ïîìîùüþ
âûñêàçûâàíèé, íàïèñàííûõ íà çàäàííîì ÿçûêå, — èñ÷èñëåíèå ïðåäèêàòîâ ïåð-
âîãî ïîðÿäêà. Íà ýòè îãðàíè÷åíèÿ ìîãóò áûòü íàëîæåíû åùå è äîïîëíèòåëü-
íûå îãðàíè÷åíèÿ.
Áóäåì ãîâîðèòü, ÷òî îòíîøåíèå R óäîâëåòâîðÿåò îãðàíè÷åíèþ g, èëè, ÷òî g
ñîäåðæèòñÿ â R, åñëè ïîñëå ýòîãî îòîáðàæåíèÿ îòíîøåíèå R ïðèíèìàåò çíà÷åíèå
true. Èíà÷å ìû ãîâîðèì, ÷òî g ëîæíî (false) â R . Ê îãðàíè÷åíèÿì îòíîñÿò òðàäè-
öèîííûå çàâèñèìîñòè — ÔÇ, ÄÇ, ÌÇ, ÇÏÑ, à òàêæå ââåäåííûå â [5] çàâèñèìîñòè
äîìåíà — DD è çàâèñèìîñòè êëþ÷à — KD.
Ïóñòü Õ — íàáîð àòðèáóòîâ, g — åäèíñòâåííîå îãðàíè÷åíèå è G — íàáîð
îãðàíè÷åíèé (èëè åäèíñòâåííîå îãðàíè÷åíèå). Òîãäà î÷åâèäíî, ÷òî G ëîãè÷åñêè
âêëþ÷àåò g (â êîíòåêñòå Õ ), èëè, ÷òî g — ëîãè÷åñêîå ñëåäñòâèå G (â êîíòåêñòå Õ ).
Ñòðîãî ýòî îçíà÷àåò, ÷òî âñÿêèé ðàç, êîãäà G ñîäåðæèòñÿ â îòíîøåíèè ñ àòðèáóòàìè
X , òî è g ÿâëÿåòñÿ òàêîâûì. Áóäåì îáîçíà÷àòü ýòîò ôàêò êàê îáû÷íîå ñëåäñòâèå
G g
, åñëè êîíòåêñò Õ ïîäðàçóìåâàåòñÿ, íàïðèìåð, { }A B B C A C� �
�, .
Êàê è â [5], çàâèñèìîñòü äîìåíà áóäåì îáîçíà÷àòü IN ,( )A S , ãäå A — àòðè-
áóò è S — ìíîæåñòâî. Ýòî îçíà÷àåò, ÷òî äëÿ êàæäîãî êîðòåæà çíà÷åíèå àòðèáóòà
A äîëæíî ïðèíàäëåæàòü S .
Çàâèñèìîñòü êëþ÷à KEY( )K , ãäå K — ìíîæåñòâî àòðèáóòîâ, îçíà÷àåò, ÷òî K
ÿâëÿåòñÿ êëþ÷îì (key), ò.å. ÷òî â îòíîøåíèè íåò äâóõ êîðòåæåé, äëÿ êîòîðûõ çíà-
÷åíèÿ K îäèíàêîâû.
Ñ ïîíÿòèåì îãðàíè÷åíèÿ ðåëÿöèîííîé ñõåìû ñâÿçàíî è ïîíÿòèå âûïîëíè-
ìîñòè ðåëÿöèîííîé ñõåìû [5]. Ñõåìà âûïîëíèìà, åñëè äëÿ íåå íàéäåòñÿ õîòÿ áû
îäèí äîïóñòèìûé ýêçåìïëÿð ñõåìû è íàáîð åå îãðàíè÷åíèé íåïðîòèâîðå÷èâ.
Òåïåðü ïî àíàëîãèè ñ [5] ââåäåì îïðåäåëåíèå ÄÊÍÔ.
Îïðåäåëåíèå ÄÊÍÔ [5]. Ïóñòü R— ðåëÿöèîííàÿ ñõåìà, íàõîäÿùàÿñÿ â 1ÍÔ,
ïóñòü G — íàáîð çàâèñèìîñòåé DD KD( ) ( )R R� ñõåìû. R íàõîäèòñÿ â ÄÊÍÔ,
åñëè G g
äëÿ ëþáîãî îãðàíè÷åíèÿ g ñõåìû R.
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Áàçîâàÿ ñîâîêóïíîñòü
N ñóùíîñòåé-îáúåêòîâ
X1 X2 X3 X4 XN
…
Ïîëíàÿ ñîâîêóïíîñòü
áèíàðíûõ ñâÿçåé
X1, X2 X1, X3 …
X1, XN X2, X3 …
X3, XN XN�1, XN
Ïîëíàÿ ñîâîêóïíîñòü
òåðíàðíûõ ñâÿçåé
X1, X2, X3
…
X1, X3, X4
…
X1, XN�1, XN X2, XN�1, XN
…
XN�2, XN�1, XN
Ïîëíàÿ ñîâîêóïíîñòü
êâàðòàðíûõ ñâÿçåé
X1, X2, X3, X4 X1, XN�2, XN�1, XN
…
X2, XN�2, XN�1, XN
…
XN�3, XN�2, XN�1, XN
…
Åäèíñòâåííàÿ
N-àðíàÿ ñâÿçü
…
X1, X2, X3,…, XN�2, XN�1, XN
Ðèñ. 1. Ðåëÿöèîííûé êëþ÷åâîé êàðêàñ äëÿ N ñóùíîñòåé-îáúåêòîâ
Âûïèøåì èç [5] îñíîâíóþ òåîðåìó î ÄÊÍÔ. Îíà áóäåò áàçîâîé äëÿ äàëü-
íåéøèõ âûêëàäîê.
Òåîðåìà 8 (òåîðåìà Ôåéäæèíà î ÄÊÍÔ). Âûïîëíèìàÿ 1ÍÔ-ðåëÿöèîííàÿ
ñõåìà íàõîäèòñÿ â ÄÊÍÔ òîãäà è òîëüêî òîãäà, êîãäà â íåé íåò àíîìàëèé âñòàâêè
èëè óäàëåíèÿ.
Ñ ó÷åòîì ýòîãî óòâåðæäåíèÿ, äîêàçàííîãî â [5], ðàññìîòðèì îñîáîå îòíîøå-
íèå ñî ñõåìîé R X A( ), , íàçâàííîå òàê â [1]. Ïðè ýòîì ïî àíàëîãèè ñ [1] íàçîâåì
òàêæå îñîáûìè ñëåäóþùèå îãðàíè÷åíèÿ ýòîé ñõåìû:
DD IN const IN const
KD KE
( ) ( , ( )) ( , ( )),
( )
R A A A X X X
R
� � � � �
�
�
Y( ) .X X A
�
Òàêèì îáðàçîì, îñîáûå îãðàíè÷åíèÿ — ýòî òàêàÿ ñîâîêóïíîñòü, â êîòîðîé îãðà-
íè÷åíèÿ íà äîìåíû: ëþáûå çíà÷åíèÿ àòðèáóòîâ X è A, íå ÿâëÿþùèåñÿ êîíñòàíòîé
(è â òîì ÷èñëå ïóñòûì ìíîæåñòâîì), îãðàíè÷åíèÿ íà êëþ÷è: X — åäèíñòâåííûé
êëþ÷ îòíîøåíèÿ, à äîïîëíèòåëüíûå îãðàíè÷åíèÿ: íàëè÷èå ÔÇ X A� — ýòî åñòåñò-
âåííîå ñëåäñòâèå èç îãðàíè÷åíèÿ êëþ÷à.
Îòìåòèì, ÷òî ëþáîå îòíîøåíèå ñî ñõåìîé R X X X A A Ai i j( , , , , , , , )1 2 1 2� � ,
ãäå ( ) ( )X X X A A Ai j1 2 1 2 � � � , íà îñíîâàíèè àêñèîì Àðìñòðîí-
ãà [18] ìîæåò áûòü çàìåíåíî ðàâíîñèëüíûì îòíîøåíèåì ñî ñõåìîé R X Ai
* ( , ) è åäè-
íñòâåííîé ÔÇ X A� , ãäå X X X X i� ( )1 2 � , à A A A A j� ( )1 2 � .
Ñôîðìóëèðóåì ýòî óòâåðæäåíèå â âèäå ñëåäóþùåé ëåììû.
Ëåììà 3. Âûïîëíèìîå îòíîøåíèå ñî ñõåìîé R X X X A A Ai i j( , , , , , , , )1 2 1 2� �
è îãðàíè÷åíèÿìè ( )X X X i1 2 � — åäèíñòâåííûé êëþ÷ îòíîøåíèÿ è îãðà-
íè÷åíèÿ íà äîìåíû — ñòðîãî ñîîòâåòñòâóþò îãðàíè÷åíèÿì íà äîìåíû â îñîáûõ
îãðàíè÷åíèÿõ, ìîæåò áûòü çàìåíåíî îòíîøåíèåì ñ îñîáîé ñõåìîé R X Ai
* ( , ) , ãäå
X X X X i� ( )1 2 � è A A A A j� ( )1 2 � , òîãäà è òîëüêî òîãäà, êîãäà
ëþáàÿ ñîâîêóïíîñòü ÔÇ èñõîäíîé ñõåìû ÿâëÿåòñÿ ñëåäñòâèåì êëþ÷à.
Íåîáõîäèìîñòü. Ïóñòü â ñõåìå R X X X A A Ai i j( , , , , , , , )1 2 1 2� � èìååòñÿ
åäèíñòâåííûé êëþ÷ ( )X X X i1 2 � . Òîãäà ñëåäñòâèåì êëþ÷à â îòíîøåíèè
èìååòñÿ ÔÇ ( ) ( )X X X A A Ai j1 2 1 2 � � � . Èç ýòîãî ñëåäóåò, ÷òî âîç-
ìîæíûå îñòàâøèåñÿ ÔÇ èìåþò ñâîèìè äåòåðìèíàíòàìè òîëüêî ÷àñòè êëþ÷à X i .
Äåéñòâèòåëüíî, â äàííîé ñõåìå îòñóòñòâóþò ëþáûå ÔÇ ñ ñîñòàâíûì äåòåðìèíàí-
òîì íà ïðîèçâîëüíîé ñîâîêóïíîñòè A j èç íåêëþ÷åâûõ àòðèáóòîâ, â ïðîòèâíîì
ñëó÷àå â ñõåìå áûë áû íå îäèí êëþ÷. Ïîêàæåì, ÷òî ýòè ÔÇ ÿâëÿþòñÿ ñëåäñòâèåì
êëþ÷à, ò.å. ìîãóò áûòü âûâåäåíû èç «êëþ÷åâîé» ÔÇ. Ïóñòü â ñõåìå
R X X X A A Ai i j( , , , , , , , )1 2 1 2� � èìååòñÿ ìíîæåñòâî ÔÇ X Xm k� . Òîãäà íà
îñíîâàíèè àêñèîìû Àðìñòðîíãà î ïîïîëíåíèè ìîæåì çàìåíèòü ëþáóþ ïðîèç-
âîëüíóþ ÔÇ X Xm k� íà ( ) ( )X X X X X Xm k � 1 2 1 2� � , ÷òî ïî
àêñèîìå î ñàìîäåòåðìèíèðîâàííîñòè áóäåò ñâåäåíî ê ( )X X X i1 2 ��
� ( )X X X i1 2 � , ò.å. ê êëþ÷ó.
Äîñòàòî÷íîñòü. Ïóñòü â ñõåìå R X X X A A Ai i j( , , , , , , , )1 2 1 2� � èìååòñÿ
ìíîæåñòâî ÔÇ X Xm k� , êîòîðûå íå ÿâëÿþòñÿ ñëåäñòâèåì êëþ÷à. Ýòî îçíà÷àåò,
÷òî èõ íåâîçìîæíî âûâåñòè èç ñîâîêóïíîñòè ( )X X X i1 2 � . Íî òîãäà â ñî-
âîêóïíîñòè äåòåðìèíàíòà X m íàõîäÿòñÿ åùå è íåêëþ÷åâûå àòðèáóòû: ýòî îçíà-
÷àåò, ÷òî èìååòñÿ åùå îäèí êëþ÷. Ïðîòèâîðå÷èå äîêàçûâàåò äîñòàòî÷íîñòü.
Òîãäà ñïðàâåäëèâî åùå îäíî ïðîñòîå, íî âàæíîå ñâîéñòâî êàðêàñíîãî îòíî-
øåíèÿ.
Ëåììà 4. Â âûïîëíèìîì êàðêàñíîì îòíîøåíèè ñî ñõåìîé R X X Xi i( , , , )1 2 � ,
ïîëó÷åííîì äåêàðòîâûì ïðîèçâåäåíèåì àòðèáóòîâ X X X i1 2, , ,� (îïåðàòîðîì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 183
ðîñòà [1]), ñ îãðàíè÷åíèÿìè: ( )X X X i1 2 � — åäèíñòâåííûé êëþ÷ îòíîøå-
íèÿ è îãðàíè÷åíèÿ íà äîìåíû, ñîîòâåòñòâóþò îãðàíè÷åíèÿì íà äîìåíû â îñîáûõ
îãðàíè÷åíèÿõ, ëþáàÿ ñîâîêóïíîñòü ÔÇ ÿâëÿåòñÿ ñëåäñòâèåì êëþ÷à.
Äîêàçàòåëüñòâà íå ïðèâîäèì â ñâÿçè ñ åãî î÷åâèäíîñòüþ.
Ýòî çíà÷èò, ÷òî â ñõåìå øóíòèðîâàííîãî îòíîøåíèÿ R X X Xi i( , , , ,1 2 �
A A A j1 2, , , )� ëþáàÿ ñîâîêóïíîñòü ÔÇ íà ÷àñòÿõ åäèíñòâåííîãî êëþ÷à êàê íà äå-
òåðìèíàíòàõ, ïðè÷åì òàê, ÷òî â ýòèõ çàâèñèìîñòÿõ íå ó÷àñòâóåò íè îäèí èç íå-
êëþ÷åâûõ àòðèáóòîâ ( , , , )A A A j1 2 � , íå ïðîòèâîðå÷èò îãðàíè÷åíèÿì êëþ÷à. Ýòî
î÷åíü âàæíî äëÿ ïðîåêòèðîâùèêà, òàê êàê îçíà÷àåò, ÷òî òàêàÿ çàìåíà áóäåò àäåê-
âàòíîé äëÿ ðàçíûõ ñîâîêóïíîñòåé ÔÇ, êîòîðûìè îáëàäàþò ñîñòàâíûå êëþ÷è ïðè
øóíòèðîâàíèè îáîáùåíèé ÄÇ. Ýòî óòâåðæäåíèå îáîñíîâûâàåò àäåêâàòíîñòü ìî-
äåëèðîâàíèÿ ìíîãîàðíîé ñâÿçè (ñ àòðèáóòàìè) ìåæäó ìíîæåñòâîì àòîìàðíûõ
ñóùíîñòåé îòíîøåíèåì ñî ñõåìîé, àíàëîãè÷íîé ñõåìå îòíîøåíèÿ, ìîäåëèðóþùå-
ãî åäèíñòâåííóþ àòîìàðíóþ ñóùíîñòü, è ïîëíîñòüþ ïîäòâåðæäàåò èäåþ ×åíà [9]
î ðàâíîñèëüíîñòè ñóùíîñòåé è ñâÿçåé.
Ñôîðìóëèðóåì íåñêîëüêî óòâåðæäåíèé, êîòîðûå íåïîñðåäñòâåííî ñëåäóþò
èç òåîðåìû Ôåéäæèíà î ÄÊÍÔ. Ïðè ýòîì ôîðìàëüíî ïðèâåäåì äîêàçàòåëüñòâà
ýòèõ óòâåðæäåíèé, íå ñìîòðÿ íà èõ î÷åâèäíîñòü.
Èìååò ìåñòî ñëåäóþùàÿ ëåììà.
Ëåììà 5. Âûïîëíèìàÿ ðåëÿöèîííàÿ ñõåìà R X A( , ) íå èìååò àíîìàëèé
âñòàâêè èëè óäàëåíèÿ òîãäà è òîëüêî òîãäà, êîãäà â íåé îòñóòñòâóþò îãðàíè÷å-
íèÿ, êîòîðûå íå ñëåäóþò èç îñîáûõ îãðàíè÷åíèé.
Äîñòàòî÷íîñòü. Ïðåäïîëîæèì, ÷òî â R X A( , ) íå ñîäåðæèòñÿ îãðàíè÷åíèé,
êîòîðûå ëîãè÷åñêè íå ñëåäóþò èç îñîáûõ. Ýòî îçíà÷àåò, ÷òî â ñõåìå R X A( , ) ñó-
ùåñòâóþò òîëüêî îãðàíè÷åíèÿ, êîòîðûå ñòðîãî ñëåäóþò èç îãðàíè÷åíèé íà äîìå-
íû è êëþ÷è. Ïîêàæåì, ÷òî R X A( , ) íå èìååò àíîìàëèé âñòàâêè èëè óäàëåíèÿ.
Ïóñòü r1 — äîïóñòèìûé ýêçåìïëÿð ñõåìû R X A( , ) . Ìû äîëæíû ïîêàçàòü, ÷òî îò-
íîøåíèå r2 , êîòîðîå ïîëó÷åíî èç R X A( , ) èëè âñòàâêîé êîðòåæà, ñîâìåñòèìîãî ñ
R X A( , ), èëè óäàëåíèåì êîðòåæà èç R X A( , ), ÿâëÿåòñÿ òàêæå äîïóñòèìûì ýêçåì-
ïëÿðîì. Ïóñòü G — íàáîð çàâèñèìîñòåé ñõåìû R X A( , ) , G DD R KD R� ( ) ( )� .
Ëåãêî ïðîâåðèòü, ÷òî òàê êàê R X A( , ) óäîâëåòâîðÿåò óñëîâèÿì G, òî è r1 óäîâëåòâî-
ðÿåò óñëîâèÿì G. ×òîáû ïîêàçàòü, ÷òî r2 ÿâëÿåòñÿ äîïóñòèìûì ýêçåìïëÿðîì
R X A( , ) , íóæíî ïîêàçàòü, ÷òî r2 óäîâëåòâîðÿåò òàêæå è êàæäîìó èç îãðàíè÷åíèé g.
Íî g — ýòî åäèíñòâåííàÿ ÔÇ X A� , êîòîðàÿ ÿâëÿåòñÿ åñòåñòâåííûì ñëåäñòâèåì
îãðàíè÷åíèé íà êëþ÷è KD R( ) îòíîøåíèÿ R X A( , ), ò.å. â îòíîøåíèè îòñóòñòâóþò
îãðàíè÷åíèÿ, êîòîðûå íå ñëåäóþò èç G. Çíà÷èò, ïî îïðåäåëåíèþ R X A( , ) íàõî-
äèòñÿ â ÄÊÍÔ. Ñëåäîâàòåëüíî, ïîñêîëüêó r1 óäîâëåòâîðÿåò G è G g
, òî r2
óäîâëåòâîðÿåò g, ÷òî è òðåáîâàëîñü äîêàçàòü.
Íåîáõîäèìîñòü. Òåïåðü ïðåäïîëîæèì, ÷òî â îòíîøåíèè íåò àíîìàëèé
âñòàâêè è óäàëåíèÿ. Ïîêàæåì, ÷òî â ñõåìå ïðèñóòñòâóþò òîëüêî îñîáûå îãðàíè-
÷åíèÿ. Ïîñêîëüêó â ñõåìå íåò àíîìàëèé, îíà íàõîäèòñÿ â ÄÊÍÔ. Òîãäà ïî òåîðå-
ìå Ôåéäæèíà [5] îãðàíè÷åíèÿ, êîòîðûå íàõîäÿòñÿ â ñõåìå îòíîøåíèÿ, — ëîãè÷åñ-
êîå ñëåäñòâèå äîìåíîâ è êëþ÷åé. Íî ýòî âîçìîæíî òîëüêî òîãäà, êîãäà îíè ÿâëÿ-
þòñÿ ñëåäñòâèåì îñîáûõ îãðàíè÷åíèé, ïîòîìó ÷òî îñîáûå îãðàíè÷åíèÿ — ýòî
ñîâîêóïíîñòü èñêëþ÷èòåëüíî îãðàíè÷åíèé íà äîìåíû è êëþ÷è. �
Íåîáõîäèìî çàìåòèòü, ÷òî îïèñàííîå ëåììîé 5 «ìèíèìàëüíîå» îòíîøåíèå
áûëî ðàññìîòðåíî Ð. Ôåéäæèíûì [5, ïðèìåð 3.10]. Îäíàêî äîïîëíèòåëüíûå
îãðàíè÷åíèÿ íà òàêóþ ñõåìó, íàçâàííûå òàì çàâèñèìîñòÿìè âëîæåíèÿ (êîãäà
êàæäîå âõîæäåíèå â X äîëæíî òàêæå âõîäèòü è â A, îáîçíà÷àåòñÿ X A� ), ïðè-
âåëè ñõåìó ê àíîìàëèÿì óäàëåíèÿ. Ïðè ýòîì â [5] óêàçàíî, ÷òî áîëåå îáùàÿ ñõå-
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
ìà, â êîòîðîé «åäèíñòâåííûìè îãðàíè÷åíèÿìè ÿâëÿþòñÿ ÔÇ, ìîæåò âñåãäà ïðîñ-
òûì ñïîñîáîì ïðåîáðàçîâûâàòüñÿ â ÄÊÍÔ-ñõåìó ÁÄ... . Äëÿ êàæäîé ÔÇ X Y�
èñõîäíîé ñõåìû, ìû ôîðìèðóåì íîâóþ ñõåìó îòíîøåíèÿ ñ àòðèáóòàìè XY è
ñ åäèíñòâåííûì îãðàíè÷åíèåì KEY( )X ». Ïîýòîìó ïî àíàëîãèè ñ [5] ïðèâåäåí-
íîå äîêàçàòåëüñòâî áóäåì ñ÷èòàòü èñ÷åðïûâàþùèì âñþäó äî òåõ ïîð, ïîêà íåò
«êîíòðïðèìåðà» îòíîøåíèÿ R X A( , )) òàêîãî, ÷òî îñîáûå îãðàíè÷åíèÿ óäîâëåòâî-
ðÿþò R, íî è òàêîãî, ÷òî íàéäóòñÿ òàêèå èíûå îãðàíè÷åíèÿ-ñëåäñòâèÿ îñîáûõ
�D X A( , ) è �K X A( , ), ÷òî R ñòàíåò àíîìàëüíûì.
Âåäåì îïðåäåëåíèå ñõåìû ÁÄ. Ñîãëàñíî [5] ñõåìà ÁÄ — ýòî íàáîð ðåëÿöèîí-
íûõ ñõåì, êàæäàÿ èç êîòîðûõ ïðåäñòàâëÿåò ñîáîé íàáîð àòðèáóòîâ è íàáîð îãðàíè-
÷åíèé. Êàðêàñíóþ ñîâîêóïíîñòü îòíîøåíèé áóäåì íàçûâàòü çàìêíóòîé, åñëè â íåé
íåò íè îäíîãî îòíîøåíèÿ, ó êîòîðîãî õîòÿ áû îäíà ÷àñòü ïðîñòîãî èëè ñîñòàâíîãî
êëþ÷åâîãî àòðèáóòà âñòðå÷àåòñÿ â ñîâîêóïíîñòè åäèíñòâåííûé ðàç. Èíòóèòèâíî
ïîíÿòíî, ÷òî òàêàÿ ñîâîêóïíîñòü ìîäåëèðóåò çàìêíóòûå ñâÿçíûå ÏðÎ.
Óòâåðæäåíèå ëåììû 5, à òàêæå äîêàçàííûå â [1] òåîðåìû 3–5 ïîçâîëÿþò
ñôîðìóëèðîâàòü èòîãîâûå óòâåðæäåíèÿ, çàâåðøàþùèå ïîñòðîåíèå áàçîâîé ÷àñòè
òåîðèè ðåëÿöèîííîãî êàðêàñà.
Èìååò ìåñòî ïðîñòàÿ, íî î÷åíü âàæíàÿ äëÿ ïðîåêòèðîâàíèÿ áåçàíîìàëüíûõ
ñõåì ÁÄ òåîðåìà.
Òåîðåìà 9. Ñõåìà ÁÄ, ïîñòðîåííàÿ íà ñîâîêóïíîñòè øóíòèðîâàííûõ êàð-
êàñíûõ îòíîøåíèé, íå èìååò àíîìàëèé âñòàâêè è óäàëåíèÿ, åñëè è òîëüêî åñëè
îãðàíè÷åíèå êàæäîãî îòíîøåíèÿ ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì îñîáûõ îãðà-
íè÷åíèé.
Íåîáõîäèìîñòü. Ïóñòü êàðêàñíàÿ ñîâîêóïíîñòü R x x ai i i� � �1 1 1 1( , , , )� ,
R x x ai i i( , , , )1 � , R x x ai i i 1 1 1 1( , , , )� ÿâëÿåòñÿ øóíòèðîâàííîé. È ïóñòü ai —
øóíòèðóþùèå àòðèáóòû êàæäîãî ìíîãîàðíîãî êàðêàñíîãî îòíîøåíèÿ. Òîãäà â
ñîîòâåòñòâèè ñ ëåììàìè 3 è 4 êàæäîå øóíòèðîâàííîå îòíîøåíèå ìîæåò áûòü çà-
ìåíåíî ðàâíîñèëüíûì îòíîøåíèåì ñî ñõåìîé R X Ai i j
* ( , ) è åäèíñòâåííîé ÔÇ
X Ai j� , ãäå X x x xi i� ( )1 2 � , à A a a aj j� ( )1 2 � . Ïóñòü âñå îãðà-
íè÷åíèÿ íà äîìåíû DD X Ai i i( , ) è êëþ÷è DK Xi i( ) íå ïðîòèâîðå÷àò îñîáûì
îãðàíè÷åíèÿì. Ïîñêîëüêó ïî îïðåäåëåíèþ ÄÊÍÔ êàæäîå îòíîøåíèå âñåé ñîâî-
êóïíîñòè íàõîäèòñÿ â ýòîé íîðìàëüíîé ôîðìå, â ñîîòâåòñòâèè ñ ëåììîé 5 êàæäîå
òàêîå îòíîøåíèå íå èìååò àíîìàëèé âñòàâêè è óäàëåíèÿ.
Äîñòàòî÷íîñòü. Ïóñòü øóíòèðîâàííàÿ êàðêàñíàÿ ñîâîêóïíîñòü
R x x ai i i� � �1 1 1 1( , , , )� , R x x ai i i( , , , )1 � , R x x ai i i 1 1 1 1( , , , )� íå èìååò àíîìà-
ëèé. Òîãäà ïî òåîðåìå Ôåéäæèíà 8 îíà íàõîäèòñÿ â ÄÊÍÔ. Íî â ñîîòâåòñòâèè ñ
ëåììîé 5 ýòî âîçìîæíî ëèøü ïðè óñëîâèè, ÷òî îãðàíè÷åíèÿ êàæäîãî îòíîøåíèÿ
ÿâëÿþòñÿ ñëåäñòâèåì îñîáûõ îãðàíè÷åíèé. �
Èç ýòîãî óòâåðæäåíèÿ ñëåäóåò ïðîñòîé âûâîä äëÿ ïðîåêòèðîâùèêà: åñëè äëÿ
íåêîòîðîé ÏðÎ ñõåìà ÁÄ ïðîåêòèðóåòñÿ íà êàðêàñíîé ñîâîêóïíîñòè øóíòèðî-
âàííûõ îòíîøåíèé, è åñëè äëÿ íåêîòîðûõ îòíîøåíèé èç ýòîé ñîâîêóïíîñòè îá-
íàðóæèâàþòñÿ îãðàíè÷åíèÿ íà äîìåíû è êëþ÷è, ïðîòèâîðå÷àùèå îñîáûì îãðà-
íè÷åíèÿì, òî ýòè îãðàíè÷åíèÿ èç ñõåì îòíîøåíèé äîëæíû áûòü èñêëþ÷åíû.
 ïðîòèâíîì ñëó÷àå òàêàÿ ñõåìà ÁÄ áóäåò èìåòü àíîìàëèè.
Èç òåîðåì î ïîëíîòå, åäèíñòâåííîñòè è çàìêíóòîñòè ðåëÿöèîííîãî êàðêàñà
ñëåäóåò åùå îäíî, äàæå áîëåå ñèëüíîå óòâåðæäåíèå.
Òåîðåìà 10 (äîñòàòî÷íîå óñëîâèå áåçàíîìàëüíîñòè ðåëÿöèîííîé ñõåìû
áàçû äàííûõ). Ñõåìà áàçû äàííûõ íå èìååò àíîìàëèé âñòàâêè è óäàëåíèÿ, åñëè
îíà ïîñòðîåíà íà çàìêíóòîé ñîâîêóïíîñòè øóíòèðîâàííûõ êàðêàñíûõ îòíîøå-
íèé, êàæäîå èç êîòîðûõ èìååò îãðàíè÷åíèÿ, ëîãè÷åñêè ñëåäóþùèå èç îñîáûõ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 185
Äîêàçàòåëüñòâî. Ïðîâåäåì îò ïðîòèâíîãî. Ïóñòü èìååòñÿ èíàÿ ñîâîêóï-
íîñòü îòíîøåíèé ñ áåçàíîìàëüíîé ñõåìîé äëÿ ïðîèçâîëüíîé ñîâîêóïíîñòè îãðà-
íè÷åíèé. Ïóñòü òîãäà ñîãëàñíî ëåììàì 4 è 5 ïîëó÷åíà òàêæå ñîâîêóïíîñòü îòíî-
øåíèé: Z X X Ai i i� � �1 1 1 1( , , , )� , Z X X Ai i i( , , , )1 � , Z X X Ai i i 1 1 1 1( , , , )� ,
ñõåìà êàæäîãî èç êîòîðûõ ÿâëÿåòñÿ áåçàíîìàëüíîé. Òî, ÷òî ëåììà 5 ìîæåò èìåòü
ìíîæåñòâî «îáðàòíûõ ðåøåíèé», íåñóùåñòâåííî, òàê êàê íàñ èíòåðåñóåò èìåííî
òîò ôàêò, ÷òî îäíèì èç îáðàòíûõ ðåøåíèé óòâåðæäåíèÿ ëåììû 5 áóäåò îáÿçà-
òåëüíî íåêîòîðàÿ ñîâîêóïíîñòü îòíîøåíèé ñî ñõåìîé Z Y B( , ) , îãðàíè÷åíèÿ êî-
òîðîé îñîáûå. Íî ïîñêîëüêó òàêàÿ ñîâîêóïíîñòü çàìêíóòà ïî óñëîâèþ òåîðåìû
— ýòî ñõåìà áàçû äàííûõ íåêîòîðîé ñâÿçíîé ÏðÎ, îíà îáðàçóåò ôðàãìåíò ðåëÿ-
öèîííîãî êàðêàñà. Òîãäà èìååòñÿ äâà ðàçíûõ ôðàãìåíòà êàðêàñà. Íî ýòî ïðîòèâî-
ðå÷èò òåîðåìå î åäèíñòâåííîñòè ðåëÿöèîííîãî êàðêàñà [1]. Òàêîå ïðîòèâîðå÷èå
äîêàçûâàåò òåîðåìó. �
Ïðè ýòîì ñîâîêóïíîñòü îòíîøåíèé, êàæäîå èç êîòîðûõ íàõîäèòñÿ â äîìåí-
íî-êëþ÷åâîé íîðìàëüíîé ôîðìå, áóäåì íàçûâàòü ÄÊÍÔ-ñõåìîé ÁÄ. Ïðîåêòè-
ðîâùèêó âïîëíå äîñòàòî÷íî çíàòü, ÷òî, ïî êðàéíåé ìåðå, íà ðåëÿöèîííîì êàðêàñå
îí ìîæåò ïîëó÷èòü áåçàíîìàëüíóþ ÄÊÍÔ-ñõåìó ÁÄ ïðè óñëîâèè, ÷òî âñå îãðà-
íè÷åíèÿ ÏðÎ áóäóò ñëåäñòâèåì îñîáûõ.
Îòìåòèì, ÷òî âûâîäû òåîðåì 9 è 10 ïîëíîñòüþ ñîîòâåòñòâóåò èäåå Ä. Êðåí-
êå [10] î «åäèíñòâåííîñòè òåìû îòíîøåíèÿ». Åñëè îòíîøåíèå ìîäåëèðóåò âûñêà-
çûâàíèå ñ åäèíñòâåííîé òåìîé, îíî ñîîòâåòñòâóåò êðèòåðèÿì ÄÊÍÔ. Åäèíñòâåí-
íûé óíàðíûé èëè ñîñòàâíîé êëþ÷åâîé àòðèáóò â ýòîì êîíòåêñòå ÿâëÿåòñÿ ñåìàí-
òè÷åñêè àòîìàðíûì èëè ñîñòàâíûì ìíîãîìåñòíûì ïðåäèêàòîì [1, 20] òàêîãî
âûñêàçûâàíèÿ, ò.å. åãî «òåìîé», ïîñêîëüêó êàæäàÿ øóíòèðîâàííàÿ «ÿ÷åéêà» êàð-
êàñà, ò.å. êàæäîå àêòóàëüíîå îòíîøåíèå-ñâÿçü, ÿâëÿåòñÿ âûñêàçûâàíèåì. À àêòó-
àëüíîñòü îòíîøåíèÿ-ñâÿçè êîíñòàòèðóåò íåêèé ôàêò èç ÏðÎ.
Ïî íàøåìó ìíåíèþ, èìåííî Ä. Êðåíêå âïåðâûå ââåë ïîíÿòèå «òåìà» êàê ëî-
ãè÷åñêîå ñëåäñòâèå êëþ÷à: îäèí êëþ÷ — îäíà òåìà. Îí òåì ñàìûì èíòóèòèâíî
ïîäñêàçàë, ÷òî ó êëþ÷à îòíîøåíèÿ, åñëè îí åäèíñòâåíåí, ïîÿâëÿåòñÿ åùå îäíà
âàæíàÿ ìèññèÿ, íåæåëè òîëüêî ñîõðàííîñòü öåëîñòíîñòè îòíîøåíèÿ è äîñòóï
ê äàííûì, — áûòü íîñèòåëåì ñåìàíòèêè îòíîøåíèÿ.
Âûâîä î òîì, ÷òî â îòíîøåíèè ñ ÄÊÍÔ-ñõåìîé íå ìîæåò áûòü áîëüøå îäíî-
ãî êëþ÷à è áîëüøå îäíîãî äåòåðìèíàíòà íåêëþ÷åâûõ àòðèáóòîâ, òàêæå ïðåäëî-
æèë Ä. Êðåíêå. «Åñëè â îòíîøåíèè èìååòñÿ òðè àòðèáóòà R A B C( , , ) è ïðè ýòîì
( , )A B C� , òî íå äîëæíî áûòü åùå è çàâèñèìîñòè A B� .  ïðîòèâíîì ñëó÷àå
ïî ýòîé çàâèñèìîñòè îòíîøåíèå äîëæíî áûòü äåêîìïîçèðîâàíî» [10]. Îòíî-
øåíèå, ïîñòðîåííîå íà ðåëÿöèîííîì êàðêàñå, àâòîìàòè÷åñêè îáëàäàåò åäèí-
ñòâåííîé ÔÇ.
ÇÀÊËÞ×ÅÍÈÅ
Áëàãîäàðÿ ðåëÿöèîííîìó êàðêàñó [1] ïîëó÷åíà âîçìîæíîñòü äëÿ ïðîèçâîëüíîé
ÏðÎ ðàçðàáîòàòü àëãîðèòì àâòîìàòèçèðîâàííîé äåêîìïîçèöèè è ñèíòåçà ñõå-
ìû ðåëÿöèîííîé ÁÄ â ôîðìå, îòíîñÿùåéñÿ ê ìàêñèìàëüíî âûñîêîé ñòåïåíè
íîðìàëüíîñòè. Ïðè ýòîì êàðêàñíàÿ ñõåìà ÁÄ ïîëó÷àåò äîïîëíèòåëüíûå êîíêó-
ðåíòíûå ïðåèìóùåñòâà, âàæíûå äëÿ ïðîåêòèðîâùèêîâ-ïðàêòèêîâ.
Ê íèì îòíîñÿòñÿ ñëåäóþùèå ñâîéñòâà (ïî óáûâàíèþ çíà÷èìîñòè):
1) áåçàíîìàëüíîñòü â ñìûñëå [5];
2) äèíàìè÷åñêàÿ ìîäèôèöèðóåìîñòü ñõåìû ÁÄ, ÷òî ïîçâîëÿåò êîððåêòíî
âíîñèòü èçìåíåíèÿ â ýêñïëóàòèðóåìîå ïðèëîæåíèå, à òàêæå ãèáêî ìîäèôèöèðî-
âàòü ñõåìû íå òîëüêî ïîëüçîâàòåëüñêèõ, íî è óïðàâëÿþùèõ ÁÄ (ìåòàáàç);
3) ïîäîáèå ñõåì ÁÄ äëÿ ðàçíûõ ÏðÎ, íåñìîòðÿ íà çíà÷èòåëüíûå îòëè÷èÿ
ñåìàíòèê, ÷òî îáåñïå÷èâàåò èíòåðîïåðàáåëüíîñòü è êðîññïëàòôîðìíîñòü ïðè-
ëîæåíèé [6].
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Âñå ïåðå÷èñëåííîå äàåò âîçìîæíîñòü ðåøèòü ïðîáëåìó óíèôèêàöèè, òèïè-
çàöèè è ìèíèìèçàöèè ÑÓÁÄ, ò.å. ïî ñóòè, ðàçðàáîòàòü èíñòðóìåíòàëüíóþ îáî-
ëî÷êó, êîòîðàÿ ìàñøòàáèðóåòñÿ ìåòàäàííûìè, è íà ýòîì îñíîâàíèè ñîçäàòü ìà-
ëîãàáàðèòíûé CASE-ãåíåðàòîð êàðêàñíûõ ìåòàäàííûõ, óïðàâëÿþùèõ óíèâåð-
ñàëüíîé êàðêàñíîé îáîëî÷êîé, à òàêæå ñíàáäèòü ýòîò ãèáêèé èíñòðóìåíò
áèáëèîòåêîé òèïîâûõ ôóíêöèé íàâèãàöèè êàðêàñíîé ÐÁÄ, èñïîëüçóåìûõ â óíè-
ôèöèðîâàííûõ çàïðîñàõ.
Òàêîé ïîäõîä ìèíèìèçèðóåò ïîòðåáíîñòü â ðåñóðñîåìêèõ îïåðàöèÿõ ñîåäèíå-
íèÿ â áîëüøèíñòâå çàïðîñîâ ê ÁÄ, è ñóùåñòâåííî óïðîñòèò íàñòðîéêó ïðèëîæåíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê à ð ï ó ø à Â . Ä . , Ï à í ÷ å í ê î Á . Å . Ìîäåëèðîâàíèå è ïðîåêòèðîâàíèå ðåëÿöèîííûõ áàç
äàííûõ: Ó÷. ïîñîáèå. — Ñóìû: Èçä. ÑóìÄÓ, 2010. — 385 ñ.
2. Ï à ò . 63036. Ñïîñ³á ðîçì³ùåííÿ äàíèõ ó êîìï’þòåðíîìó ñõîâèù³ ç çàáåçïå÷åííÿì ìîäèô³êà-
ö³éíîñò³ éîãî ñòðóêòóðè / Á.ª. Ïàí÷åíêî // Ïðîìèñëîâà âëàñí³ñòü. — 2004. — ¹ 1. — C. 3.134.
— Äàòà çàÿâêè 15.11.2001.
3. Ï à ò . 92248. Ñïîñîá îáîáùåííîãî ðàçìåùåíèÿ äàííûõ ñ ó÷åòîì ìîäèôèöèðóåìîñòè ñòðóêòó-
ðû õðàíèëèùà / Á.ª. Ïàí÷åíêî // Òàì æå. — 2009. — ¹ 1. — C. 3.134. — Äàòà çàÿâêè
02.03.2009.
4. À ë ò à é á å ê À . À . Ïðîåêòèðîâàíèå áàç äàííûõ íà îñíîâå äîìåííî-êëþ÷åâîé íîðìàëüíîé
ôîðìû // Âåñòí. ÊàçÍÓ. — 2009. — ¹ 1. — C. 111–118.
5. F a g i n R . A normal form for relational databases. That is based on domains and keys // ACM
Transact. on Database Systems. — 1981. — 6, N 3. — P. 387–415.
6. Ïåðåâîç÷èêîâà Î.Ë. Îñíîâû ñèñòåìíîãî àíàëèçà îáúåêòîâ è ïðîöåññîâ êîìïüþòåðèçàöèè:
Ó÷åáíèê. — Êèåâ: Èçä. äîì «ÊÌ Àêàäåìèÿ», 2003. — 247 ñ.
7. C o d d E . F . The relational model for database management. Vers. 2. Reading Mass. — New York:
Addison-Wesley Publ. Co, 1990. — 538 p.
8. B e r n s t e i n P . A . Synthesizing third normal form relation from functional dependencies // ACM
Transact. on Database Systems. — 1976. — 1, N 4. — P. 277–298.
9. C h e n P . P . The entity-relationship model: toward a unified view of data // Ibid. — 1976. — 1,
N 1. — P. 9–36.
10. Ê ð å í ê å Ä . Ì . Òåîðèÿ è ïðàêòèêà ïîñòðîåíèÿ áàç äàííûõ. — ÑÏá.: Ïèòåð, 2003. — 800 ñ.
11. Ñ ò å ï à í î â À . È . ×èñëî è êóëüòóðà. — Ì.:, 2004. — 832 ñ.
12.  î ë ê î â à  . Í . , Ä å í è ñ î â À . À . Îñíîâû òåîðèè ñèñòåì è ñèñòåìíîãî àíàëèçà: Ó÷åáíèê.
— ÑÏá.: Èçä. ÑÏáÃÒÓ, 2001. — 512 ñ.
13. A b i t e b o u l S . , B e e r i C . On the power of languages for the manipulation of complex values.
Technical report. — Cadex (France): INRIA, 1995. — 80 p.
14. Ò à ð à ñ î â È . À . Öåëîñòíîñòü äàííûõ, àíîìàëèè ìîäèôèêàöèè äàííûõ è íîðìàëüíûå ôîðìû
òàáëèö ðåëÿöèîííûõ áàç äàííûõ // Ïðîåêòèðîâàíèå òåëåêîììóíèêàöèîííûõ è èíôîðìàöèî-
ííûõ ñðåäñòâ è ñèñòåì. — Ì.: ÌÈÝÌ, 2007. — 195 ñ.
15. Ò à ð à ñ î â È . À . Íåäîñòàòêè òåîðèè äîìåííî-êëþ÷åâîé íîðìàëüíîé ôîðìû (DKNF) Ðî-
íàëüäà Ôàãèíà. — http://itsoft.ru/about/publication/dbdesign/dknf/
16. Ã î ë î ñ î â À . Î . Àíîìàëèè â ðåëÿöèîííûõ áàçàõ äàííûõ // ÑÓÁÄ. — 1996. — ¹ 3. —
C. 23–38.
17. F a g i n R . Multivalued dependencies and a new normal form for relational databases // ACM
Transact. on Database Systems. — 1977. — 2, N 3. — P. 262–278.
18. Ê ó ç í å ö î â Ñ . Ä . Áàçû äàííûõ: ìîäåëè è ÿçûêè: Ó÷åáíèê. — Ì.: 2008. — 720 ñ.
19. Ì å é å ð Ä . Òåîðèÿ ðåëÿöèîííûõ áàç äàííûõ. — Ì.: Ìèð, 1987. — 608 ñ.
20. Ï à í ÷ å í ê î Á . Å . , Ï è ñ à í ê î È . Í . Ñâîéñòâà ðåëÿöèîííîãî êàðêàñà íà ìíîæåñòâå ñåìàí-
òè÷åñêè àòîìàðíûõ ïðåäèêàòîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 6. —
C. 120–129.
Ïîñòóïèëà 24.10.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 187
|