где X - количество бит, необходимых для хранения координат нижнего левого угла домена, T - количество бит, необходимых для хранения типа аффинного преобразования, U и V - для хранения коэффициентов контраста и яркости.
(11)
где Nb и Mb - количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:
(12)
Здесь CEIL - функция округления до максимального целого, Md и Nd - количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам:
(13)
где V и H - вертикальный и горизонтальный размеры изображения, Size - размер доменного блока, Step - шаг поиска доменной области.
Для хранения преобразования T необходимо 3 бита.
Для хранения U и V необходимо 9 и 7 бит соответственно.
Для примера возьмём изображение размером 256x256 пикселей, и будем исследовать доменную область с шагом 4 пикселя.
Nd = Md = (256 - 8 + 1) / 4 = 62
Nb = Mb = CEIL (log2 62) = 6
Х = 12
Z = 12 + 3 + 6 + 6 = 27
Коэффициент сжатия S составляет
S = (8 * 8 * 8) / 27 = 19
Коэффициент сжатия не так велик, как хотелось бы, но и параметры сжатия далеко не оптимальны, и коэффициент может увеличиваться в разы.
А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области - 1'024 штуки, для каждой - все ранговые - 58'081 штука (при шаге 1), а для каждой из них, в свою очередь, - все 8 преобразований. Итого получается 1'024 х 58'081 х 8 = 475'799'552 действия. При этом эти действия не тривиальны и включают несколько матричных операций, которые, в свою очередь, включают операции умножения и деления чисел с плавающей точкой.
К сожалению, даже на современном ПК (а именно для таких машин хотелось реализовать алгоритм) понадобится недопустимо много времени для того, чтобы сжать изображение размером всего 256 х 256 пикселов. Очевидно, что рассмотренный алгоритм нуждается в оптимизации.
В процессе проектирования базы данных возникают вопросы: хорошо ли спроектированы отношения между сущностями? Правильно ли они отражают предметную область?
На стадии физической реализации базы данных отношения преобразуются в таблицы, атрибуты становятся столбцами таблиц, для ключевых атрибутов создаются уникальные индексы, домены преображаются в типы данных, принятые в конкретной СУБД.
При этом также возникают вопросы: хорошо ли спроектированы таблицы? Правильно ли выбраны индексы?
Для ответа на этот вопрос необходимо рассмотреть понятие нормальной формы.
Рассмотрим в качестве примера предметной области некоторую организацию, выполняющую проекты. Модель предметной области опишем следующим неформальным текстом:
1. Сотрудники организации выполняют проекты.
2. Проекты состоят из нескольких заданий.
3. Каждый сотрудник может участвовать в одном или нескольких проектах, или временно не участвовать ни в каких проектах.
4. Над каждым проектом может работать несколько сотрудников, или временно проект может быть приостановлен, тогда над ним не работает ни один сотрудник.
5. Над каждым заданием в проекте работает ровно один сотрудник.
6. Каждый сотрудник числится в одном отделе.
7. Каждый сотрудник имеет телефон, находящийся в отделе сотрудника.
8. О каждом сотруднике необходимо хранить табельный номер и фамилию. Табельный номер является уникальным для каждого сотрудника.
9. Каждый отдел имеет уникальный номер.
10. Каждый проект имеет номер и наименование. Номер проекта является уникальным.
11. Каждая работа из проекта имеет номер, уникальный в пределах проекта. Работы в разных проектах могут иметь одинаковые номера.
Начинающий проектировщик будет использовать отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Номер сотрудника, ФИО, номер отдела, телефон, номер проекта, название проекта, номер задания), имеющее сложный ключ).
Действительно, зачем разбивать данное отношение на несколько более мелких отношений, если оно заключает в себе все данные? А разбивать надо потому, что при использовании универсального отношения возникает несколько проблем:
1. Проблема избыточности. Даже одного взгляда на отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ достаточно, чтобы увидеть, что данные хранятся в ней с большой избыточностью. Во многих строках повторяются фамилии сотрудников, номера телефонов, наименования проектов. Кроме того, в данном отношении хранятся вместе независимые друг от друга данные - и данные о сотрудниках, и об отделах, и о проектах, и о работах по проектам. Пока никаких действий с отношением не производится, это не страшно. Но как только состояние предметной области изменяется, то, при попытках соответствующим образом изменить состояние базы данных, возникает большое количество проблем.
2. Аномалии обновления. Вследствие избыточности можно обновить телефон отдела для одного сотрудника, оставляя его неизменным в других строках. Следовательно, при обновлениях необходимо просматривать всю таблицу для нахождения и изменения всех подходящих строк. Причина аномалии - избыточность данных, также порожденная тем, что в одном отношении хранится разнородная информация.
Вывод - увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров.
3. Аномалии включения. В отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ нельзя вставить данные о сотруднике, который пока не участвует ни в одном проекте. Действительно, если, например, во втором отделе появляется новый сотрудник, скажем, Пушников, и он пока не участвует ни в одном проекте, то мы должны вставить в отношение кортеж (4, Пушников, 2, 33-22-11, null, null, null). Это сделать невозможно, т.к. атрибут Н_ПРО (номер проекта) входит в состав сложного ключа, и, следовательно, не может содержать null-значений. Точно также нельзя вставить данные о проекте, над которым пока не работает ни один сотрудник.
Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и о проектах, и о работах по проекту).
Вывод - логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно.
4. Аномалии удаления. При удалении некоторых данных может произойти потеря другой информации. Например, если закрыть проект "СУЭД" и удалить все строки, в которых он встречается, то будут потеряны все данные о сотруднике Петрове П.П.. Кроме того будет потеряна информация о том, что в отделе номер 2 имеется телефон под номером 25-54-54.
Говорят, что отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ находится в 1НФ.
Первая нормальная форма (1НФ) - это обычное отношение. Любое отношение автоматически уже находится в 1НФ. Свойства 1НФ:
· В отношении нет одинаковых кортежей.
· Кортежи не упорядочены.
· Все значения атрибутов атомарны.
В 1 НФ модель данных не адекватна модели предметной области. Следовательно, первой нормальной формы недостаточно для правильного моделирования данных.
Для устранения указанных аномалий (а на самом деле для правильного проектирования модели данных!) применяется метод нормализации отношений. Нормализация основана на понятии функциональной зависимости атрибутов отношения. Функциональная зависимость - семантическое понятие, она возникает, когда по значениям одних данных в предметной области можно определить значения других данных. Например, зная табельный номер сотрудника, можно определить его фамилию, по номеру отдела можно определить телефона.
В отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ можно привести следующие примеры функциональных зависимостей:
от ключа {Н_СОТР, Н_ПРО} зависят следующие атрибуты ФИО, номер отдела, телефон, название проекта, номер задания;
от номера сотрудника зависят следующие атрибуты ФИО, номер отдела, телефон;
от номера проекта зависит наименование проекта;
от номера отдела зависит номер телефона;
Замечание. Эти зависимости отражают взаимосвязи, обнаруженные между объектами предметной области.
Отношение находится во второй нормальной форме (2НФ) тогда и только тогда, когда оно находится в 1НФ и нет неключевых атрибутов, зависящих от части сложного ключа. (Неключевой атрибут - это атрибут, не входящий в состав никакого потенциального ключа).
Замечание. Если ключ отношения является простым, то отношение автоматически находится в 2НФ.
Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ не находится в 2НФ, т.к. есть атрибуты, зависящие от части сложного ключа: зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника является зависимостью от части сложного ключа, зависимость наименования проекта от номера проекта является зависимостью от части сложного ключа.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26
