СУБД / УМК СУБД

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

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

Задача экономного представления результатов набора практически не рассматривается в литературе.

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

Также следует отметить недостаточную активность в создании и внедрении методов сжатия, позволяющих оперировать при выполнении запросов непосредственно закодированными данными. Существующие разработки ориентированы на кодирование индексных данных.

Тема 11. Фракталы и Фрактальные методы архивации

Существуют алгоритмы архивации (сжатия) больших информационных массивов,

информационных хранилищ и складов данных с помощью фракталов. Они основаны на теореме Банаха о сжимающих преобразованиях (также известной как Collage «Theorem»)

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

Джорджия Майкла Барнсли.

1. Фракталы и история возникновения метода фрактального сжатия

Понятия «фрактал» и «фрактальная геометрия» (fractus – состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии связывают с выходом в 1977 г. книги Б. Мандельброта «Фрактальная геометрия природы», в которой объединены в единую систему научные результаты учёных,

работавших в период 1875-1925 гг. в этой области (Пуанкаре, Жюлиа, Кантор и др.).

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

С точки зрения машинной графики, фрактальная геометрия незаменима при генерации сложных неевклидовых объектов, образы которых весьма похожи на

95

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

Существует большое разнообразие фракталов. Потенциально наиболее полезным видом фракталов являются фракталы на основе системы итеративных функций (Iterated Function System – IFS). Метод IFS применительно к построению фрактальных изображений, изобретённый большим их знатоком Майклом Барнсли (Michael Barnsley) и

его коллегами из Технологического института шт. Джорджия (Georgia Institute of Technology), базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения позволяют переносить, поворачивать и изменять масштаб участков изображения; таким образом, эти участки служат компоновочными блоками остальной части картины.

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

фракталов.

IFS-фракталы имеют одно вполне реальное и полезное применение: с их помощью можно сжимать большие растровые изображения до долей их нормальных размеров. Этот утверждение следует из теоремы Банаха о сжимающих преобразованиях (также известной как Collage Theorem) и является результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли в области IFS. Вооружившись этим выводом, он ушёл из института, запатентовал своё открытие и основал компанию Iterated Systems Incorporated. О своём достижении он рассказал миру в журнале Byte за январь 1988 г.

Однако там отсутствовали какие-либо сведения о решении обратной задачи: как по заданному изображению найти аффинные преобразования. К тому моменту у этой задачи не было даже намёка на решение. В статье Барнсли было показано несколько реалистичных фрактальных изображений, но все они были созданы вручную.

96

В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM), воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin). Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его

частям.

2. Математические основы фрактального сжатия

Итак, рассмотрим математическое обоснование возможности фрактального сжатия.

Есть отображение			,
где	–	множество	всех возможных	изображений.	является объединением
отображений		:
где	– изображение,
– какие-то (возможно, перекрывающиеся) области изображения .
Каждое преобразование			переводит в	. Таким образом:
	Будет логично представить изображение в виде функции двух переменных					.

На множестве всех таких функций введём метрику (расстояние между изображениями),

например, таким образом:

	(	)
Согласно теореме Банаха, существует определённый класс отображений, для
которых существует константа	такая, что	для любых изображений	и
выполняется неравенство

Такие отображения называются сжимающими, и для них справедливо следующее утверждение:

Если к какому-то изображению F0 мы начнём многократно применять отображение W

таким образом, что

то в пределе, при i, стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве :

97

Это конечное изображение называют аттрактором, или неподвижной точкой

отображения	. Также известно, что если преобразования являются сжимающими, то
их объединение	тоже является сжимающим.

3.Типовая схема фрактального сжатия

Сучётом вышесказанного, схема компрессии выглядит так: изображение разбивают на кусочки , называемые ранговыми областями. Далее для каждой области

, находят область		и преобразование такие, что выполняются следующие условия:
1.	по размерам больше ,.
2.	имеет ту же форму, размеры и положение, что и ,
3.	Коэффициент	преобразования должен быть меньше единицы.
4.	Значение должно быть как можно меньше.

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

изображения (отсюда и название – «фрактальная компрессия»). Как оказалось,

практически все реальные изображения содержат такие похожие друг на друга, с

точностью до аффинного преобразования, части.

	Таким образом, для компрессии изображения нужно:
1.	Разбить изображение на ранговые области , (непересекающиеся области,
покрывающие все изображение).
2.	Для каждой ранговой области , найти область	(называемую доменной), и
отображение , с указанными выше свойствами.
3.	Запомнить коэффициенты аффинных преобразований , положения доменных
областей , а также разбиение изображения на домены.
	Соответственно, для декомпрессии изображения нужно будет:
1.	Создать какое-то (любое) начальное изображение .
2.	Многократно применить к нему отображение	(объединение wi).
3.	Так как отображение сжимающее, то в результате, после достаточного количества

итераций, изображение придёт к аттрактору и перестанет меняться. Аттрактор и является нашим исходным изображением. Декомпрессия завершена.

Пусть дано изображение точек (где и кратны 8), 256 градаций серого.

Ранговые и доменные области будем брать квадратными. Исходное изображение разобьём

98

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

центральной вертикали, от главной и побочной диагоналей). Осталось найти только

коэффициенты для преобразования цвета. Но значения			и	(контрастности и яркости)
можно легко найти аналитически.
Если	есть две	последовательности значений	цвета		пикселов
(доменной	области) и	(ранговой области),		то	можно минимизировать

среднеквадратичное отклонение цвета пикселов, представляющее собой вариант метрики различия изображений:

		∑
Для этого достаточно приравнять частные производные								по и по к нулю, и
решить уравнение относительно		и . Получатся такие выражения:
	∑	∑	∑			∑		∑
	∑	∑
при этом, если
		∑	(∑ )
то
				∑

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

4. Оценка коэффициента сжатия и вычислительных затрат Размер данных для полного определения ранговой области рассчитывается по

формуле:

,

где – количество бит, необходимых для хранения координат нижнего левого угла домена

– количество бит, необходимых для хранения типа аффинного преобразования

99

и– для хранения коэффициентов контраста и яркости.

где и – количество бит, необходимых для хранения каждой из координат,

рассчитываются по следующим формулам:

,

где – функция округления до максимального целого и – количество доменов, умещающихся по горизонтали и вертикали, которые

рассчитываются по формулам:

где и – вертикальный и горизонтальный размеры изображения

– размер доменного блока,	– шаг поиска доменной области.
Для хранения преобразования	необходимо 3 бита.
Для хранения и необходимо 9 и 7 бит соответственно.
Для примера возьмём изображение размером		пикселей, и будем исследовать

доменную область с шагом 4 пикселя.

Коэффициент сжатия составляет

Коэффициент сжатия не так велик, как хотелось бы, но и параметры сжатия далеко не оптимальны, и коэффициент может увеличиваться в разы.

А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области – 1'024 штуки, для каждой – все ранговые – 58'081 штука (при шаге 1), а для каждой из них, в свою очередь, – все 8

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

свою очередь, включают операции умножения и деления чисел с плавающей точкой.

К сожалению, даже на современном ПК (а именно для таких машин хотелось реализовать алгоритм) понадобится недопустимо много времени для того, чтобы сжать

100

изображение размером всего пикселов. Очевидно, что рассмотренный

алгоритм нуждается в оптимизации.

5. Оптимизация алгоритма компрессии

Алгоритм нуждается в оптимизации по нескольким направлениям: по скорости, по

качеству получаемого изображения, по степени компрессии.

Для снижения вычислительных затрат можно предпринять следующие меры:

1. Исследовать доменную область не полностью, а с некоторым шагом. Это также позволит увеличить степень сжатия, но скажется на качестве изображения.

2. Искать не лучшую доменную область, а удовлетворяющую некоторому . Хотя это

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

3. При поиске доменной области подвергать преобразованию не доменную область, а

ранговую. Для этого удобно хранить 8 вариантов ранговых областей с различными преобразованиями. При этом в результирующий файл нужно записать обратное преобразование. Для всех преобразований, кроме двух, обратным является само это

преобразование. Для поворота на и необходимо записать поворот на и

соответственно. Это значительно сократит вычислительные затраты, но также значительно увеличатся затраты оперативной памяти.

4. Для поиска доменной области можно использовать не перебор, а какой-либо из алгоритмов условной нелинейной глобальной оптимизации, такой, как алгоритм моделирования отжига или генетический алгоритм. В этом случае будет всего три варьируемых параметра (координаты доменной области и номер аффинного преобразования), а целевой функцией – среднеквадратичное отклонение доменной области от ранговой.

Для улучшения качества: в случае необнаружения доменной области,

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

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

за счёт чего будет достигнуто сжатие 1 к 64 (для ранговых областей размером 8).

101

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

Общие организационно-методические указания по выполнению

лабораторного практикума

Методические указания построены по следующему принципу: сначала ставится цель задания, затем дается методика достижения цели, потом на примере разбирается решение, и только после этого выдаются индивидуальные задания по вариантам .

Рассмотренные в методических указаниях в качестве примеров задачи должны быть решены студентом. Только после этого студент самостоятельно решает задачи в соответствии с выбранным вариантом. Письменные выводы, сделанные в ходе выполнения заданий, заносятся студентом в тетрадь, с указанием варианта и номеров задания.

Решенные примеры сохраняются в файле рабочей книги в каталоге студента,

указанном преподавателем, на ПК.

СТРУКТУРА

ЦЕЛИ И ЗАДАЧИ

Цель

Научиться пользоваться СУБД Microsoft Access.

Задача

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

ПРИОБРЕТАЕМЫЕ НАВЫКИ

•Умение работать с общедоступной СУБД

•Умение автоматизировать свое рабочее место с помощью общедоступной СУБД Введение.

Любой человек сталкивался с необходимостью каким-либо образом хранить

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

любая картотека, подшивка будет неудобна с точки зрения поиска, корректировки или изъятия нужной информации.

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

Таким образом, перед тем, как приступить к изучению самой программы Microsoft Access, определим тот круг задач, который можно решать с его помощью.

102

Что такое база данных?

Перед тем, как пытаться получить результат обработки информации, следует учитывать, что информация должна быть соответствующим образом структурирована и представлена. При этом понятие «информация» заменяется на понятие «данные»,

совокупность которых образует базу данных. Однако не следует воспринимать любой набор чисел или текста как базу данных – хранимые в ней данные должны быть структурированы и каким-то образом поименованы (примерно, как в картотеке есть данные Иванов, Петров, Сидоров, поименованные соответственно как Фамилия).

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

Модель данных – это совокупность структур данных и операций их обработки.

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

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

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

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

Что такое система управления базами данных?

База данных может быть создана и в дальнейшем обработана с помощью многих программ (например, и текстовый процессор Microsoft Word, и табличный процессор

Microsoft Excel позволяют работать с простейшими базами данных), но существует специальный вид программ, именно и разрабатываемых для этих целей, которые называются системами управления базами данных (СУБД).

Система управления базами данных (СУБД) – это прикладная программа,

предназначенная для создания, ведения баз данных и организации поиска в них нужной информации.

Microsoft Access является системой управления реляционными базами данных,

которая входит в состав пакета Microsoft Office 2010 и позволяет реализовывать основные операции по созданию баз данных и обработке хранящейся в них информации.

Проектирование базы данных

103

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

При этом мы как менеджеры располагаем сведениями о товаре (минимальном наборе его характеристик – наименовании, общих сведениях и цене), о клиентах, которые у нас хотят купить товар (наименовании, адресе) и, наконец, о собственно продажах товара клиентам (дате продажи, наименовании продаваемого товара, наименовании покупающего клиента, количестве продаваемого товара).

Проектируя будущую базу данных, можно видеть, что хранение всей этой информации «в одной куче» приведет к тому, что данные хоть и будут структурированы и содержаться в одной таблице, но... кто захочет постоянно вводить данные о товаре, если мы его продаем 10 раз за один день? А о клиенте, если он покупает несколько видов товара?

Таким образом, можно создать три таблицы – «Товары», «Клиенты» и «Продажи»,

каждая из которых будет хранить строго определенный набор данных. Но в этом случае появляется другой вопрос – а как можно узнать, какой клиент купил тот или иной товар?

И какой именно товар продается согласно записи таблицы «Продажи»?

Возвращаясь к рассмотренному материалу, определим между таблицами отношения – то есть в таблицу Продажи необходимо ввести поле, содержащее наименование товара, и поле, содержащее наименование клиента.

Однако, если мы будем нумеровать (или кодировать) записи, то проблема лишних обращений к клавиатуре будет еще более сокращена за счет ввода только номера товара и номера клиента – при условии, что соответствующие поля будут введены в состав таблиц

«Товары» и «Клиенты».

Итак, набросав примерный проект базы данных, приступим к его реализации.

104