Рекурсивные связи и темпоральность в реляционном каркасе — маски сущностей-объектов

У відповідності до нової моделі даних — реляційного каркаса — неформально описано алгоритм врахування рекурсивних зв’язків сутностей-об’єктів в предметній області. Алгоритм застосовується для більш точного проектування схем реляційних баз даних (БД). Для цього запропоновано механізм каркасного синте...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Панченко, Б.Е.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Назва видання:	Проблемы управления и информатики
Теми:	Методы обработки информации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207604
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Рекурсивные связи и темпоральность в реляционном каркасе — маски сущностей-объектов / Б.Е. Панченко // Проблемы управления и информатики. — 2013. — № 2. — С. 92–105. — Бібліогр.: 30 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207604
record_format	dspace
spelling	irk-123456789-2076042025-10-12T00:15:34Z Рекурсивные связи и темпоральность в реляционном каркасе — маски сущностей-объектов Рекурсивні зв’язки та темпоральність у реляційному каркасі — маски сутностей-об’єктів Recursive Relations and Temporality in the Relational Framework — the Masks of Entity-Objects Панченко, Б.Е. Методы обработки информации У відповідності до нової моделі даних — реляційного каркаса — неформально описано алгоритм врахування рекурсивних зв’язків сутностей-об’єктів в предметній області. Алгоритм застосовується для більш точного проектування схем реляційних баз даних (БД). Для цього запропоновано механізм каркасного синтезу часткових копій атрибутів, що беруть участь у різних ролях сутностей-об’єктів. Запропоновано також новий підхід до моделювання темпоральних даних. Наведено результати числового експерименту доступу до БД. In accordance with a new data model — relational framework — an algorithm of recognition of recursive relations of entity-objects in a subject domain is informally described. The algorithm is used for precise designing of schemes of relational databases (DB). For this, we offer a mechanism of framework synthesis of partial attributes’ copies that take part in various roles of entity-objects. We also offer a new approach to designing temporal data. Results of a numerical experiment of DB access are given. 2013 Article Рекурсивные связи и темпоральность в реляционном каркасе — маски сущностей-объектов / Б.Е. Панченко // Проблемы управления и информатики. — 2013. — № 2. — С. 92–105. — Бібліогр.: 30 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207604 004.652 10.1615/JAutomatInfScien.v45.i4.60 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	2013
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207604
citation_txt	Рекурсивные связи и темпоральность в реляционном каркасе — маски сущностей-объектов / Б.Е. Панченко // Проблемы управления и информатики. — 2013. — № 2. — С. 92–105. — Бібліогр.: 30 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT pančenkobe rekursivnyesvâziitemporalʹnostʹvrelâcionnomkarkasemaskisuŝnostejobʺektov AT pančenkobe rekursivnízvâzkitatemporalʹnístʹurelâcíjnomukarkasímaskisutnostejobêktív AT pančenkobe recursiverelationsandtemporalityintherelationalframeworkthemasksofentityobjects
first_indexed	2025-10-12T01:11:37Z
last_indexed	2025-10-13T01:09:44Z
_version_	1845826981427412992
fulltext	© Б.Е. ПАНЧЕНКО, 2013 92 ISSN 0572-2691 МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ УДК 004.652 Б.Е. Панченко РЕКУРСИВНЫЕ СВЯЗИ И ТЕМПОРАЛЬНОСТЬ В РЕЛЯЦИОННОМ КАРКАСЕ — МАСКИ СУЩНОСТЕЙ-ОБЪЕКТОВ Введение В работе [1] обоснована новая концептуальная модель данных, построенная на реляционном каркасе, который формируется на основе декартовой зависимо- сти ключевых атрибутов. В [2] показан обобщенный алгоритм синтеза схем реля- ционных БД (в дальнейшем — БД), моделирующих поведение предметных обла- стей (ПрО). Этот алгоритм позволяет использовать единую процедуру автомати- зации процесса дизайна схемы БД. Важной особенностью подхода является возможность моделировать связи степенью GH : в схеме одного отношения. Этот метод обеспечил модифицируемость [1] схемы БД, т.е. минимизировал число операций для внесения изменений в динамическом режиме — непосред- ственно в процессе эксплуатации приложения, а также дал возможность оптими- зировать объединение различных приложений в единую информационную систе- му. Алгоритм синтеза схемы БД [3], также построенный на разделении отноше- ний-сущностей и отношений-связей, как отмечалось в [1], имеет ряд недостатков. Одним из наиболее существенных является невозможность корректного, с точки зрения теории нормализации [4], моделирования рекурсивных связей [5]. Постановка задачи Рассмотрим более подробно пример из [6]. Пусть в ПрО «Поликлиника» ре- гулярно формируются отчеты по неключевому атрибуту ПолПациента из отно- шения ВИЗИТ К ВРАЧУ (Пациент, Талон, ПолПациента, …). Для упрощения процедуры синтеза отчетов может использоваться принцип «маска для роли» атомарной сущности-объекта, предложенный в [7] — отдельное отношение, кото- рое является частичной копией атомарного отношения ПАЦИЕНТ. Моделирова- ние и поддержка таких отношений существенно сокращают потребность проекти- ровщика разрабатывать листинги запросов, что в итоге улучшает эксплуатацион- ные свойства приложения. Отношение-связь с ключами ПолПациента+КодТалона может формировать- ся в реальном времени по факту обновления базового отношения. В формируемом отношении, которое универсальными процедурами в процессе эксплуатации под- держивается в целостном состоянии и актуально, может храниться и необходимая статистика — формироваться естественные неключевые шунтирующие атрибуты. В [6] такая декомпозиция отношения ПАЦИЕНТ на два отношения — ПОЛ ПАЦИЕНТА и, например, ВОЗРАСТ ПАЦИЕНТА — определена как денормализа- ция. Однако Р. Фейджин в [8, 9] аналогичный прием привел как пример нормализа- ции схемы отношения: «…Схема может быть разложена на две … кортеж, содер- Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 93 жащий данные о поле человека, входит в первое отношение, а кортежи, содержа- щие данные о его профессии, входят во второе отношение. Схема SEX_ROLE удо- влетворяет функциональной зависимости (ФЗ) PERSONROLE, в то же время схема PROF_ROLE не удовлетворяет этой зависимости. … Преимущество разло- жения состоит в том, что механизм обработки ключей системы может тогда предотвратить вставку двух ролей пола для одного человека». Таким образом, учет рекурсивных связей, а также возможность многократно- го добавления ключевых атрибутов, отвечающих за различные состояния состав- ных сущностей-объектов, выполняющих разные роли в ПрО, в каркасной схеме БД [7] могут быть осуществлены с использованием масок. При этом возможен учет номеров отрезков времени таких модификаций в таких отношениях. Этот механизм позволил вносить изменения в схему БД по полно-модифици- руемому принципу, а не с существенным редизайном как самой схемы БД, так и приложения. Схожий подход к проектированию рекурсивных связей описан и в [10]. Од- нако вопрос нормализации отношений, построенных на частичных копиях сущно- стей-объектов, там не исследован. Маски сущностей-объектов В [2, 7] предложена классификация сущностей-объектов произвольной ПрО, которая наиболее соответствует каркасной совокупности, а также формально определены артефакты как сущности-копии, данные о которых будут условно размещаться в БД по решению пользователя. Важным частным случаем артефакта является маска сущности-объекта. Под маской сущности-объекта будем понимать такой многоместный преди- кат ),,( jkj BXM ключевым предикатом которого является ключевой предикат некоторого семантически атомарного, слабого или составного предиката (т.е. ис- ходной сущности-объекта), а аргументами — ограниченная совокупность аргу- ментов этого же предиката. Таким образом, под маской сущности-объекта будем понимать такую ча- стичную копию сущности-объекта (такой артефакт), которая является носителем ограниченной группы атрибутов этой сущности-объекта, отвечающих лишь за единственную роль [11] сущности-объекта. На языке схем БД под масками отношения ),,( nk AXR в котором совокуп- ность атрибутов kX является единственным ключом, а совокупность атрибутов nA не является ключом и полностью зависит от ключа, будем понимать совокупность отношений ),,( jkj BXM в каждом из которых имеется лишь некоторая уникальная часть неключевых атрибутов ,nj AB  где ,1j n и ,21 nj ABBB   а также имеется единственный ключ kX — копия ключа отношения R. Таким об- разом, отношения ),( nk AXR и ),( jkj BXM подобны [12]. Процедура их форми- рования может иметь несколько частных случаев. 1. ),,( jij BXM где ki  — рассечение отношения ),( nk AXR операцией split [8] на слои при постоянстве некоторой части ключа const.ikX 2. ),,,( nmkkj AXXM  где mkX  — новое дополнительное звено един- ственного ключа, которое отвечает за этимологию смысла [2] роли моделируемой сущности-объекта. Очевидно, что такое звено может быть как унарным, так и многоарным. Последний случай отвечает за иерархическую маску. 94 ISSN 0572-2691 3. ),,,( nkjj AXYM где jY — новый дополнительный ключ отношения, как правило, суррогатный унарный атрибут. Каждая сущность-объект может иметь в ПрО определенное число разных ма- сок, т.е. либо множество, либо несколько, либо лишь одну. Тем не менее число масок обусловливается числом ролей сущности-объекта в ПрО, т.е. связей, в ко- торых принимает участие сущность-объект. Если, например, рассматривается сущность-объект ЧЕЛОВЕК, то таких масок может быть значительное количество: СПЕЦИАЛЬНОСТЬ, ДОЛЖНОСТЬ, ВОИНСКОЕ ЗВАНИЕ, НАУЧНАЯ СТЕПЕНЬ и т.д. Тем не менее если это сущность-объект ЖИВОТНОЕ, то масок может быть намного меньше: ДОМАШНИЕ ЖИВОТНЫЕ, ДИКИЕ ЖИВОТНЫЕ, СКОТ и т.д. Маски необходимы лишь тем сущностям-объектам, которые могут выпол- нять разные роли. Очевидно, что связи, которые моделируются составными сущ- ностями-объектами, дальнейшего участия в новых связях не принимают. Для кар- касной совокупности отношений это свойство связей доказано в [2] в виде леммы. Характерной особенностью участия в разных связях атомарных и слабых сущно- стей-объектов является их темпоральность. Иными словами, каждая роль, кото- рую выполняют атомарные или слабые сущности-объекты в одной из связей, но- сит временный характер. Способ простого декартова произведения, используемый в [1, 2], также фор- мирует реляционный каркас и тем самым учитывает все возможные связи между группами сущностей-объектов, которые могут образовываться в ПрО. Однако он не учитывает влияние разнообразия ролей каждой сущности-объекта на разнооб- разие связей, которое ограничивает его применение. Таким образом, маски могут применяться в следующих случаях. 1. Для корректного моделирования рекурсивных связей между экземплярами одной и той же сущности-объекта, выполняющими разные роли. Например, физи- ческие или юридические лица, одновременно выступающие в ролях покупатель– продавец, учащийся–преподаватель, врач–пациент и т.п. 2. Для регулярного формирования в БД в отдельном отношении группы ат- рибутов как фрагмента одного исходного отношения (или группы отношений), выделенного по определенному условию, налагаемому на одну или несколько ча- стей ключевого атрибута (например, равенство определенному значению). Однако в отношения-маски ключевые атрибуты-фильтры не копируются. 3. Для значительного сокращения списка экземпляров справочной сущности- объекта (выделенных по определенному условию) и использования лишь в со- кращенном виде. 4. Для переименования ключевых атрибутов. 5. Для совмещения метаданных и данных в одном отношении. Синтез отношений-масок может осуществляться либо посредством пост- процедурного запроса, либо запроса реального времени, выполнение которого синхронизировано с формированием исходного отношения. Аналогичная потреб- ность в таком формировании отношений описана в [13]: «Отношения должны быть доступны по-разному у разных пользователей за один и тот же промежуток времени». Нормализация отношений, построенных на масках Покажем, что маски, построенные на актуальных ячейках каркаса [14], обла- дают 5НФ, а при некоторых условиях на ограничения — и доменно-ключевой нормальной формой (ДКНФ) [9]. Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 95 Пусть отношение ),( jkj BXM является j-й маской отношения ).,( nk AXR Тогда совокупность атрибутов kX — единственный ключ, а совокупность атри- бутов nA и jB не является ключом и полностью зависит от него. При этом .nj AB  Если отношение ),( nk AXR — актуальная ячейка реляционного карка- са и его ограничения — логическое следствие особых ограничений [1], то оно находится в безаномальной ДКНФ [9]. Отношение ),( jkj BXM подобно отношению ),( nk AXR с коэффициентом подобия 1 [12]. Подобными в [12] названы схемы отношений с равным чис- лом ключей и ключевых ФЗ. При этом если в сравниваемых отношениях имеется разное число ключей, то отношения не являются подобными, а тип, число и ар- ность неключевых атрибутов на подобие схем не влияют. Под коэффициентом подобия схем отношений в [12] понимается целая часть от деления большей арно- сти ключей на меньшую. Тогда форма нормализации маски ),( jkj BXM строго соответствует 5НФ, так как, исходя из подобия, имеет единственный ключ и единственную ключевую ФЗ ,jk BX  а условием принадлежности отношения к ДКНФ по теореме о безаномальности актуальных ячеек каркаса является логиче- ское следствие ограничений на домены и ключи данного отношения из особых ограничений [1, 14]. В работе [9] приведен пример, подтверждающий данный вывод. Все обозначе- ния соответствуют [1, 9]. Пусть R — реляционная схема с атрибутами КодСотр, Статус, Зарплата и ограничениями:  })000:{,()( nКодСотрRDD ))1;0(,(})100001000:{,( СтатусnnЗарплата  KD(R)KEY(КодСотр) )),5000][()0][((  ZtSTATUStt где атрибут Статус — переменная STATUS, а атрибут Зарплата — переменная Z. Смысл ограничений выражается так: КодСотр — целое число из трех цифр, преобразованное в строку с добавлением ведущих нулей в соответствии с форма- том ‘000’; КодСотр является ключом; имеется два статуса: 0 и 1; значение Зар- плата может изменяться в диапазоне между 1000 и 10000. Исключение: сотруд- ники со статусом 0 не могут иметь зарплату больше 5000. Эта схема находится в 4НФ и даже в 5НФ. Однако в схеме есть следующая аномалия вставки. Пусть R — отношение с первыми тре- мя кортежами в таблице. Это отношение — до- пустимый экземпляр схемы. Пусть t — четвер- тый кортеж (006, 0, 5600). Кортеж t совместим с отношением R. Однако, вставив кортеж t в R, мы бы получили отношение, которое не является допустимым экземпляром схемы, так оно нарушает ограничение, что любой работник со статусом 0 не может иметь зарплату больше 5000. Следовательно, схема в примере не находится в ДКНФ, и для получения ДКНФ одного только подхода декомпозиции недостаточно. Здесь вновь может быть использован оператор разделения split [9]. Таким образом, Р. Фейджин в [9] заменяет первоначальную в примере схему R двумя схемами: 1R и ,2R где эк- Таблица КодСотр Статус Зарплата 003 1 7300 004 0 3200 005 1 4600 006 0 5600 96 ISSN 0572-2691 земпляры схемы 1R содержат информацию о сотрудниках со статусом 0, а экзем- пляры схемы 2R — о сотрудниках со статусом 1. Тогда отношение со схемой 1R (первая маска), содержащее информацию о сотрудниках со статусом 0, имеет только атрибуты КодСотр и Зарплата. Атрибут Статус больше не является не- обходимым, так как все значения тождественно равны 0. Ограничения отношения 1R теперь имеют вид: DD(R) IN(КодСотр, {n: ‘000’})  IN(Зарплата,{n: 1000≤n≤5000}) KD(R)KEY(КодСотр). Отношение со схемой 2R (вторая маска) содержит информацию о сотрудни- ках со статусом 1. Исключение лишь в том, что в ограничениях отноше- ния 2R значение 5000 необходимо заменить на 10 тыс. В соответствии с выводом, приведенным в [9], схемы 1R и 2R находятся в ДКНФ. Проверим, какова форма отношений-масок в частных случаях. 1. Слои ),( nij AXM отношения ),( nk AXR при постоянстве некоторой ча- сти ключа const,ikX где .ki  Поскольку отношение ),( nij AXM подобно отношению ),,( nk AXR имеет единственный многоарный ключ ,iX единствен- ную ключевую ФЗ шунтировано неключевыми атрибутами ,nA оно относится к 5НФ. А при ограничениях, являющихся логическим следствием особых ограни- чений, — и к ДКНФ. 2. Отношение ),,,( nmkkj AXXM  где mkX  — новое дополнительное звено единственного ключа, которое может быть как унарным, так и многоарным. Как и отношение ),,( nk AXR оно имеет единственный многоарный ключ ,mkk XX  единственную ключевую ФЗ, шунтировано неключевыми атрибутами nA и отно- сится к 5НФ, а при ограничениях, являющихся логическим следствием особых ограничений, — и к ДКНФ. 3. Отношение ),,( nkjj AXYM с новым дополнительным независимым клю- чом .jY В связи с наличием транзитивной функциональной зависимости (ФЗ) от двух независимых ключей это отношение должно быть декомпозировано на два отношения. В [2] это утверждение доказано в виде леммы 1 (обозначения соответствуют [1, 9]). Если отношение ),,( AYXR имеет ограничения const))(,(const))(,(const))(,()(  AAAINYYYINAYXXXINRDD (Y),KEY(X)KEY)( RKD то в нем существует транзитивная зависимость .AYX  Таким образом, в большинстве случаев использование масок не приводит схему отношения к денормализации, за исключением случая введения дополни- тельного ключа. Поэтому вывод, что такая замена всегда снижает форму норма- лизации отношений, ошибочен. Однако при использовании масок могут возни- кать некоторые некритические проблемы программной реализации. Рассмотрим их подробнее. 1. Потребность объединить в одной операции (запросе) и данные, и метадан- ные: восстановить исключенную связь, но не между значениями исходных и ре- зультирующих атрибутов, а между значениями атрибутов исходных отношений и Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 97 именами результирующих отношений-масок. При этом, как правило, разным зна- чениям фильтруемых атрибутов соответствуют разные группы результирующих отношений-масок. Как уже упоминалось, аналогичный тип отношения применял- ся разными авторами [10, 13, 15]. «Такое рассечение … обычно требует разных имен таблиц в запросах, в зависимости от значений в таблице» [15]. Авторы, ука- занных работ отнесли эти отношения к категории денормализованых. Однако, как было показано ранее, маски, подобные актуальным ячейкам каркаса [14], имеют форму не ниже 5НФ. Формально, пусть в отношении со схемой ),,,,( 21 jn AXXXR  имеются атрибуты ,lk XX  каждое текущее значение конкатенации которых соответ- ствует некоторым константам из совокупности }.,,,{ 21 sccc XXX  Пусть в приложении работает процедура, которая по факту появления в от- ношении R каждой новой записи проверяет условие равенства }{ sclk XXX  и при его выполнении, в зависимости от значения константы , scX формирует но- вые записи только в f-й группе, состоящей из p отношений ),,,,( f j f n f m f p BXXQ  где .,1 fPp  Однако при этом в любом отношении f pQ атрибуты lk XX  от- сутствуют (в этом смысл частичной копии отношения, т.е. маски). Тогда данная процедура будет выполнимой, если на момент выполнения условия sclk XXX  для любых ,sc p и f существует однозначное соответствие . f pc QX s  Такое соответствие может быть заранее организовано проектиров- щиком в виде отдельного отношения-маски ),( pc QXZ s или ),,( pc DXZ s где вместо имени отношения pQ использован, например, номер отношения ,pD т.е. метаданные. Однако, исходя из подхода [16], отношение ),( pc QXZ s или ),( pc DXZ s может восприниматься как выходящее за рамки начальной реляционной модели данных. Но, исходя из концепции современного языка SQL, такое объединение — типовая процедура. 2. В отношении-маске появляются взаимные ФЗ [17] в двух ключах — пер- вичном и новом .YX  Это приводит к денормализации схемы БД, потому что отношение-маска ),,( AYXR формально обладает «паразитной» транзитивной ФЗ неключевого атрибута от каждого из ключей: ,YX  AY  и ,XY  .AX  Тот же факт, что YX  — ключи, не компенсирует такую транзитивность. Аномалия устраняется декомпозицией исходного отношения на два отношения: ),(1 YXR и ),,(2 AYR где Y — новый ключ. Но при этом появляется дополни- тельное суррогатное отношение ),(1 YXR — взаимно-однозначное соответствие ключевых атрибутов (хелпер-таблица [18]). Однако, как правило, проектировщики не проводят такую декомпозицию, считая, что схема ),,( AYXR более компактна, а вероятность проявления анома- лии мала. При этом отношение-маска со схемой ),,( AYXR выполняет две функ- ции одновременно: моделирует однозначное соответствие между разными ключе- выми атрибутами и новую сущность-объект с атрибутами A. 98 ISSN 0572-2691 Уточненный алгоритм проектирования схем БД с использованием масок Число масок произвольной сущности-объекта не может быть любым или от- деленным от числа других масок этой сущности-объекта или иных сущностей- объектов. При образовании бинарных, тернарних или связей более высокой арно- сти со стороны каждой задействованной в этой связи сущности-объекта должна быть «предоставлена» соответствующая маска. А это, в свою очередь, означает, что маски актуализируются или аннулируются синхронно с актуализацией или аннулированием соответствующих связей, т.е. ролей, в которых те или иные группы сущностей-объектов принимают участие. Это соответствие масок суще- ственно упрощает построение модели ПрО. Признаком отнесения характеристик-атрибутов к той или иной маске есть смысловая, т.е. предикатная зависимость конкретной характеристики-атрибута от конкретной маски сущности-объекта. Такая процедура отвечает каркасной моде- ли. Используется тот факт, что каждый атрибут принадлежит лишь одной уни- кальной сущности-объекту, а лишь общая совокупность всех атрибутов образо- вывает полную взаимно независимую совокупность свойств, и объединение раз- ных групп характеристик от разных предикатов в одну сущность-объект (в одно отношение), что часто наблюдается в искусственных сущностях-объектах (в ар- тефактах), зачастую приводит к появлению нежелательных «паразитных» межатрибутных ФЗ. Таким образом, формальным признаком корректного отбора атрибутов сущ- ности-объекта в отдельную маску есть отсутствие в совокупности атрибутов тран- зитивных зависимостей, а также отсутствие дополнительных потенциальных ключей в кортежах отношений. При таком принципе отбора атрибутов сущности- объекта в совокупность атрибутов маски сущности-объекта не возникает условий существования ФЗ частей составных ключей от неключевых атрибутов, и наоборот. Итак, сама маска есть не только поименованная частичная копия сущности- объекта, а и эксклюзивный носитель группы взаимно-независимых атрибутов именно этой сущности-объекта. Таким образом, каждое отношение-маска вмеща- ет лишь единственный составной ключ и группу функционально взаимонезависи- мых атрибутов маски, которые полностью зависят лишь от ключа. Композиционный метод синтеза схем отношений благодаря алгоритму управления ФЗ предложил П.А. Бернштейн в 1975 г. [19]. Он отмечал, что под ФЗ понимается связь между сущностями-объектами и между сущностями-объектами и их атрибутами. Тем не менее, поскольку входным фактором вышеупомянутого метода является набор ФЗ определенной ПрО, в этом его существенный недоста- ток. Реляционные схемы, которые образовываются в соответствии с этим алго- ритмом, зависят от семантики ПрО. В отличие от упомянутого, описываемый ал- горитм предоставляет процедуру абстрагирования от ФЗ. Таким образом, в алгоритме синтеза реляционного каркаса как шаблона схе- мы БД, предложенного в [2], необходимо учесть маски сущностей-объектов. По аналогии с [2] будем употреблять термин «маска» в значении логической частич- ной копии сущности-объекта, а термин «домен-маска» — в значении физического размещения данных из маски в участке памяти. Шаг 1. Для каждой сущности-объекта в памяти отводится несколько участ- ков для размещения элементов хранения. В каждом участке размещают домен- маску с идентификатором ячейки, структура которого строго соответствует структуре, найденной по [2] этимологии. Таким образом, создается множество доменов-масок. Для использования в схеме БД отношений-масок важно правильно модели- ровать слабые сущности-объекты. Поэтому домены-маски назначаются всем мас- Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 99 кам базовой совокупности [2] сущностей-объектов, в том числе и маскам слабых сущностей-объектов. Поскольку в общем случае слабые сущности-объекты зависят от цепи сущно- стей-объектов, где каждая сущность-звено является также слабой сущностью- объектом (исключая лишь наивысшую), на начальном этапе проектирования схе- мы БД маски назначают так, будто этой зависимости не существует, т.е. анало- гично процедуре получения базовой совокупности сущностей-объектов, игнори- руя иерархическую зависимость. Алгоритм предусматривает дальнейший учет всех типов связей между масками, а значит, и иерархических связей между сущ- ностями-объектами, это действие не приведет к потере иерархических связей. При этом проектировщик схемы БД должен отслеживать семантическое соответствие каждой маски каждой роли, т.е. соответствие масок и связей: чтобы одна маска уникально соответствовала единственной роли. Шаг 2. Осуществляется формирование расширенного каркаса связей масок — сочетание декартовых произведений всех упомянутых доменов-масок между со- бой по принципу «все на все». Общее число )(tS полученных таким образом от- ношений для БД существенно увеличивается по сравнению с другими способами. С учетом множества масок каждой сущности-объекта и зависимости количе- ства сущностей от номера промежутка времени актуальности схемы БД общее число таблиц определяется выражением ,12 !))((! !)( )( )( )( 1      tNN tNN K KtNNK tNN tS где K — текущая арность связей групп доменов-масок, а )(tNN — общее число доменов-масок, которое зависит от t — номера промежутка времени актуальности схемы БД, на протяжении которого эта схема не претерпевает модификации. Общее же число доменов-масок определяется формулой ,),,()( ),( 1 )( 1 tjitNN tiM j tN i    где, в свою очередь, ),,( tji — признаки актуальности домена-маски. Признак актуальности — это формальный массив целых чисел, каждое из ко- торых определяется совокупностью индексов ),,,( tji и в пределах данного алго- ритма принимается или ноль, что соответствует аннулированию домена-маски, или единица, что соответствует актуальности домена-маски. Тогда i — индекс, который определяет номер сущности, )(tN — общее число сущностей-объектов на промежутке времени t, ),( tiM — число доменов-масок каждой i-й сущности- объекта на промежутке времени t, а j — индекс, который определяет номер доме- на-маски i-й сущности-объекта. Суммарное число доменов-масок для одной сущ- ности-объекта формирует внутренняя сумма. Тогда внешняя сумма формирует общее число доменов-масок. На рис. 1 приведена схема расширенного реляционного каркаса, построенно- го на булеане )(tNN масок сущностей-объектов — схема БД, которая моделирует ПрО, где 1141131121111 ,,,,, NNMKKKKK  — совокупность структурированных идентификаторов бесконечных столбцов доменов-масок, а также структура мно- гоарных отношений каждого уровня связей, которые получены путем декартова произведения доменов-масок между собой. При этом M обозначает зависимый от номера сущности-объекта индекс, который соответствует числу масок каждой сущности-объекта. Для экономии места на рисунке символ i не приведен. По этой 100 ISSN 0572-2691 же причине приведены лишь некоторые случайные таблицы бинарных связей, а также на третьем и четвертом уровнях арности таблиц вместо трехмерного идентификатора ijtK обобщенно показаны массивы ,,,,,, NDCBA  т.е. симво- лы имен сущностей-объектов, которые обобщают имена своих масок. Последнее NN-арное отношение показано с раскрытой структурой ключа. K111 K121 K131 K141  K1M1  K211 K221 K231 K241  K2M1  K311 K321 K331 K341  K3M1  K411 K421 K431 K441  K4M1   K(NN–1)11   K111 K131 K141 K341  K1M1 K4M1  K(NN–1)21 K(NN–1)31 K(NN–1)M1 KNN11  KNN21 KNN31 KNNM1   K(NN–1)11 KNN21 K(NN–1)M1 KNNM1 A, B, C A, B, C, D A, B, D  A, N–1, N  B, N–1, N  N– 2, N–1, N A, N–2, N–1, N   B, N–2, N–1, N  N– 3, N–2, N–1, N  K111, K121, K131,, K1M1, K211,, K2M1,, K3M1,, K(NN–2)M1, K(NN–1)M1, KNNM1 1, K121, K131,, K1M1, Рис. 1 Темпоральность каркасной БД Еще одно отличие описанного алгоритма заключается в структуре идентифи- катора, который может иметь единое имя для всех отношений и сквозную трех- мерную индексацию ).,,( tji Индексы имеют тот же смысл, что и в выражении общего числа доменов-масок. Каждый из индексов ключа уникально соответству- ет каждой маске каждой сущности-объекта, т.е. каждый из индексов соответству- ет своему базовому фактору алгоритма, а именно:  )(,1 tNi  — номер каждой сущности-объекта, где )(tN — общее число сущностей-объектов за t-й промежуток времени;  ),(,1 tiMi  — номер маски i-й сущности-объекта за t-й промежуток времени;  t — номер отрезка времени актуальности текущего состояния t-й модифи- кации совокупности всех ),( ji -х отношений. Таким образом, за промежуток времени t схема всей БД остается без измене- ний, т.е. не модифицируется, а на моменте времени 1t эта же совокупность от- ношений уже получает модификацию своего состояния. В такой модификации может незначительно изменяться лишь размер одного из столбцов уже существующего отношения и появляться новая группа отношений. Пользователь получает возможность самостоятельно назначать и использовать лю- бое формальное условие перехода к новому коду отрезка времени, который характеризует актуальность состояния схемы БД, а значит, к новой совокупности отношений и кортежей. Благодаря кодированию промежутков времени, на протяжении которых со- стояние структуры совокупности таблиц сохраняет актуальность, алгоритм Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 101 предоставляет возможность анализировать все слои состояний схемы БД либо от- дельно один от другого, либо в полной совокупности. Такая технология синтеза схемы БД предоставляет возможность хранения каждого отдельного t-слоя сово- купности отношений в целостном виде со всеми наработанными данными за этот промежуток времени и построить темпорально-слоевой архив данных, что суще- ственно отличается от концепции архива «кубов данных» [18, 20]. В приведенном алгоритме также не существует ограничений относительно момента добавления дополнительных доменов-масок от начальных, или даже от новых сущностей-объектов, которые проектировщик не учел на начальном этапе. Такое добавление и является упомянутой модификацией дежурного состояния схемы БД. Дополнительный «физический» смысл констант ),,( tji — это еще и факт размножения определенной маски, когда определенная константа равняется 2, 3, 4 и т.д. Это, в свою очередь, означает моделирование возможности многоразового одновременного выполнения одной сущностью-объектом одной роли, т.е. участие сущности-объекта своей одной маской в одном типе связи несколько раз. Такая ситуация не имеет аналогов в ПрО. Как уже отмечалось, используется принцип уникальности — каждая маска применяется лишь для одной роли, а в каждой роли, т.е. в каждом типе связи сущность-объект принимает участие этой маской лишь один раз. Поэтому даже рекурсивная связь произвольной арности одного и того же экземпляра сущности- объекта, которая в теории проектирования хранилищ данных считается одним из существенных противоречий ПрО, органически моделируется описываемым ал- горитмом за счет разных масок, которые принадлежат одной сущности-объекту. Тем не менее в пределах алгоритма размножение еще и масок (сугубо теоретиче- ская ситуация) не создаст существенных структурных проблем и противоречий. Описанный подход к моделированию темпоральности данных несколько от- личается от общеизвестных [21]. Результаты экспериментальных исследований В настоящей работе проведен эксперимент, основной характеристикой кото- рого является время доступа к любому атрибуту отношения-маски исследуемой БД. Как известно, самой ресурсоемкой операцией реляционной алгебры являются соединения отношений [22]. Эта операция применяется при выполнении запросов к БД без использования отношений-масок и более низкой «нормальности» — не выше 3НФ. Особенностью каркасной схемы является то, что в БД большинство исследованных связей моделируется уже соединенными отношениями, поэтому отсутствие операции соединения значительно экономит время доступа к БД. Для экспериментального исследования каркасного метода проектирования схемы БД и проведения указанного численного эксперимента выбрана ПрО «Го- родская поликлиника». Описываемое приложение БД разработано в г. Хмельниц- ком в одной из городских поликлиник с помощью CASE-генератора SWS [23] сторонними пользователями этой инструментальной системы. В работе имеется соответствующий акт внедрения. Как показано в [24, 25], само CASE-средство SWS проектировалось в строгом соответствии с каркасной моделью данных. При этом приложения БД, синтезируемые с помощью SWS и каркасной схемы БД, об- ладают высокой эффективностью. На основании алгоритмов нормализации [4] и каркасного синтеза схемы БД [1, 2] были исследованы семантика ПрО, каркасная схема БД, характеристики доступа к большим объемам данных. 102 ISSN 0572-2691 Ценность подробного разделения групп отношений на маски особенно про- является при поддержке СУБД режима реального времени [24, 25], когда прева- лирующее большинство запросов пользователей проектируется заранее. Тогда на моменте ввода любого данного в отношения, моделирующие оперативные состо- яние ПрО, запускаются фоновые процедуры синтеза всех необходимых «архив- ных» масок, в которых в режиме реального времени обновляются соответствую- щие кортежи, связанные индексами соответствующих ключей. При такой конфигурации приложения потребность в написании значительно- го объема листингов запросов, так или иначе зависящих от семантики данных, существенно снижается. Заметим, что вид каркасной диаграммы указанной ПрО полностью соответ- ствует диаграмме из работ [2, 14], поэтому здесь не приводится. Для формирова- ния унифицированного запроса к БД, возвращающего группу данных для анализа документов (артефактов), таких как «Отчет о работе регистратуры» или «Счет к оплате больному», применяется единственная операция — выборка из отношения. Причем все соединения схемы БД, сформированы не по факту выполнения запро- са пользователя к БД, а по факту внесения текущих оперативных данных [24, 25]. Запросы могут быть сформулированы на естественном языке. Например: «выбрать группу категорий посетителей за все месяцы конкретного года, обслу- женных в конкретном отделении конкретной поликлиники, показатели анализов которых не превышали бы такой-то величины». А также: «выбрать все счета к оплате за текущий месяц текущего года, по которым для конкретной категории посетителей в произвольных подразделениях конкретной поликлиники разными врачами и в разные смены скидки-надбавки были бы не выше указанных». В экспериментальной схеме БД синтезировано 125 каркасных отношений. Скорость доступа к данным по типовым запросам повысилась на несколько по- рядков по сравнению со схемой, разработанной в соответствии с алгоритмом нормализации Кодда [4]. 0,5 1,0 1,5 2,0 2,5 3,0 3,5 0 1 2 3 4 5 6 z t 2 1 10 20 30 40 50 60 0 1 2 3 4 5 6 z t 2 1 а б Рис. 2 На рис. 2, а приведены графики роста времени доступа (в мс) к данным при получении одной записи из увеличивающихся пачек записей при запросе на со- единение четырех 3НФ-отношений (кривая 2) и заметно меньший прирост време- ни на индексную выборку этой же записи из одного бинарного отношения в ДКНФ (кривая 1) при таком же увеличении числа записей. Рис. 2, б иллюстрирует еще меньший прирост времени доступа к декарному отношению в ДКНФ (кривая 1) с увеличением числа обрабатываемых записей и значительный рост времени выполнения этого же запроса при соединении 12 отношений в 3НФ (кривая 2). При этом результирующее отношение аналогич- но примеру 1 имело в среднем от 100 до 200 кортежей. Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 103 Заключение Таким образом, каркасная модель данных позволила обнаружить следующие основные совпадения описанного подхода с классическими результатами: 1) модель «сущности-связи» [11]; 2) частичные копии сущностей-объектов [10, 13, 15] 3) дизъюнктивно-нормальная форма в логике: «дизъюнкция конъюнкций» [26]; 4) булеан как семантика в реляционной модели данных [27]; 5) булеан как модель поведения сложных систем [28]; 6) ДКНФ-схема и модифицируемость [3]; 7) денормализация, рост скорости доступа [6, 29]; 8) CASE «МикроПоиск» [30]. Назовем основные отличия каркасного подхода. В схеме БД не найдется ни одного отношения (кроме некоторых «хелпер-таблиц»), в котором существовало бы больше одного ключа. Единственный ключ отношения выполняет несколько функций — семантику данных, целостность данных, связь между таблицами, до- ступ к данным. Каркасная совокупность отношений является одновременно и оперативной БД, и исторически-архивным хранилищем данных. Схема каждого отношения находит- ся в форме нормализации не ниже 5НФ, а большинство отношений — в ДКНФ. Ре- структуризация схемы БД в направлении повышения эффективности работы при- ложения выполняется так, чтобы нормализация каждого отношения не уменьша- лась (денормализация), а повышалась. Все перечисленное дает возможность решить проблему унификации, типиза- ции и минимизации системы управления базой данных. Такой подход минимизи- рует потребность в ресурсоемких операциях соединения в большинстве запросов к БД и существенно упрощает настройку приложения. Б.Є. Панченко РЕКУРСИВНІ ЗВ’ЯЗКИ ТА ТЕМПОРАЛЬНІСТЬ У РЕЛЯЦІЙНОМУ КАРКАСІ — МАСКИ СУТНОСТЕЙ-ОБ’ЄКТІВ У відповідності до нової моделі даних — реляційного каркаса — неформально описано алгоритм врахування рекурсивних зв’язків сутностей-об’єктів в пред- метній області. Алгоритм застосовується для більш точного проектування схем реляційних баз даних (БД). Для цього запропоновано механізм каркасного син- тезу часткових копій атрибутів, що беруть участь у різних ролях сутностей- об’єктів. Запропоновано також новий підхід до моделювання темпоральних да- них. Наведено результати числового експерименту доступу до БД. B.Ye. Panchenko RECURSIVE RELATIONS AND TEMPORALITY IN THE RELATIONAL FRAMEWORK — THE MASKS OF ENTITY-OBJECTS In accordance with a new data model — relational framework — an algorithm of recognition of recursive relations of entity-objects in a subject domain is informally described. The algorithm is used for precise designing of schemes of relational data- bases (DB). For this, we offer a mechanism of framework synthesis of partial attrib- utes’ copies that take part in various roles of entity-objects. We also offer a new ap- 104 ISSN 0572-2691 proach to designing temporal data. Results of a numerical experiment of DB access are given. 1. Панченко Б.Е. Каркасное проектирование доменно-ключевой схемы реляционной базы данных // Кибернетика и системный анализ. — 2012. — № 3. — C. 174–187. 2. Панченко Б.Е. Алгоритм синтеза реляционного каркаса. Неформальное описание // Между- народный научно-технический журнал «Проблемы управления и информатики». — 2013. — № 1. — С. 83–103. 3. Алтайбек А.А. Проектирование баз данных на основе доменно-ключевой нормальной фор- мы // Вестник КазНУ. — Алматы, 2009. — № 1. — C. 111–118. 4. Codd E.F. The relational model for database management, vers. 2, reading mass. — New York : Addison-Wesley Publ. Co, 1990. — 538 p. 5. Вендров А.М. CASE-технологии: Современные методы и средства проектирования инфор- мационных систем. — М. : Финансы и статистика, 1998. — 176 с. 6. Кунгурцев А.Б., Зиноватная С.Л. Анализ целесообразности реструктуризации базы данных методом введения нисходящей денормализации // Тр. Одес. политехн. ун-та. — Одесса : ОНПУ, 2006. — 1(25). — С. 104–108. 7. Пат. 92248. Способ обобщенного размещения данных с учетом модифицируемости структу- ры хранилища / Б.E. Панченко // Промислова власність. — 2010. — № 19. — C. 3.131–3.132. 8. Fagin R. Normal forms and relational database operators // Proc. ACM SZGMGD, 1979, — P. 153–160. 9. Fagin R. A normal form for relational databases that is based on domains and keys // ACM Transactions on Database Systems. — 1981. — 6, N 3. — P. 387–415. 10. Диго С.М. Базы данных. Проектирование и создание. — М. : Изд. центр ЕАОИ, 2008. — 171 с. 11. Chen P.P. The entity-relationship model: toward a unified view of data // ACM Trans. on Data- base Systems. — 1976. — 1, N 1. — P. 9–36. 12. Панченко Б.Е. Об алгоритме синтеза реляционного каркаса. Постановка задачи и формали- зация // Компьютерная математика. — 2012. — № 1. — С. 84–93. 13. Mullins S.C. Denormalization guidelines. — http://www.tdan.com/view-articles/4142/. 14. Панченко Б.Е. К вопросу о модифицируемости и безаномальности схемы реляционной ба- зы данных // Проблемы программирования. — 2012. — № 2–3. — С. 281–288. 15. SQL server performance and tuning guide: database design and denormalizing for performance, chapter 2. — http://www.lcard.ru/~nail/sybase/perf/1088.htm. 16. Codd E.F. Extending the database relational model to capture more meaning // ACM Transact. on Database Systems. — 1979. — 4, N 4. — P. 397–434. 17. Филиппович А.Ю. Принципы взаимных функциональных зависимостей // Интеллектуаль- ные технологии и системы. — 2002. — Вып. 4. — C. 222–241. 18. Kimball R. The data warehouse toolkit: practical techniques for building dimensional data ware- houses. — New York: John Willey & Sons, 1996. — 491 p. 19. Bernstein P.A. Synthesizing third normal form relation from functional dependencies // ACM Transact. on Database Systems. — 1976. — 1, N 4. — P. 277–298. 20. Inmon W.H. Building the data warehouse. — New York : John Willey & Sons, 2002. — 412 p. 21. Когаловский Р.М. Расширение реляционной модели для баз данных временных рядов // Управляющие системы и машины. — 1994. — № 6. — С. 24–30. 22. Ульман Д.Д., Уидом Д. Основы реляционных баз данных. — М. : Мир, 2006. — 374с. 23. Панченко Б.Е., Гайдабрус В.Н., Церковицкий С.Л. CASE-генератор прикладных сетевых информационных комплексов — инструментальная система SWS 1.0 // Свидетельство об официальной регистрации программы для ЭВМ № 940165. — М. : РосААП, 1994. — 2 с. 24. Панченко Б.Е., Гайдабрус В.Н., Церковицкий С.Л. Сетевые вычислительные комплексы // Компьютеры плюс программы. Спец. выпуск. — Киев, 1994. — С. 30–37. 25. Панченко Б.Е. Исследования доменно-ключевой схемы реляционной базы данных // Ки- бернетика и системный анализ. — 2012. — № 6. — С. 157–172. 26. Яловец А.Л. Представление и обработка знаний с точки зрения математического моделиро- вания. Проблемы и решения. — Киев : Наук. думка. — 2011. — 360 с. 27. Abiteboul S., Beeri C. On the power of languages for the manipulation of complex values. (Techn. rep.) — Cadex (France): INRIA, 1995. — 80 p. 28. Степанов А.И. Число и культура. — М. : Языки славянской культуры, 2004. — 832 с. 29. Пуле М. Денормализация: как нарушить правила и избежать последствий. — http://www. sqlmag.com/article/data-modeling/responsible-denormalization. http://www.tdan.com/view-articles/4142/ http://www.lcard.ru/~nail/sybase/perf/1088.htm Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 105 30. Перевозчикова О.Л., Тульчинский В.Г., Коломиец А.В. и др. Высокопродуктивные методы анализа и спецификации пространств атрибутов предметной области для организации вы- числений (Отчет о НИР № 0107U000800 ВФ.145.09.11). — Киев, 2011. — 378 с. Получено 17.12.2012 Статья представлена к публикации акад. НАН Украины А.А. Летичевским.

Рекурсивные связи и темпоральность в реляционном каркасе — маски сущностей-объектов

Репозитарії

Схожі ресурси