А. В. Брешенков Проектирование баз данных на основе информации табличного вида Допущено в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки диплом
| Вид материала | Диплом |
Содержание8.3. Исследование методики преобразования информации табличного вида в реляционные базы данных |
- Учебное пособие Допущено Министерством образования Российской Федерации в качестве, 2582.59kb.
- Д. В. Андреев Программирование микроконтроллеров mcs-51, 2064.3kb.
- И. В. Борискина, А. А. Плотников, А. В. Захаров проектирование современных оконных, 1699.55kb.
- «История нового времени», 4001.1kb.
- Учебное пособие. 3-е изд., испр и доп, 125.38kb.
- М. В. Ломоносова Хрестоматия по истории государства и права зарубежных стран, 11295.75kb.
- В. В. Крупица Личность Коллектив Стиль отношений (социально-психологический аспект), 4876.34kb.
- И. М. Синяева, В. М. Маслова, В. В. Синяев сфера, 5230.77kb.
- И. К. Корнеев информационная безопасность и защита информации учебное пособие, 7667.6kb.
- Курслекций допущено умо по образованию в области социальной работы в качестве учебного, 2178.14kb.
8.3. Исследование методики преобразования информации табличного вида в реляционные базы данных
Преобразование ИТВ в РБД, как видно из вышесказанного, представляет собой сложный итерационный процесс, включающий в себя ряд шагов от преобразования таблиц ИТВ к реляционному виду до построения РБД, удовлетворяющей требованиям непротиворечивости, минимальности, целостности. В зависимости от промежуточных результатов преобразования, а также целей проектирования РБД отдельные человеко–машинные процедуры могут повторяться и выполняться параллельно Так, например, в процессе нормализации таблиц ИТВ могут назначаться ключевые поля и формироваться связи между таблицами. Эти действия в соответствии с методикой преобразования ИТВ к РБД реализуются и как самостоятельные этапы проектирования РБД на основе ИТВ, которые непосредственно не связаны с этапом нормализации таблиц ИТВ. Для исследования характеристик методики автоматизированного проектирования РБД на основе использования существующей информации табличного вида, а также для исключения принципиальных ошибок в системах проектирования на ранних этапах ее разработки оправданно создание формальной модели интерактивного взаимодействия разработчика и системы для совместного решения проектных задач. Также оправданно использование для этих целей специализированного математического аппарата.
Задачами исследования, решение которых должна обеспечить модель и математический аппарат, являются выявление и исключение ситуаций, приводящих к зацикливанию процесса интерактивного взаимодействия, выявление и исключение недостижимых ситуаций интерактивного взаимодействия, анализ функциональной полноты проекта системы, предварительный анализ временных характеристик системы. При этом модель должна отражать асинхронные процессы, предоставлять возможность моделирования протекания параллельных процессов и абстрагироваться от разделения ролей между разработчиком БД, между системой специальных содержательных вопросов и между операциями ввода – вывода. В качестве аппарата формализации, полностью удовлетворяющего сформулированным требованиям, выбран аппарат сетей Петри. Согласно [17] сети Петри ”идеально удовлетворяют требованиям представления интерактивных процессов”.
В связи со значительным объемом разрабатываемых средств детальное описание и исследование всех человеко-машинных процессов, возможных при решении задач преобразования ИТВ к РБД, затруднительно. Однако задача упрощается в связи с существованием однотипных процессов и процессов с небольшим числом состояний, исследование которых не представляет интереса. В частности, вероятно, не следует включать в модель все 4-е методики нормализации реляционных таблиц, все 4-е методики формирования связей между реляционными таблицами.
Начальный уровень представления интерактивного взаимодействия в процессе преобразования ИТВ к РБД в форме сети Петри разработан на основе динамической модели (рис. 8.2.11).
Рис. 8.3.1. Сеть Петри соответствующая динамической модели преобразования ИТВ в РБД
На рис. 8.3.1 приведена сеть Петри, соответствующая динамической модели. Модели ИТВр, модели РБДр, СО, СП ставятся в соответствие положения сети Р. Операторам ОП, ОПР ставятся в соответствие переходы сети t. Имена положений и переходов сети Петри соответствуют номерам компонент динамической модели.
Сеть Петри представляется тройкой P = Р, Т, Р, где
Р – множество положений;
Т – множество переходов;
Н – множество маркеров.
С помощью построенной модели можно выполнить анализ устойчивости сети, или анализ способности отражать реальные процессы интерактивного взаимодействия разработчика и автоматизированных средств в ходе проектирования РБД на основе существующей ИТВ.
Сеть Петри является устойчивой, если она имеет потоковое назначение i 0 для каждого T ti, где потоковое назначение – это функция, которая приписывает каждому переходу T ti положительное рациональное число, называемое ее потоком [18]. Потоковое назначение для сети Петри должно удовлетворять требованиям:
- каждая дуга переносит поток, равный потоку перехода, к которому присоединена эта дуга;
- для каждого положения сумма потоков входных дуг должна равняться сумме потоков выходных дуг.
Пусть для каждого перехода сети рис. назначен поток i. Для каждого положения Pi запишем уравнения потоков, которые не должны противоречить друг другу, если данная сеть устойчива. Уравнения сведены в таблицу табл. 8.3.1.
Т а б л и ц а 8.3.1
| | t1 | t2 | t3 | t4 | t5 | t6 | t7 | t8 | t9 | t10 | |
| Р1 | -1 | | | | | -6 +6 | | | | | =0 |
| Р2 | +1 | | | | | -6 | | | | | =0 |
| Р3 | | +2 -2 | +3 | -4 | | | | | | | =0 |
| Р4 | | -2 | | +4 | | | | | | | =0 |
| Р5 | | | +3 -3 | | -5 | | | +8 | | | =0 |
| Р6 | | | -3 | | +5 | | | | | | =0 |
| Р7 | | | | | | -6 +6 | -7 | | | | =0 |
| Р8 | | -2 | -3 | | | | +7 | -8 +8 | | | =0 |
| Р9 | | | | | | | -7 +7 | | -9 | | =0 |
| Р10 | | | | | | | -7 | | +9 | | =0 |
| Р11 | | | | | | | | -8 +8 | | -10 | =0 |
| Р12 | | | | | | | | -8 | | +10 | =0 |
Перепишем полученные уравнения в более компактной форме:
- 1 - 6 + 6 = 0 (1)
+ 1 - 6 = 0 (2)
+ 2 - 2 + 3 - 4 = 0 (3)
- 2 + 4 = 0 (4)
+ 3 - 3 + 8 - 5 = 0 (5)
- 3 + 5 = 0 (6)
- 7 - 6 + 6 = 0 (7)
- 2 - 3 + 7 + 8 - 8 = 0 (8)
- 7 + 7 - 9 = 0 (9)
- 7 + 9 = 0 (10)
- 8 + 8 - 10 = 0 (11)
- 8 + 10 = 0 (12)
Преобразовав уравнения, получим:
1 = 0 (1)
1 = 6 (2)
3 = 4 (3)
2 = 4 (4)
8 = 5 (5)
3 = 5 (6)
7 = 0 (7)
7 = 2 + 3 (8)
9 = 0 (9)
7 = 9 (10)
10 = 0 (11)
8 = 10 (12)
Выполнив соответствующие подстановки, получим:
1 = 2 = 3 = 4 = 5 = 6 = 7 = 8 = 9 = 10 = 0,
То есть все потоковые значения нулевые. Это противоречит условию устойчивости системы.
В связи с этим рассмотренная сеть не является устойчивой, а, следовательно, процессы, ею описываемые, также являются неустойчивыми.
Поэтому модель нуждается в модификации, иначе методика, построенная на базе полученной модели, вероятно, будет содержать ошибки. Как видно из системы уравнений, нулевые потоковые значения, которые привели к нулевым потоковым значениям для всех положений, связаны с положениями Р1, Р7, Р9, Р11. Естественно предположить то, что если исправить ситуацию для перечисленных положений, то она исправится и для сети в целом.
Вернемся к прообразам положений Р1, Р7, Р9, Р11 и попытаемся выяснить существо ошибки.
Р1 отражает в модели СОр систему оценки соответствия информации табличного вида требованиям, предъявляемым к реляционным таблицам. Из рис. 8.2.11 видно, что СОр по выходам связана с двумя операторами, а по входам – с одним (связь с ИТВ не является связью с оператором). Из связи такого рода можно сделать ложный вывод о том, что СОр получается непосредственно из ИТВ без всяких преобразований. На самом деле это не так. Необходимо выполнить ряд оценок, что сопряжено с действиями и соответственно с операторами. Поэтому в динамической модели преобразования введем соответствующий оператор, а в сети Петри соответствующий переход t11. (Этот оператор и другие компоненты обновленной динамической модели отражены на рис. 8.3.4, который построен после выполнения всех необходимых манипуляций с сетью Петри).
Прообразом положения Р7 является ИТВ, прообразом положения Р9 является СОи (система оценки импорта). Эти компоненты модели связаны между собой, поэтому вначале попытаемся нормализовать ситуацию с одной из компонент, а другую рассмотрим позже. СОи по входу связана с одним оператором ОПи, а по выходу – с двумя операторами ОПРи и ОПи. Имеется связь между ИТВ и СОи по входу, но эта связь предполагает, что оценки необходимых действий по импорту выполняются без участия специальных средств. На самом деле это не так. В процессе импорта задействуются специализированные средства СУБД, использование которых не отражено. В связи с этим в операторную модель рис. 8.3.4 необходимо добавить дополнительный оператор ОСОи между ИТВ и СОИ, а в модель на основе сети Петри добавим соответствующий переход t12.
Прообразом положения Р11 является СОн (система оценки нормализации таблиц РБД). СОн по входу связана с одним оператором ОПн, а по выходу с двумя операторами ОПРн и ОПн. Это и нарушает потоковое равновесие. СОн связана по входу непосредственно с РБД. И если бы они были связаны посредством оператора, то фрагмент модели, связанной с СОн, не привносил бы отрицательную составляющую в устойчивость сети. И действительно, в динамической модели ошибочно отражено состояние процесса оценки соответствия таблиц РБД нормальным формам. Это безусловно действие и даже систему действий, которая в динамической модели должна быть отражена хотя бы одним оператором. В связи с этим в операторную модель рис. 8.3.4 добавим оператор ОСОн, а в модель, полученную на основе сети Петри, соответствующий переход t13.
В результате выполнения модификаций получим сеть Петри, представленную на рис. 8.3.2.
Рис 8.3.2. Первая модификация сети Петри
Несмотря на выявление и исключение теперь уже очевидных ошибок, полной уверенности в том, что полученная сеть стала устойчивой, нет. Дело в том, что в сеть добавлены 3-и новых перехода. Тем самым изменено потоковое назначение сети не только для рассмотренных положений, но и для положений, связанных с ними через переходы. Поэтому повторно запишем уравнения потоков для обновленной сети (табл. 8.3.2).
Т а б л и ц а 8.3.2
| | t1 | t2 | t3 | t4 | t5 | t6 | t7 | t8 | t9 | t10 | t11 | t12 | t13 | |
| Р1 | -1 | | | | | -6 +6 | | | | | +11 | | | =0 |
| Р2 | +1 | | | | | -6 | | | | | | | | =0 |
| Р3 | | +2 -2 | +3 | -4 | | | | | | | | | | =0 |
| Р4 | | -2 | | +4 | | | | | | | | | | =0 |
| Р5 | | | +3 -3 | | -5 | | | +8 | | | | | | =0 |
| Р6 | | | -3 | | +5 | | | | | | | | | =0 |
| Р7 | | | | | | -6 +6 | -7 | | | | -11 | -12 | | =0 |
| Р8 | | -2 | -3 | | | | +7 | -8 +8 | | | | | -13 | =0 |
| Р9 | | | | | | | -7 +7 | | -9 | | | +12 | | =0 |
| Р10 | | | | | | | -7 | | +9 | | | | | =0 |
| Р11 | | | | | | | | -8 +8 | | -10 | | | +13 | =0 |
| Р12 | | | | | | | | -8 | | +10 | | | | =0 |
Напишем уравнения в более компактной форме.
- 1 - 6 + 6 + 11 = 0 (1)
+ 1 - 6 = 0 (2)
+ 2 - 2 + 3 - 4 = 0 (3)
- 2 + 4 = 0 (4)
+ 3 - 3 + 8 - 5 = 0 (5)
- 3 + 5 = 0 (6)
- 7 - 6 + 6 - 11 - 12 = 0 (7)
- 2 - 3 + 7 + 8 - 8 - 13 = 0 (8)
- 7 + 7 - 9 + 12 = 0 (9)
- 7 + 9 = 0 (10)
- 8 + 8 - 10 + 13 = 0 (11)
- 8 + 10 = 0 (12)
Анализ уравнений позволяет сделать вывод о том, что ситуация существенно улучшилась. Однако осталось еще два противоречивых уравнения - уравнение 7 и уравнение 8. В уравнении 7 имеет место 4-е исходящих потока и 1 – входящий. В уравнении 8 входит 4-е потока и выходят 2 потока – явный дисбаланс.
Выражение 7 записано для положения 7 а положение 7 соответствует компоненте ИТВ в динамической модели (рис 2.2.11), Анализируя окружение ИТВ в динамической модели, можно сделать вывод о том, что только один оператор, непосредственно связанный с ИТВ имеет с ней обратную связь. А между тем, преобразование ИТВ – итерационный процесс и обратные связи с операторами, непосредственно работающими с ИТВ по всей видимости необходимы. Сформируем эти связи в сетевой и динамической моделях. Модифицированная сетевая модель приведена на рис.8.3.3, модифицированная операторная модель – на рис.8.3.4.
Рис. 8.3.3. Вторая модификация сети Петри
Для полученной сети запишем уравнения потоков, которые представлены в табл. 8.3.3.
Т а б л и ц а 8.3.3
| | t1 | t2 | t3 | t4 | t5 | t6 | t7 | t8 | t9 | t10 | t11 | t12 | t13 | |
| Р1 | - 1 | | | | | - 6 +6 | | | | | +11 | | | =0 |
| Р2 | +1 | | | | | - 6 | | | | | | | | =0 |
| Р3 | | +2 - 2 | +3 | - 4 | | | | | | | | | | =0 |
| Р4 | | - 2 | | +4 | | | | | | | | | | =0 |
| Р5 | | | +3 - 3 | | -5 | | | +8 | | | | | | =0 |
| Р6 | | | - 3 | | +5 | | | | | | | | | =0 |
| Р7 | | | | | | - 6 +6 | - 7 +7 | | | | - 11+11 | -12+12 | | =0 |
| Р8 | | - 2 | - 3 +3 | | | | +7 | - 8 +8 | | | | | -13+13 | =0 |
| Р9 | | | | | | | - 7 +7 | | - 9 | | | +12 | | =0 |
| Р10 | | | | | | | - 7 | | +9 | | | | | =0 |
| Р11 | | | | | | | | - 8 +8 | | - 10 | | | + 13 | =0 |
| Р12 | | | | | | | | - 8 | | +10 | | | | =0 |
Уравнение потоков для положения Р7 теперь выглядит следующим образом:
- 6 + 6 - 6 + 7 - 11 + 11- 12 + 12 = 0, или 0 = 0.
Таким образом, уравнение превратилось в тождество, и противоречий нет.
Уравнение потоков для положения Р8 теперь выглядит следующим образом:
- 2 - 3 + 3 + 7 + 8 - 8 - 13 + 13 = 0, или 7 = 2.
Противоречия нет.
В результате выполненных преобразований исходной сети Петри получена устойчивая сеть (рис.8.3.3).Функционирование такой сети не приведет к коллизиям перемещения информационных потоков. А так как полученная сеть взаимно однозначно соответствует динамической модели (рис. 8.3.4), то модель методики преобразования ИТВ к РБД является устойчивой, что исключает принципиальные ошибки в методике на ранних этапах ее разработки и реализации.
Рис. 8.3.4. Динамическая модель преобразования ИТВ к РБД
Для того, чтобы в полной мере удостовериться в том, что полученная сеть удовлетворяет требованиям к классической модели, построенной на основе сети Петри, выполним ее визуальный анализ. Предварительно напомним определение классической сети Петри – это двудольный ориентированный граф с разметкой положений. Двудольный граф – это граф, в котором задействованы вершины двух типов, причем вершины одного типа связаны с вершинами другого типа. В нашем случае положения должны быть связаны посредством ориентированных связей с переходами и наоборот.
После пошагового построения сети Петри синхронно с пошаговым формированием динамической модели преобразования ИТВ в РБД оказалось, что положения Р8 и Р9 связаны непосредственно между собой, что противоречит определению сети Петри. В связи с этим возможны следующие ситуации:
- эта связь лишняя и не отражает реальные процессы;
- эта связь необходима, но ее надо реализовать посредством перехода;
- динамическая модель не может быть в полном объеме отображена посредством классической сети Петри.
Последняя ситуация хоть и несколько неприятна, но разрешима. Можно задействовать аппарат модифицированных сетей Петри и использовать соответствующие средства исследования модели или выполнить декомпозицию таким образом, чтобы полученные подсети удовлетворяли требованиям к классическим сетям Петри. Затем выполнять исследования модели по частям. Прежде, чем выполнять эти манипуляции, рассмотрим две оставшиеся ситуации.
Является ли данная связь лишней? Из прототипа сетевой модели следует, что это - обратная связь, которая сформирована между РБД и СОи (системы оценок импорта). Эта связь задействована на начальных этапах построения динамической модели, и это косвенно свидетельствует о ее необходимости. Действительно, СОи должна не только выполнить анализ мероприятий, которые необходимо выполнить в процессе импорта таблиц ИТВ в таблицы РБД, но и должна выполнить анализ успешности выполнения мероприятий по импорту данных. Этот анализ выполняется во многом на основе данных, полученных в РБД. Поэтому связь между РБД и СОи необходима.
Нужен ли специальный переход (оператор) для реализации данной связи. Оператор для выполнения действий над импортированными таблицами в РБД по сути отчасти реализован в самой РБД. В частности, в процессе импорта формируются таблицы ошибочных записей. Это и привело к тому, что в динамической модели явно он не указан, но он есть. Более того действий инструментальной СУБД может быть недостаточно для формирования СОи. Вероятнее всего, потребуются специальные методы, средства и усилия разработчика.
В связи с вышесказанным в операторную модель вводится оператор ОПи, а в сеть Петри соответствующий переход. Таким образом, анализ несоответствия сетевой модели и классической помог выявить недостающую компоненту разрабатываемой системы.
Так как сформирован дополнительный переход t14, то вероятно нарушился баланс потоков для положений, которые связаны посредством нового перехода.
Новое уравнение потоков для Р8:
7 + 8 + 13 + 3 = 2 + 3 + 8 + 13 + 14 или
7 = 2 + 14
Это противоречивое уравнение. Поэтому необходимо проанализировать Р8 на отсутствие входных связей, которые имеют физический смысл.
Положение Р8 имеет обратные связи с переходами t3, t8 и t13, которым соответствуют операторы ОПк, ОПн, ОСОн. Это операторы, которые непосредственно связаны с РБД и реализуют операции назначения ключевых полей, операции нормализации таблиц РБД. Кроме названных операторов непосредственно с РБД связан оператор ОПс – оператор, обеспечивающий формирование связей между реляционными таблицами. Но этот оператор не имеет обратной связи с РБД и это явное упущение, так как процесс назначения связей между таблицами итерационный. Поэтому между ОПс и РБД формируется двунаправленная связь, которая и отражена в сети (рис. 2.3.3) ОПс соответствует переход t2.
Запишем уравнения потоков для Р8 с учетом дополнительного потока:
2 + 7 + 8 + 13 + 3 = 2 + 3 + 8 + 13 + 14 или
7 = 14
Противоречий нет.
Новое уравнение потоков для положения Р9 выглядит следующим образом:
14 + 12 + 7 = 7 + 9 или
14 + 12 = 9
Это уравнение противоречивое.
(Из уравнения (9) следует, что 12 = 9 и тогда 14 = 0)
Очень вероятно, что для положения Р9 ошибочно не сформирована необходимая связь, которая имеет физический смысл. Так как переход Р9 соответствует СОи (система оценки результатов импорта), то необходимо проанализировать связанные с ней операторы на предмет наличия входных связей. Можно предположить то, что посредством оператора ОСОи не только формируется система оценок результатов импорта на основе данных ИТВ, но и наоборот, посредством оператора ОСОи на основе СОи выполняется модификация ИТВ с целью ее подготовки для реализации успешного импорта таблиц ИТВ. По сути так оно и есть, тем более, что между ОСОи и ИТВ имеется двунаправленная связь. Поэтому в сети отразим обратную связь между Р9 и t12. Эту же связь отразим на динамической модели.
Выполним проверку баланса потоков для положения Р9:
14 + 12 + 7 = 7 + 9 + 12 или
14 = 9
Противоречий нет.
Таким образом, на основе анализа опраторной модели, анализа вариантов сети Петри построена устойчивая сеть Петри, удовлетворяющая классическим требованиям.
Может создаться ложное впечатление о том, что динамическая модель подгонялась под требования используемого математического аппарата. На самом деле наоборот, математический аппарат сетей Петри позволил выявить коллизии в динамической модели, которая построена эмпирическим путем и не была гарантирована от ошибок. В результате выполненных преобразований, с одной стороны, получена операторная модель методики преобразования ИТВ к РБД, свободная от принципиальных ошибок, а с другой стороны, получено формальное описание этой модели, которое может быть использовано для ее дальнейшего исследования и улучшения. В связи с тем, что в формальном описании модели выявлены и исключены принципиальные ошибки, то оно является адекватным реальному моделируемому процессу.
Даже на данной стадии описания и исследования операторной модели она представляет ценность. Операторная модель позволяет сделать вывод:
- о необходимом составе операторов (методов, алгоритмов и средств), которые необходимо разработать для реализации полнофункциональной системы;
- о необходимом составе системы оценок или функций (методов, алгоритмов и средств), которые необходимо разработать для реализации полнофункциональной системы проектирования;
- о связях между методами и средствами в разрабатываемой системе.
Кроме того, операторная модель иллюстрирует порядок и правила использования методов и средств задействованных в процессе решении задач преобразования ИТВ в РБД в разрабатываемой системе.
Что касается динамики функционирования сети Петри и соответствующей ей операторной модели, она в данном случае отражена лишь отчасти и сводится к ориентации информационных потоков.
Их можно визуально отслеживать и в результате делать необходимые умозаключения. Однако, для более глубокого анализа динамических свойств модели и соответствующего объекта исследования оправданно использование специальных средств – маркерных сетей Петри, которые рассмотрены ниже.