автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Методы и средства обеспечения целостности данных в автоматизированных системах организационного управления

ВВЕДЕНИЕ.

1. ОБЕСПЕЧЕНИЕ ЦЕЛОСТНОСТИ ДАННЫХ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ.

1.1. Требование достоверности и причины возникновения ошибок в данных

1.2. Достоверность и целостность данных.

Методы обеспечения целостности.

1.3. Современные концепции проектирования автоматизированных систем

1.4. Открытые проблемы проектирования и использования средств обеспечения целостности.

Выводы.

2. ПОСТРОЕНИЕ И АНАЛИЗ БАЗ ДАННЫХ, СВОБОДНЫХ

ОТ АНОМАЛИЙ КОРРЕКТИРОВОК

2.1. Анализ аномалий корректировок.

2.2. Постановка и решение задачи проектирования концептуальной схемы базы данных

2.3. Постановка и решение задачи проектирования концептуальной схемы базы данных при ограничениях на внешние схемы.

2.4. Ликвидация аномалий корректировок при проектировании баз данных минимальной избыточности.

Выводы.

3. АВТОМАТИЗАЦИЯ ПРОГРАММИРОВАНИЯ СРЕДСТВ

ОБЕСПЕЧЕНИЯ СЕМАНТИЧЕСКОЙ ЦЕЛОСТНОСТИ.

3.1. Построение концептуальной модели правил целостности.

3.2. Анализ языков описания правил целостности

3.3. Язык концептуального описания правил целостности ЛИРА.

3.4. Методика проектирования инструментальных средств обеспечения целостности

Выводы.

4. РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ СРЕДСТВ ОБЕСПЕЧЕНИЯ

ЦЕЛОСТНОСТИ.

4.1. Программное обеспечение систем генерации программ контроля.

4.2. Реализация инструментальных средств генерации программ контроля в системе ИНЕС

4.3. Практическое применение ППП "СОЦ-ИНЕС"

4.4. Применение методики проектирования баз данных в "Автоматизированной библиотечной системе" МИФИ.

Выводы.

В основных направлениях развития народного хозяйства СССР на I98I-I985 гг. и на период до 1990 г. предусмотрено обеспечить дальнейшее ускорение научно-технического прогресса и совершенствование управления экономикой, В директивных документах ноябрьского (1982 г.)» июньского (1983 г.) Пленумов ЦК КПСС, в постановлении ЦК КПСС и Совета Министров СССР "О мерах по ускорению научно-технического прогресса в народном хозяйстве" эти задачи конкретизируются и подчеркивается необходимость существенного повышения производительности труда во всех сферах народного хозяйства. В связи с этим в статьях Г.И.Марчука [32] и А.П.Александрова [i] отмечается необходимость повышения эффективности воздействия достижений науки на темпы роста экономики страны и подчеркивается, что одной из главнейших задач является широчайшее использование в народном хозяйстве средств автоматизации. Один из путей решения поставленной задачи состоит в разработке автоматизированных систем управления (АСУ), среди которых важное место занимают автоматизированные системы организационного управления (АСОУ). Любая АСУ ".органически включает автоматизированную систему обработки данных (АСОД), главной целью которой является автоматизация процессов сбора, переработки информации и усовершенствование формы и организации их выполнения" [20].

Одним из основных требований, предъявляемых к АСОД, является обеспечение достоверности обрабатываемых данных. Разработкой методов и средств обеспечения достоверности данных занимались многие советские ученые: Будзко В.И., Дмитриев Н.И., Куцык Б.С., Пепеля-ев А.Н., Селетков С.Н., Шураков В.В. и другие, а также их зарубежные коллеги: Дейт К., Дэвенпорт Р., Кодд Е., Майерс Г., Маклеод Д., Хоффман Л. и другие.

Важность проблемы обеспечения достоверности данных и влияние ошибок, приводящих к снижению уровня достоверности, целесообразно проиллюстрировать следующими цитатами [30] : "Поскольку обработка данных затрагивает нашу жизнь во все большей степени, ошибки ЭВМ могут теперь иметь такие последствия, как нанесение материального ущерба, нарушение секретности, оскорбление личности и даже смерть. Ошибка в единственном операторе программы на Фортране привела к неудаче при первом запуске американского исследовательского корабля на Венеру. Что хуже всего, ошибки в медицинском программном обеспечении явились причиной нескольких смертных случаев, а ошибки при проектировании самолета вызвали несколько серьезных авиакатастроф".

Отличительной особенностью АСУ одиннадцатой пятилетки является ориентация их работы на машины третьего поколения и использование при разработке систем новых методов, основанных на концепции банков данных. В настоящее время проблематика проектирования, внедрения и эксплуатации автоматизированных банков данных (АБД) является центральной при разработке АСОД. В основе АБД лежит принцип максимальной независимости программной реализации функциональных задач от организации и состава информационной базы. От простых файловых систем к автоматизированным банкам данных, и далее, к распределенным банкам данных - вот шаги прогресса в развитии архитектуры систем обработки данных, вызванные как развитием технической базы от ЭВМ второго поколения к мощным вычислительным системам третьего поколения, так и формированием основ теории систем обработки данных и практикой их функционирования.

Указанные изменения архитектуры систем обработки данных потребовали принципиальных изменений в архитектуре систем управления базами данных (СУБД): от архитектуры систем управления данными ОС ЕС ЭВМ [il], к архитектуре, предложенной комитетом КОДАСЙЛ [17,35] и, наконец, к архитектуре, предложенной комитетом ANSI / SPARC

78,80] • Появление последней обусловлено созданием большого числа СУБД, поддерживающих различные модели данных, и неочевидностью выбора СУБД для конкретной системы обработки данных. Уровень проектирования АСОД, независящий от конкретной, реализованной в рамках определенной СУБД, модели данных, называют концептуальным уровнем.

В настоящее время появилось большое число работ, посвященных методам концептуального проектирования [6,73,25,12,71,80],и в некоторых из них отмечается привлекательность реляционного подхода к описанию концептуального проекта системы [ .6, ,12,73] . Однако в этих работах недостаточно исследованы вопросы языкового представления на концептуальном уровне требований к достоверности данных, а также способам автоматизированного погружения этих требований в реально существующие СУБД. Здесь важно отметить, что ".существеннейшей научно-технической задачей является создание вычислительной техники и автоматизации очень высокой надежности. . Изготовление программных средств должно быть, как и в космической технике, в значительной степени автоматизировано и приспособлено к автоматическим системам поиска ошибок. Это сложные технические задачи, но их обязательно нужно решить" [i],

В настоящей работе ставятся открытые вопросы концептуального описания требований к достоверности данных и автоматизированного проектирования программной компоненты, предназначенной для обеспечения контроля данных в АСОД.

Диссертация состоит из введения, четырех глав, заключения и приложения.

Выводы

1. Для удовлетворения требований пользователей к достоверности данных необходимо разрабатывать комплекс организационно-программных средств обеспечения целостности.

2. При современном подходе к проектированию автоматизированных систем вопросы обеспечения целостности должны быть решены на концептуальном уровне.

3. С целью создания средств концептуального описания проектных решений по обеспечению целостности необходимо: а) исследовать методы проектирования баз данных, свободных от аномалий корректировок,и дать практические рекомендации по проектированию концептуальных схем баз данных; б) построить и исследовать модели семантических правил целостности.

Практически ценной и актуальной является разработка языка описания правил целостности и трансляторов (препроцессоров) с него в языки существующих СУБД.

ГЛАВА 2. ПОСТРОЕНИЕ И АНАЛИЗ БАЗ ДАННЫХ,

СВОБОДНЫХ ОТ АНОМАЛИЙ КОРРЕКТИРОВОК

Как отмечалось в главе I, одной из актуальных проблем обеспечения целостности данных в автоматизированных системах является проблема концептуального проектирования баз данных, свободных от аномалий корректировок. Отсутствие аномалий корректировок означает, что любое преобразование внешний-концептуальный может быть описано средствами языка манипулирования данными. Возможность такого описания существенно зависит от вида концептуальной схемы базы данных. Поэтому при разработке концептуального проекта системы необходимо таким образом спроектировать концептуальную схему базы данных, чтобы при работе с базой данных не было аномалий корректировок.

В данной главе дана постановка задачи проектирования концептуальной схемы базы данных и рассматриваются методы ее решения. Поставлена и решается задача проектирования концептуальной схемы при заданных ограничениях на внешние схемы.

2.1. Анализ аномалий корректировок

Для более ясного понимания проблемы устранения аномалий корректировок при проектировании концептуальной модели базы данных, целесообразно детализировать введенные в главе I составные части концептуального проекта системы: концептуальных моделей обработки данных и данных пользователя.

Рассмотрим концептуальную модель АСОД, приведенную на рис. 2.1 и показывающую информационные процессы будущей системы без привязки к конкретному техническому комплексу, ЭВМ, СУБД и т.п. Данная концептуальная модель АСОД согласуется с архитектурой перспективных СУБД [ 12,80] и допускает использование существующих систем управления базами данных, выбор которых, как бьио показано в п. 1.3, осуществляется на этапе рабочего проектирования. Приведенные на рис. 2.1 схемы исходных, выходных, внешних и внемашинных данных являются частями описания концептуальной модели данных пользователя, а приведенные преобразователи - частями описания концептуальной модели обработки данных. Схемы исходных и выходных данных представляют собой описания данных на машинных носителях, вводимых и выводимых из ЭВМ соответственно, с которыми работает конечный пользователь. Это могут быть входные и выходные документы системы, сообщения и указания, выдаваемые на терминалы, директивы пользователя и т.п.

Внешние схемы представляют собой описание взглядов пользователей на базу данных и могут существенно отличаться от схем исходных и выходных данных, с которыми непосредственно работает конечный пользователь. Это отличие может быть как по составу данных, так и по формам их представления. Например, в схеме выходных данных могут присутствовать описания производных показателей, вычисляемых на основе хранимых в базе данных.

Все внешние схемы в дальнейшем будем разделять на два основных класса: Vi - множество внешних схем вывода и Vg - множество внешних схем ввода.

Концептуальная схема базы данных является описанием представления общего информационного содержания базы данных (концептуальной модели базы данных), независимым от структуры хранения или стратегии доступа.

Преобразователи "исходный-внешний" и "внешний-выходной" включают в себя алгоритмы редактирования, алгоритмы вычисления производных показателей и правила целостности, описывающие ограничения на обрабатываемые данные и реакцию системы на возникновение ошибок в данных.

Гшмгшм/м

M/X 4ДШ/Х

T * А fpWp/TW/rfflk exwffr/tw шх4/г//шх

JtifWMfS /гмш£/г-гми /7 £02) I

J^fMtfw**'* i lit -1

L-iteMSfx^

В отличие от них преобразователи "внешний-концептуальный" и "концептуальный-внешний" не касаются изменений состава и формы представления данных, а описывают только структурные изменения данных при работе с базой. Для описания преобразований "концептуальный-внешний" и "внешний-концептуальный- используется подъязык данных, который ориентирован на запоминание данных в базе данных и выборку их из нее.

В п. 1.3 отмечалась целесообразность использования для описания концептуального проекта системы реляционного подхода.

В настоящее время предложено большое многообразие реляционных языков манипулирования данными [14,57,60,70] . Их разделяют на следующие основные классы: алгебры отношений, исчисления предикатов и языки отображений [57]. В дальнейшем для записи цепочек преобразования данных будет использоваться нотация реляционной алгебры Кодда [ 60].

В работе Кодда [60] доказана полнота реляционной алгебры для вывода отношений из базы данных. Описание преобразования "внешний-концептуальный" может быть записано не для любой внешней схемы и возникновение такой ситуации принято называть аномальным эффектом корректировок, причем существование аномалий корректировок зависит от вида концептуальной схемы базы данных. Концептуальная схема базы данных должна быть спроектирована таким образом, чтобы аномалии корректировок отсутствовали.

Рассматривать постановку и решение задачи проектирования концептуальной схемы базы данных, свободной от аномалий корректировок, будем для двух случаев: а) когда необходимо обеспечить принципиальную возможность преобразования "внешний-концептуальный" для произвольной внешней схемы ввода; f : н С sr.-'l-tf": ссср * б) когда все внешние схемы известны и концептуальная модель обработки данных практически не изменяется в цроцессе функционирования автоматизированной системы обработки.

Один из подходов к проблеме проектирования концептуальной схемы основан на концепции универсального отношения, последовательная декомпозиция которого позволяет построить модель данных, свободную от аномалий [ 12,61,65 ] . При этом необходимо, чтобы при переходе от одной схемы к другой была обеспечена эквивалентность преобразований. Определим понятие эквивалентности. Пусть заданы две схемы:

S0=R0(U0) И S-jRiCUi.), i=i,2,.,p}.

В соответствии с [14] будем считать схемы S0 и S эквивалентныр ми, если они содержат одинаковые атрибуты U0=UUt и схема S

1=1 обладает по отношению к схеме So свойством соединимости без по- р — терь (то есть для любого R схемы S верно R0= .^RltUi), где R0 - экземпляр отношения R0 , а {1 = 1,2, .,р} -множество экземпляров отношений со схемой S , * - операция естественного соединения). Эквивалентность схем So и S будем в дальнейшем обозначать так: S ~ S0 . При решении проблемы устранения аномальных эффектов корректировок базы данных важную роль играют такие два класса свойств отношений как функциональные и многозначные зависимости. Приведем определения этих зависимостей [52,74].

Определение I.' Пусть X,Y - множества атрибутов из

U = {Ai,A 2,.,Aq); X,Y£U.

Говорят, что в отношении R существует функциональная зависимость Y от X , если в любой момент времени каждому значению X соответствует только одно значение У.

Функциональную зависимость будем обозначать следующим образом:

X-*Y , где X называется детерминантной).

Определение 2. Пусть X,Y,Z sU и Z=U-XY , где ХПУ^О или X0Y= 0.

Определим множество

Говорят, что в отношении "R существует многозначная зависимость Y от X, если для каждой xz - величины совокупности атрибутов XZ в любой момент времени

Yk(xz)=Yr(X). Неформально говорят, что существует многозначная зависимость Y от X в отношении, если множество значений атрибута Y , которое появляется в £ с заданным значением х атрибута X не зависит от величины любого другого атрибута, или иначе совокупность значений атрибута Y, появляющаяся в кортежах отношения "R с заданным значением х атрибута X , появляется с любой комбинацией значений х и Z , ocz eRtXZ] (многозначная зависимость обозначается следующим образом: X Y ). Для функциональных зависимостей определены и доказаны следующие свойства [521:

1. Если X ->Y , то XZ Y (свойство дополнения);

2. Если X и Y-^Z , то X Z (свойство транзитивности);

3. Если X , то X->Y (свойство рефлексивности);

4. Если X-^YZ , тоХ^-Y иХ-^-Z (свойство декомпозиции).

Для многозначных зависимостей определены и доказаны следующие свойства [74]:

1) Если XYZ = U и YDZsX , то X-»Y тогда и только тогда, когда Х-***- Z (свойство дополнения).

2) Если Y s X, то X Y (свойство рефлексивности).

3) Если X Y и , то X->^Z-Y (свойство транзитивности).

4) Если Xи то XY^Y^ , X-» Y2 - Yi и X (свойство декомпозиции).

В литературе [ 12,61 ] показано, что устранение в отношениях неполных и транзитивных функциональных и многозначных зависимостей позволяет устранить аномальные эффекты корректировок. Существование аномальных эффектов корректировок базы данных и взаимосвязь аномалий корректировок с приведенными свойствами функциональных зависимостей можно цроиллюетрировать на примерах. Предположим построена КМБД "БИБЛИОТЕКА" со схемой R0(#MC , КАФ, ФАК, ТЕЛ, #NK , А - Н) (экземпляр отношения Ro приведен на рис. 2.2). Названия атрибутов имеют следующий смысл (символ # указывает, что атрибут является частью первичного ключа отношения): #NC - номер сотрудника, КАФ - номер кафедры, на которой он работает, ФАК - шифр факультета, к которому кафедра относится, ТЕЛ - телефон сотрудника, #NK - номер книги в библиотеке, А - Н - сведения об авторах и названии книги.

Для отношения "R0 множество функциональных зависимостей имеет вид:

1)#NC КАФ, ФАК, ТЕЛ;

2) -*» А - Н;

3) КАФ ФАК;

4) #NG,#MK КАФ, ФАК, ТЕЛ, А - Н.

Из приведенного списка зависимостей видно, что в отношении имеются неполные функциональные зависимости (атрибуты ТЕЛ, КАФ, ФАК, А - Н функционально неполно зависят от ключа ШС ) и транзитивная зависимость (атрибут ФАК транзитивно зависит от атрибута #NC ). Аномалия корректировки отношения JR0, связанная с существованием в R0 неполных функциональных зависимостей, проявляется

9м ГМ

A/4 /V3 A/1 A/2 22 12 4 - ' 22 12 /С r rt T2 ГЗ T4 T2 Ж 4 //4 *3 XI M3 Д с 3 С ш

М0 Г£/Г

22 п

А/г 42 тг

А/3 4 гз f/C ФУ/г а/4 Х4 a/z Х4

А/3 МЗ а/4 кг а/г МЗ рм

22 X

42 X i г

ФМг я-// м //

42 3

АГЗ с

2.2. /7рмм£/> MfiAffJt/sw/tf в том,что невозможно ввести в отношение сведения о сотруднике до тех пор, пока он не возьмет в библиотеке хотя бы одну книгу. Соответственно и сведения о книге не могут быть введены в отношение до тех пор, пока ее не возьмет из библиотеки кто-нибудь из сотрудников.

Если представить БД в виде трех отношений (рис. 2.2), то можно заметить, что отмеченного аномального эффекта не будет.

Множество У для R^R^R^R'} имеет вид:

1) ШС -> КАФ, ФАК, ТЕЛ;

2) ЙШК А - Н;

3) КАФ ФАК.

Причем в Ф отсутствуют неполные функциональные зависимости. Однако, для отношения R* имеет место аномальный эффект, связанный с существованием транзитивной зависимости. Невозможно ввести в R* сведения о том, что с конкретным значением кафедры связано конкретное значение факультета до тех пор, пока нет сведений хотя бы об одном сотруднике, работающем на этой кафедре. Если БД представить в виде 4-х отношений (рис. 2.2), то такого аномального эффекта не буцет. Множество ^ для R имеет вид:

1)Ш1-*КАФ, ТЕЛ;

2)4ШК-*А - Н;

3) КАФ -> ФАК.

Причем транзитивные и неполные функциональные зависимости отсутствуют. Однако, при корректировке отношения R" имеет место аномальный эффект, связанный с существованием в R" декомпозиционных зависимостей. Нельзя ввести сведения о сотруднике до тех пор, пока неизвестен или отсутствует номер его телефона. Если представить БД в виде R я {1^,1*2 «ЬзДЪийв К то такого аномального эффекта не будет. Множество $ для R имеет вид:

1)4ШС ТЕЛ;

2)#NC КАФ;

3) # КАФ ФАК;

4)#NK-^A - Н.

Причем в R отсутствуют транзитивные, неполные и декомпозиционные функциональные зависимости. Можно заметить, что КМБД при этом состоит из отношений, на каждом из которых существует только одна функциональная зависимость.

Рассмотрим еще один пример. Схема отношения, в котором хранятся сведения об абитуриентах вуза, имеет вид:

АБИТ (#NA , ФИО, МП, МУ, ФЗ, ЛП), где ФИО - фамилия, имя, отчество абитуриента,#NA - системный номер;

МП, МУ, ФЗ, ЛП - имена атрибутов, обозначающие оценки, которые абитуриент получил на вступительных экзаменах по соответствующим предметам;

МП - математика (письменно);

МУ - математика (устно);

ФЗ - физика;

1. Определение 3. Аномальный эффект корректировки, который может возникать только при существовании в отношении неполных функциональных зависимостей, назовем аномальным эффектом свойства дополfнения функциональных зависимостей и обозначим Адоп.

2. Определение Аномальный эффект корректировки отношения, который может быть только при существовании в отношении транзитивнойфункциональной зависимости, назовем аномальным эффектом свойстваfтранзитивности функциональных зависимостей и обозначим его Атрн.

3. Определение 6. Аномальный эффект корректировки отношения, который может присутствовать только при наличии в отношении неполных многозначных зависимостей, назовем аномальным эффектом свойствадМдополнения мнргозначных зависимостей и обозначим его Адоп.

4. Постановка и решение задачи проектирования концептуальной схемы базы данных

5. Формальная постановка задачи проектирования концептуальной схемы базы данных (КСБД), свободной от аномалий корректировок будет иметь вид:1. Пусть задано:а) Концептуальная схема универсального отношения:

6. So = Ro^o) » где Uo множество имен атрибутов;б) множества ? = и M = {mj}, j€ l,k , где У множество функциональных зависимостей на "R0,

7. М множество многозначных зависимостей на R0.

8. Требуется спроектировать концептуальную схему базы данных S={Ri(Ut), р}, такую, что в) S-S0,г) ттип | S |,д) для Vv,| , 3Q3(Uj,S), j€if|Vg|f |-Uj6V2где Uj внешняя схема ввода;

9. Vg- множество произвольных внешних схем ввода; Qj(.Uj,S) преобразование "внешний-концептуальный", записанное в нотации алгебры кодда.

10. Кодд и Бойс .12,591 предложили следующее решение задачи проектирования КСБД:

11. Пусть даны следующие определения.

12. Определение 9. Элементарной многозначной зависимостью называется зависимость вида: {AtpA^,., А^} -» А'ц , где

13. U I = { 1,2,.,п} , 1^12 = 0.

14. Определение 10. Ключом отношения называется множество

15. K = {Ai1,Aia,., Ац., М*,., 4е ^ •которое однозначно идентифицирует кортеж отношения и при удалении любого атрибута Ац € К данное свойство разрушается.

16. Тогда решение будет иметь вид.1. Решение Б.

17. Каждое отношение базы данных должно находиться в 1НФ и вструктуре многозначных зависимостей имеются только элементарные многозначные зависимости и/или такие многозначные зависимости, что левая часть любой из них является ключом отношения.

18. Решение Б) называют приведением отношений базы данных к Четвертой Нормальной Форме (4НФ). Следует отметить, что такое решение задачи позволяет устранить все аномальные эффекты, кроме аномального эффекта свойства декомпозиции функциональных зависимостей.

19. Каждое отношение базы данных должно находиться в 1НФ и в структуре зависимостей на El существуют только элементарные функциональные или элементарные многозначные зависимости.

20. Из таблицы 2.1 видно, что чем выше уровень нормализации, тем меньше аномальных эффектов корректировок базы данных. Причем все1. Нормальные формы

21. Аномальные эффекты корректировки

22. Аномальный эффект свойства дополнения

23. Аномальный эффект свойства транзитивности

24. Аномальный эффект свойства многозначных зависимостей

25. Аномальный эффект свойства декомпозиции1НФ + + + +2НФ + + +1. ЗНФ + +4.НФ - + VJ11. КНФ