Содержание к диссертации
Введение
Глава 1. Аналитический обзор современного состояния средств СУБД и машин баз данных 17
1.1. Общие положения: исторический очерк 17
1.2. Неоднородные многопроцессорные ма шины баз данных (МВД) 21
1.3. Параллельные машины баз данных 33
1.4. Побудительные причины исследования и сущность предлагаемого подхода к созданию МЕД 34
1.5. Выводы 38
Глава 2. Структурно - лингвистические средства акселерации 41
2.1. Понятийный базис продукционной алгоритмической системы 41
2.2. Классификация формул подстановок 46
2.3. Способы синтеза акселерациониых форм представления продукций 49
2.4. Иллюстрация продукционной реализации операций реляционной алгебры 53
2.5. Способы сопоставления (поиска по образцу) 57
2.6. Способы сортировки 65
2.6.1. Классификация алгоритмов сортировки последовательноетей 65
2.7. Способ парной параллельной сортировочной транспозиции элементов и слияния отсортированных последовательностей 67
2.8. Выводы 70
Глава 3. Разработка аппаратных средств акселерации
3.1. Способ организации машины баз данных
3.2. Специализированное устройство сортировки
3.3. Специализированное устройство слияния
3.4. Специализированное устройство быстрого поиска позиций вхождений образцов
3.4.1. Работа устройства поиска вхождений образца
3.5. Специализированное устройство модификации слов
3.6. Выводы
Глава 4. Алгоритмические средства устройств управления специализированными устройствами МБД и результаты исследования скоростных характеристик
4.1. Алгоритмы управления устройств сортировки и слияния
4.1.1. Алгоритм управления устройства сортировки
4.1.2. Алгоритм управления устройства слияния
4.2. Алгоритм управления устройства поиска вхождения
4.3. Алгоритм управления устройства модификации
4.4. Результаты исследования скоростных характеристик
4.4.1. Сопоставительный анализ ускорений разработанного устройства и аналога
4.4.2. Анализ скоростных характеристик устройства поиска
4.4.3. Анализ скоростных характеристик продукционного символь-ного процессора
4.5. Выводы
Заключение 157
Список литературы 159
Приложения 167
- Неоднородные многопроцессорные ма шины баз данных (МВД)
- Иллюстрация продукционной реализации операций реляционной алгебры
- Специализированное устройство быстрого поиска позиций вхождений образцов
- Анализ скоростных характеристик продукционного символь-ного процессора
Введение к работе
Актуальность работы. Сбор релевантной информации, надежность её хранения, высокоскоростной доступ и обработка при минимально допустимой стоимости составляют основные направления в условиях глобальной информатизации и компьютеризации. Бурный рост объёмов, разнообразия типологий и сложности логических структур информации в современных компьютерных системах определяет необходимость в разработке новых методов и систем хранения с быстрым откликом на запросы пользователей.
Попытки решения проблем хранения информации с быстрым откликом сконцентрировались в области научно-технических программ, направленных на создание машин и систем баз данных. После негативных результатов практического использования специализированных машин баз данных в этой области вычислительной техники была сформулирована и реализована концепция многопроцессорных систем, аппаратно поддерживающих различные системы управления базами данных. Такой скачкообразный переход привел к тому, что не используются возможности относительно простых структур машин баз данных, построенных на основе разнородных специализированных устройств быстрых символьных вычислений, функционирующих в различных конфигурациях и предназначенных для аппаратной поддержки систем управления широко распространенных баз данных средних объемов, что составляет основную проблемную ситуацию.
Решению проблем создания машин и систем баз данных и знаний посвящены работы М. Сенко, Я. Палмера, Г. Найсена, Э. Озкарахана, Л. Калини-ченко, Д. Поспелова и других исследователей как у нас в стране, так и за рубежом.
Между тем, в существующих работах отсутствуют реализации машин баз данных, основанных на технологии обработки символьной информации.
В современных источниках научно-технической информации содержится достаточное количество работ, содержащих необходимые сведения для разрешения основной проблемной ситуации. Теоретическая часть работы содержит разработку способов быстрых символьных вычислений и обоснование их логической состоятельности и целесообразности использования для структурно-функциональной организации как отдельных устройств, так и символьной машины баз данных в целом. Практическая часть диссертации заключается в разработке аппаратных реализаций и получении результатов исследования скоростных характеристик машин рассматриваемого класса.
На основании изложенного можно заключить, что тема диссертационного исследования является актуальной и перспективной.
Работа выполнялась в рамках НИР по Единому заказ-наряду и грантам Г00-4.2.15 и Г02-4.2.5, выполненных в Курском государственном техническом университете в период с 1999 по 2005 годы при непосредственном участии автора.
Целью работы является повышение скорости работы и расширение функциональных возможностей аппаратных платформ систем управления базами данных путём создания средств акселерации работы продукций и процессов быстрого поиска и сортировки, специализированных устройств и архитектуры символьной машины баз данных на их основе, а также исследование скоростных характеристик.
Для достижения указанной цели поставлены и решены следующие основные задачи: - разработка форм представления продукций, являющихся элементарными операторами алгоритмических схем быстрых символьных вычислений, и образцов продукций, обеспечивающих сокращение затрат времени как при работе продукций, так и при сопоставлении с образцом; - создание алгоритмических средств организации быстрых процессов сопоставления с образцом (поиск), работы продукций (поиск и модификация), сортировки и слияния; разработка технических решений устройств: поиска, модификации, сортировки и слияния упорядоченных данных, и осуществление их структурно-функционального объединения в архитектуру символьной машины баз данных; проведение экспериментальных исследований скоростных характеристик символьной машины баз данных.
Объектом исследования являются алгоритмические и аппаратные средства, поддерживающие процессы управления данными.
Предмет исследования составляют процессы преобразования информации в системах управления базами данных (СУБД).
Методы исследования базируются на теории алгоритмов, конструктивной математической логике, современной прикладной семиотике, а также теории автоматов и проектирования ЭЦВМ.
Научная новизна работы заключается в получении следующих результатов:
На основе структурно-лингвистического анализа впервые разработан и обоснован новый сокращенный набор акселерационных форм представления продукций для быстрых символьных вычислений в контурах СУБД, обеспечивающий скоростное преимущество до четырех-пяти раз. Кроме того, разработаны новый способ, соответствутощие формы представления образцов и алгоритм быстрого поиска, особенностью которого является безотступный режим сопоставления с образцом, что позволяет сократить затраты времени до двух раз по сравнению с реализацией алгоритмов-аналогов.
Созданы способ и осуществлена алгоритмизация средств быстрой модификации обрабатываемых слов, а также алгоритм сортировки, отличающийся тем, что в нем используется механизм параллельной компарации и транспозиции пар элементов исходного массива, позволяющий выполнять сортировку за число шагов, не превышающее число элементов исходной последовательности, и осуществлена алгоритмизация процесса слияния упорядоченных данных.
Впервые разработана структурно-функциональная организация символьной машины баз данных, имеющей скоростное преимущество до трёх-четырёх раз по отношению к аналогу и созданной на основе новых технических решений четырех специализированных устройств с двумя конфигурациями - с независимой работой компонентов и с объединением их в два процессора: универсальный символьный процессор быстрых символьных вычислений (с использованием устройств быстрого поиска и модификации) и процессор сортировки данных (с использованием устройств сортировки и слияния).
Разработана конфигурация с универсальным символьным процессором, которая существенно расширяет функциональные возможности машины баз данных, обеспечивая решение множества разнотипных задач символьных вычислений: обработка знаний и языков запросов, а также реализация функций и операций существующих и вновь создаваемых реляционных или объектно-ориентированных баз данных.
Практическая ценность работы заключается в том, что ее результаты рекомендуются для использования на уровне программных средств в процессах обработки символьной информации в контурах СУБД, а технические решения устройств создают основу для дальнейших опытно-конструкторских разработок с целью организации производства символьных машин баз данных. Вместе с тем разработанные способы, алгоритмические и аппаратные средства имеют признаки новизны и существенных отличий и рекомендуются для использования в учебном процессе студентов соответствующих специальностей.
Апробация работы. Результаты диссертационного исследования докладывались и обсуждались на:
2-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Расгюзлаваиие-1995» (Курск, 1995);
Международной конференции «Актуальные проблемы компьютеризации в странах СНГ» (Донецк, 2002);
6-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2003» (Курск, 2003);
6-й Международной научно-технической конференции «Медико-экологические информационные технологии-2003» (Курск, 2003).
Личный вклад автора в работы, написанные в соавторстве, заключается в модификации способов и построении базовых алгоритмов, в доказательстве основных положений, структурно-лингвистическом анализе процессов сопоставления (поиска) и конструктивных процессов работы продукций, а также в разработке результирующих технических решений.
Реализация и внедрение. Результаты диссертационной работы внедрены в НПО «Экран» (Москва), а также используются в учебном процессе Курского государственного технического университета в рамках курса «Высокопроизводительные вычислительные системы», что подтверждается актами о внедрении.
На защиту выносятся:
Акселерационные формы представления продукций, а также образцов для быстрых символьных вычислений и процессов сопоставления в контурах СУБД.
Способы, алгоритмы и устройства быстрого поиска и модификации, а также алгоритмы и устройства быстрой параллельной сортировки и слияния.
Технические решения специализированных устройств и структурно-функциональная организация символьной машины баз данных на их основе.
4. Результаты исследования скоростных характеристик символьной машины баз данных.
Структура и объём диссертации. Диссертация состоит из введения, четырех глав и заключения, изложенных на 167 страницах, содержит 57 рисунков, 2 таблицы, списка литературы из 75 наименований.
Во введении обоснована актуальность темы, сформулированы цель и задачи исследования, научная новизна, практическая ценность работы, основные положения, выносимые на защиту и др.
Первая глава носит обзорный характер и служит целям анализа функциональных особенностей машин баз данных (МБД).
В обзорной части главы приведены общие положения и классификация МБД, рассмотрены основные архитектуры МБД (однородная, неоднородная, параллельная). МБД представляет собой аппаратно-программный комплекс, являющийся частью вычислительной системы и предназначенный для выполнения всех или некоторых функций СУБД. Анализ задач, решаемых современными СУБД, позволил выделить основные требования, предъявляемые к МБД: возможность обработки больших объёмов обрабатываемых данных со сложной логической структурой, быстрый поиск, добавление, изменение и удаление фрагментов структур; возможность обработки данных, хранящихся как в реляционных базах данных, так и данных, хранящихся в текстовом или документальном формате. Анализ вычислительных средств, ориентированных на выполнение указанных требований, позволил выявить два альтернативных подхода: применение универсальных компьютеров с программным обеспечением, поддерживающим СУБД, и применение специализированных аппаратных устройств, реализующих ресурсоёмкие или часто выполняемые функции СУБД. Рассмотрены преимущества и недостатки указанных подходов.
В связи с прогрессом в области СБИС получило развитие такое направление в области обработки данных как разработка специализированных МБД, n выполняющих некоторые функции конкретных типов СУБД. Быстрая эволюция СУБД является основным источником быстрого морального старения аппаратных платформ специализированных МБД, поэтому в последнее время в литературе развернута острая критика этого класса машин, что явилось побудительной причиной создания параллельных систем разнородного и однородного типа. Одним из средств повышения скорости обработки данных в этих архитектурах, является механизм переноса данных из массовой памяти в системную буферную память, с которым могут совмещаться операции фильтрации. Этот механизм реализован во многих многопроцессорных неоднородных МБД, он позволяет сбалансировать скорости «перекачки» данных и их обработки в процессорах и за счет этого существенно повысить производительность МБД. Значимой причиной востребованности параллельных систем явилось широкое распространение высоко структурированных реляционных и объектно-ориентированных баз данных больших объемов. В свою очередь, при использовании параллельных МБД возникает ряд сложных проблем, сопряженных с организацией их работы и проблемы параллельного программирования.
В сложившихся обстоятельствах, разработчики аппаратных платформ МБД переориентировались на параллельные архитектуры систем баз данных, оставив без должного внимания функциональные возможности неоднородных машин баз данных, функционирующих на основе специализированных устройств, использующихся в различных конфигурациях.
Сущность предлагаемого подхода заключается в использовании технических решений специализированных устройств символьных вычислений: поиска, модификации, сортировки и слияния, составляющих основу структурно-функциональной организации символьной машины баз данных (СМБД). Разработанная СМБД отличается тем, что она функционирует под управлением центрального процессора в двух конфигурациях, первая из которых задает независимую работу устройств, а вторая формирует из них два процессора: универсальный npoijeccop быстрых символьных вычислений и процессор сортировки и слияния. Такая организация СМБД позволяет повысить скорость обработки информации и существенно расширить функциональные возможности при решении классических задач обработки символьной информации (реализация функций и типовых операций реляционной алгебры, обработка знаний, обработка языков и т.д.) в существующих и вновь создаваемых СУБД.
Во второй главе разработаны формальные структурно-лингвистические средства акселерации работы элементарного оператора (продукции) алгоритмических схем обработки символьной информации. Сформирован новый сокращенный класс элементарных операторов в виде продукций специального вида (акселерационные формы) и разработан метод реализации быстрых процедур поиска в безотступном режиме, а также организация процессов параллельной сортировочной транспозиции и слияния.
Приведены понятийный базис продукционной алгоритмической системы и классификация формул подстановок.
Определена конструктивная дизъюнкция позволяющая относить анализируемую формулу к классу транзитивных, которые потенциально создают подстановкой модификатора в обрабатываемом слове позицию вхождения собственного образца.
Для преобразования транзитивных формул введена унифицированная операция итерации, которая используется для записи акселерационных форм представления формул этого класса с целью обеспечения возможности выполнять безотступную технологию сопоставления. Представлены все варианты записи (шаблоны) самоопределяющихся формул в соответствии с истинностью членов конструктивной дизъюнкции.
Далее во второй главе проиллюстрирована продукционная реализация операций реляционной алгебры (операции объединения, пересечения, вычитания, декартово произведение, деление) и функции DECODE, реализованной в языке PL-SQL, поддерживаемом СУБД Oracle.
Изложены результаты разработки способов быстрого поиска по образцу, которые создают необходимые предпосылки для аппаратной реализации в виде устройств быстрого поиска. И представлен, положенный в основу запатентованного устройства, способ быстрого поиска по образі{у, разработанный на основании предварительных структурно-лингвистических исследований.
В заключении главы представлена классификация известных алгоритмов сортировки последовательностей и представлен разработанный способ парной параллельной сортировочной транспозиции элементов последовательности, заключающийся в двухфазной компарации их значений. Как показывают результаты моделирования предлагаемого способа сортировки, продолжительность процесса упорядочения зависит от структуры расположения значений элементов, а самый продолжительный процесс выполняется за М пар фаз сравнения, но только в том случае, когда исходная последовательность является обратно упорядоченной. Учитывая частотный показатель встречаемости обратно упорядоченных исходных последовательностей элементов и последовательностей с другими структурами, включая обратно упорядоченные ее фрагменты, Тцр -0,75*М.
Преимущества выбора такого простого способа слияния определяется низким уровнем аппаратной сложности устройства слияния и высокой скоростью работы в связи с достижениями современных электронных технологий.
Третья глава диссертационной работы включает в себя технические решения специализированных устройств: быстрого поиска вхождений, модификации, сортировки и слияния, а также структурно-функциональная организация машины баз данных.
Техническое решение СМБД, базируется на модульной асинхронной архитектуре и основано на информационном взаимодействии специализированных вычислительных модулей, объединённых в СМБД. Два специализированных устройства быстрого поиска и модификации в одном из вариантов конфигура- ции объединяются в модуль универсального символьного процессора, а устройства сортировки и слияния - в модуль процессора сортировки.
Специализированные устройства разработанной СМБД соединяются между собой посредством общей быстродействующей шины или непосредственно через локальные шины, связь с хост-системой осуществляется через магистральную шину.
Устройство сортировки упорядочивает входные данные, полученные по общей быстродействующей и магистральной шинам из ОЗУ или ВЗУ, и передаёт упорядоченные массивы данных, для дальнейшего их слияния, в устройство слияния посредством локальной шины данных. Между собой эти устройства взаимодействуют через шину управления. Входными данными для устройства слияния могут являться как выходные данные устройства сортировки, так и данные из основной (внешней памяти).
Входными данными для устройства поиска вхождений являются данные, полученные по общей быстродействующей и магистральной шинам из ОЗУ. Перед началом работы устройства загружаются данные и адреса данных блока памяти вхождений и данные и адреса данных блока памяти слов. Сигналы запуска устройства и установки в ноль, производят запуск и начальную инициализацию устройства. Найденные адреса вхождений передаются из устройства поиска вхождений на вход устройства модификации по локальной шине данных. Слова из блока памяти слов устройства поиска вхождений загружаются в устройство модификации по локальной шине.
Образцы и их адреса загружаются в память модификаторов и память адресов модификаторов устройства модификации по общей быстродействующей и магистральной шинам из ОЗУ или ВЗУ. При совместной работе с устройством поиска, после выполнения операции подстановки устройство модификации возвращает модифицированные слова устройству поиска по локальной шине. В конфигурации с раздельной работой этих двух устройств результат модификации передаётся в основную память по общей быстродействующей шине.
Устройство сортировки функционирует на основе способа параллельной транспозиции пар сравниваемых операндов заданного массива. Время работы устройства пропорционально длине массива сортируемых последовательностей. Поскольку устройство сортировки имеет ограничения на длину последовательностей из-за ограничений при аппаратной реализации, то в состав СМБД введено устройство слияния двух исходных отсортированных массивов. Особенностью устройства слияния следует считать возможность применения памяти двух массивов с вертикальным групповым однотактным обменом битовыми срезами одновременно по всем числовым линейкам с одинаковыми адресами, т.е. «двух-дольную» статическую регистровую память, реализованную фирмой-производителем на одном кристалле.
Устройство поиска функционирует на основе оригинального алгоритма, особенностью которого является режим безотступного сопоставления с образцом и этим отличается от известного высокоскоростного алгоритма Кнута-Морриса-Пратта (КМП). Отметим, что использование алгоритма быстрого поиска позволяет достигнуть скоростного преимущества до двух раз по отношению к КМП-алгоритму.
Введенное в состав МБД устройство модификации, позволяет в автономном режиме модифицировать атрибуты и кортежи по заданным полям и конкретизировать структуры знаний с высокой производительностью. Совместное функционирование устройств быстрого поиска и модификации, дает возможности реализовать быстрые символьные вычисления при решении типовых задач символьной обработки в СУБД, а также открывает пути эффективной по времени обработки знаний и языков.
Б четвертой главе приводятся алгоритмические средства, включая продукционные алгоритмы управления работой специализированных устройств, а также результаты моделирования устройств и сравнительного анализа скорости работы на основе тестов из Wisconsin Benchmark (язык моделирования: VHDL).
База данных размещалась на RAID массиве 3 уровня общей ёмкостью 128 Гбайт, поддерживающем скорость 100 Мб/с.
В качестве объекта сопоставления выбрана СУБД-машина Ринда (фирма NTT, Япония). Его аналогами разработчики выбрали специализированные машины баз данных Terada (фирма SDF, Япония) и Gamma (фирма Tops, Великобритания).
Программа пользователя измеряет время от начала выполнения запроса до возвращения последнего ряда результатов. Все выполненные запросы были разбиты на 4 категории: простая выборка, объединение, функции МІп (функция вычисления минимума) и Count (функция счёта). Получены зависимости затрат времени при реализации всех названных запросов для аналогов и разработанной СМБД и установлено, что её скоростное преимущество составляет три раза.
Таким образом, выполненные разработки способов, алгоритмов и устройств и проведенные исследования позволили создать новую, эффективную по затратам времени и функциональным возможностям, символьную машину баз данных.
В заключении приводятся основные результаты диссертационного исследования.
В приложении размещен листинг программных средств для моделирования работы алгоритмов и устройств.
Неоднородные многопроцессорные ма шины баз данных (МВД)
Вместе с тем интенсивно разрабатываются [16, 17, 18] многопроцессорные неоднородные МБД, работа которых основывается на нескольких структурных принципах: функциональный параллелизм (рис. 1.2); наличие нескольких уровней обработки и иерархическая организация виртуальной памяти. (Примером использования являются такие проекты, как INFOPLEX, DIALOG. Авторы [17] дают следующее описание данному принципу: «Этот принцип иерархической декомпозиции заключается в выделении иерархии уровней обработки данных в МБД и согласовании с ними иерархии уровней памяти»); возможность распараллеливания операций на каждом уровне обработки и на каждом функциональном уровне.
Что касается принципа распараллеливания обработки на каждом функциональном уровне, то необходимо отметить, что к настоящему времени разработаны схемы распараллеливания функции массовой обработки данных. Распараллеливание других функций, таких, как управления транзакциями, поддержки целостности БД, трансляция запросов и др. пока требует дальнейшего изучения. В связи с этим пока принято, что для выполнения этих функций в МБД должен обязательно присутствовать процессор (или процессоры) общего назначения, т.е. хост-процессор [19].
Поуровневая обработка с использованием иерархии памяти применяется во всех проектах многопроцессорных неоднородных МБД. Такая структура с тремя функциональными подсистемами имеет место, например, в таких проектах, как GRACE, SPIRITS, RDBM, DBC, MPDC, RAPS [2].
Одним из средств повышения скорости обработки МБД, исходя из данной структуры, является механизм опережающей подкачки данных из устройства массовой памяти в системную буферную память, с которым могут совмещаться операции фильтрации. Этот механизм реализован во многих многопроцессорных неоднородных МБД, он позволяет сбалансировать скорости перекачки данных и их обработки в процессорах и за счет этого существенно повысить производительность МБД [6].
Примером использования буферизации нижнего уровня может послужить СУБД-машина базы данных Ринда, разработанная японской компанией NTT и используемая для ускорения обработки неиндексированных запросов реляционной базы данных [20]. Проект архитектуры процессора баз данных Ринда принят в диссертационном исследовании в качестве прототипа, поскольку являет собой оригинальный и высокопроизводительный вариант СУБД-машины по своей структурно-функциональной организации.
Данная СУБД-машина включает в себя процессоры ассоциативного поиска (ПАсП) и процессоры ускорения реляционных операций (ПРО) [21]. ПАсП ведет поиск рядов в дисковой памяти и передает выбранные ряды в основную память. ПРО сортирует ряды, записанные в основную память. Ринда связана с главной универсальной ЭВМ - компьютером семейства DIPS [22, 23] - посредством канальных интерфейсов и находится под управлением своей программы, исполняемой на главной ЭВМ.
Задачу выборки рядов выполняет интеллектуальный дисковый контроллер, осуществляющий поиск непосредственно в дисковой памяти. Таким образом, экономится время центрального процессора (ЦП), расходуемое на перебор всех рядов в таблице, и время, затрачиваемое на пересылку рядов с диска в основную память.
Системы могут эффективно выполнять различные запросы лишь в случае отсортированных рядов. Аппаратный сортировщик с мощной памятью позволяет значительно ускорить сортировку рядов. В результате сокращается расход времени работы ЦП, связанный со сложностью обычных алгоритмов N log(N), где N - число рядов, и уменьшается количество дополнительных обращений к диску, обусловленных недостаточной емкостью памяти.
Являясь машиной баз данных, Ринда разгружает главный компьютер от дополнительных затрат времени и памяти, связанных с выполнением неиндек-сированных запросов. При этом исключается необходимость заменять главный компьютер и дисковую память. Эти возможности реализуются благодаря специальным процессорам ПАсП и ПРО. На рисунке 1.3 приведена типовая структурно-функциональная организация СУБД-машины Ринда. Устройство ПАсП связывает главный компьютер и контроллер дисков с канальными интерфейсами, а устройсво ПРО с аппаратным сортировщиком посредством канала.
Иллюстрация продукционной реализации операций реляционной алгебры
Обрабатываемое слово представляет собой последовательность кортежей из отношений R1 и R2. Продущионный алгоритм (реализуется символьным процессором): переменные, принимающие значение элемента кортежа с первым, вторым и т.д. атрибутами из R1; "о" - разделитель кортежей в обрабатываемом слове; "- " - обозначение заключительной продукции; "#" -обозначение композиции алгоритмов; " "- метка-указатель позиции начала сопоставления. Мета-алгоритм (реализуется хост-процессором) (З, у продукционному алгоритму (в память образцов и модификаторов символьного процессора); І = і + 1; в противном случае - завершить процесс выполнения операции, где N число кортежей в R1; М — число атрибутов. Обрабатываемое слово представляет собой последовательность кортежей из отношений R1 и R2. Продукционный алгоритм: принимающие значение элемента кортежа с первым, вторым и т.д. атрибутами из Юи R2, "$" - метасимвол из расширения рабочего алфавита продукционного алгоритма. Мета-алгоритм: р\ у продукционному алгоритму (в память образцов и модификаторов символьного процессора); і = і + 1; в противном случае - завершить процесс выполнения операции и выполнить аннуляцию $ - , где N - число кортежей в R1 и R2, М - число атрибутов. Обрабатываемое слово представляет собой последовательность кортежей из отношения R1. Продукционный алгоритм: где ф, х, у - литеральные переменные, принимающие значение элемента кортежа с первым, вторым и т.д. атрибутами из R2. Мета-алгоритм: Ф, %,...,у продукционному алгоритму (в память образцов и модификаторов символьного процессора); і = і + 1; в противном случае - завершить процесс выполнения операции, где N число кортежей в R2, М — число атрибутов.
Обрабатываемое слово представляет собой последовательность кортежей из отношения R1. Продукционный алгоритм: кортежа с первым, вторым и т.д. атрибутами из Rl; q X--- " литеральные переменные, принимающие значение элемента кортежа с первым, вторым и т.д. атрибутами из R2. Мета-алгоритм: і = 1; m2: а — k;l; 3 —» k;2; ...; у — k,M; при і N - передать значения а, Р, у продукционному алгоритму на символьный процессор (в память образцов и модификаторов); і = і + 1; перейти на тЗ; в противном случае - завершить процесс выполнения операции; тЗ: g= 1; ml: ф —» kgl; %— kg2 ...\f/ —» кёМ1; g = g + 1; при g N1- передать значения р, %,...,\у продукционному алгоритму и запустить его в работу; выполнить переход на ml, в противном случае - выполнить аннуляцию ар\..уо — и перейти на т2, где N число кортежей в R1, N1 - число кортежей в R2; М - число атрибутов в Rl, Ml - число ат Для реализации операции "деление отношений" требуется разработать адекватный продукционный алгоритм и структуру обрабатываемых слов. Первое отношение R1 является обрабатываемым, а второе R2 - обрабатывающим.
Задача заключается в том, что необходимо сохранить только такие поля (имена и значения) атрибутов, которые не соответствуют совпадению атрибутов из R1. Обрабатываемое слово представляет собой последовательность кортежей из отношения R1: уК1уК2у .. .уКп, где п - число кортежей, а каждый кортеж является словом вида: /V1/V2/ .../Vm/, где V - атрибут из Rl, m - число элементов (атрибутов) кортежа, у - разделитель в обрабатываемых словах. Введём аннулирующую продукцию: где ф-литеральная переменная на множестве атрибутов всех кортежей из R2, который представляет собой слово: vl, v2, ...,vp, где р - число атрибутов; а метасимвол. В результате работы приведенной продукции все совпадающие атрибуты из R1 и R2 будут аннулированы путём их замены на метасимвол. После обработки последовательности кортежей из R1 аннулирующей продукцией необходимо устранить те кортежи последовательности, которые не имеют в своей структуре метасимвол а. С этой целью разработаем следующий продукционный алгоритм: [Лр] - !, где -литеральная переменная на множестве VkUa(k l,2,...,m; U - обозначение операции объединения множеств, m - число элементов (атрибутов) кортежа; Для аннуляции эквивалентных кортежей в результирующем отношении введём продукцию: Тогда общий вид продукционного алгоритма, реализующего операцию деления отношений, будет иметь вид: По аналогии могут создаваться любые другие продукционные алгоритмы, выполняющие моделирование обработки данных в реляционных СУБД, а таюке в других типах СУБД. Приведем иллюстрация продукционной реализации процедурных расширений языка SQL.
Специализированное устройство быстрого поиска позиций вхождений образцов
Устройство поиска вхождений, представленное на рисунке 3.14 содержит: блок памяти образцов, компаратор, блок памяти слов, блок анализа, блок хранения адреса образцов, блок управления, блок анализа скобок, оперативные запоминающие устройства, Д-триггер, электронные ключи, генератор тактовых импульсов, двоичные счётчики, реверсивные регистры, логические элементы И, НЕ-И, ИЛИ. Вместе с тем устройство поиска вхождений образца, содержащее блок памяти слов, блок управления, блок памяти образцов, компаратор, блок анализа, блок хранения адреса образцов, блок анализа скобок имеет следующую внутреннюю структуру. Первый и второй управляющие входы блока управления соединены с первым и вторым управляющими выходами блока памяти образцов, управляющий вход которого соединен с первым управляющим выходом блока управления, с первого по четвертый информационные выходы которого соединены соответственно с первым по четвертый информационными входами блока памяти образцов. Информационный выход блока памяти образцов соединен с первым информационным входом компаратора, управляющий выход которого соединен с пятым управляющим входом блока анализа и с третьим управляющим входом блока управления. Второй и третий управляющие выходы блока управления соединены с первым и вторым управляющими входами блока анализа, первый и второй управляющие выходы которого соединены соответственно с четвертым и пятым управляющими входами блока управления. Седьмой и восьмой управляющие выходы блока управления соединены соответственно с третьим и четвертым управляющими входами блока анализа, информационный выход которого соединен с информационным входом блока хранения адреса образца, с первого по третий управляющие входы которого соединены, соответственно, с четвертым по шестой управляющими выходам блока управления. Девятый управляющий выход блока управления соединен с управляющим входом блока памяти слов, с первого по четвертый информационные входы которого соединены соответственно с пятым по восьмой информационными входами блока управления. Шестой управляющий вход блока управления соединен с управляющим выходом блока памяти слов, информационный выход которого соединен со вторым информационным входом компаратора, седьмой и восьмой управляющие Входы "Пуск" и "Сброс" блока управления являются внешними входами устройства.
При осуществлении поисковых функций в словах, образцы представляются пятью различными комбинациями: 1) нет повторений одинаковых фрагментов слов (итерация) в образце, пример -"абсерватория"; 2) итерация расположена в середине образца, пример - "касса", при этом принято обозначение P{S}T; 3) итерация существует в конце образца, пример - "длинношеее", обозначение P{S); 4) итерация существует в начале образца, примером может служить "ссылка", обозначение (S}P; 5) итерация в образце присутствует и в начале, и в конце, пример — ((a+b) (c-d))» {V}P{W}. С первого по третий вариант представления образца, когда нет итерации, итерация есть в середине образца и итерация существует в его конце, поиск вхождений образца в слове производится с начала слова (с первой его буквы). Символы образца также считываются с начала, т.е. с его первой буквы. Четвертый случай представления образца, при котором итерация находится в начале образца, поиск необходимо производить с конца слова, т.е. с последней буквы. Слово при этом считывается из регистра слова в обратном порядке - последняя буква - первой, предпоследняя - второй и т.д., первая буква - последней. Символы образца считываются в таком же порядке, т.е. в обратном. На рисунке 3.14 представлено устройство поиска. Устройство поиска вхождений содержит блок 1 памяти образцов, компаратор 2, блок 3 памяти слов, блок 4 анализа, блок 5 хранения адреса образцов, блок 6 управления устройством, блок 7 анализа скобок. Приведем назначение блоков: - БПВ - блок служит для хранения образцов, которые являются эталонами поиска; - БПС - блок служит для хранения обрабатываемых слов, в которых будут определяться позиции вхождения образцов; - БАС — блок служит для подсчёта итераций в образце; - КОМ - служит для сравнения символов образца с символами обрабатываемых слов с целью распознавания позиций вхождений образца; - БА - блок служит для анализа сигнала компаратора по обнаружению позиций вхождений образца, а также по определению адреса (позиции) вхождений образцов в обрабатываемом слове; - БХР - блок служит для хранения в памяти адресов позиций вхождений; БУ - блок служит для управления устройством.
Анализ скоростных характеристик продукционного символь-ного процессора
Построение алгоритмов управления каждым из специализированных устройств (быстрого поиска, модификации, сортировки и слияния) в формах продукционных алгоритмических схем приводит к ряду преимуществ, основными из которых является их реализация на ассоциативных процессорах, самоочевидность емкостной сложности (число байт) и низкий уровень сложности моделирующих программ.
Организация функционирования символьной машины баз данных в двух конфигурациях открывает возможности ее использования как в одном экземпляре, так и во многих экземплярах одновременно и асинхронно в соответствии с числом внешних запоминающих устройств (например, жестких дисков с различными типами данных).
В результате проведения эксперимента в конфигурации с раздельным использованием устройств СМБД для получения зависимости затрат времени от длины данных, соответственно, для основных функций: SELECTION 1% (выборка 1 процента данных); SELECTION 10% (выборка 10 процента данных); JOIN AselB (объединение двух отношений); JOIN CselAselB (объединение трёх отношений); MIN Scalar (скалярная операция нахождения минимума); MIN Group (групповая операция нахождения минимума); COUNT Scalar (скалярная операция СЧЁТ); COUNT Group (групповая операция СЧЁТ) - достигается скоростное преимущество в три-четыре раза по отношению к СУБД-машине Rinda ее аналогов: Terada и Gamma для всех перечисленных функций.
Экспериментом для определения скоростных преимуществ устройства быстрого поиска установлено, что аппаратная поддержка акселераци-ониых форм представления образцов при их сопоставлении с обрабатываемым словом в процессах поиска позволяет ускорить процесс до двух раз по сравнению с работой поискового устройства-аналога, функционирующего на основе канонических (марковских) форм представления образцов.
Установлено, что затраты времени на реализацию функции DECODE, реализованной в языке PL-SQL, поддерживаемом СУБД Oracle, в конфигурации с совместным функционированием устройства поиска и модификации с использованием акселерационных форм представления продукций уменьшаются до восемнадцати раз по сравнению с выполнением этой функции на марковском символьном процессоре.
Впервые в рамках парадигмы символьных вычислений решена важная научно-техническая задача, заключающаяся в создании способов, алгоритмических и аппаратных средств символьной машины баз данных с расширенными функциональными возможностями и высокой скоростью реализации функций СУБД. 1. На основе методов прикладной семиотики разработан новый сокращённый набор акселерационных форм продукций, обеспечивающих быстрые символьные вычисления с использованием безотступного режима работы продукции, со скоростным преимуществом до четырех раз, что является основанием для их выбора в качестве объектов аппаратной поддержки. 2. Создан способ и осуществлена алгоритмизация быстрого поиска, особенностью которого является новая схема анализа итераций в обрабатываемом слове и образце, обеспечивающая двукратное преимущество по отношению к алгоритму-аналогу, а также алгоритмы параллельной парной сортировки и последовательного слияния, позволяющие выполнять сортировку и слияние за число шагов, не превышающее число элементов исходной последовательности. Полученные алгоритмы использованы при разработке новых специализированных устройств для символьной машины баз данных. 3. Разработана и исследована структурно-функциональная организация символьной машины баз данных на основе каскада специализированных устройств, объединенных модульной асинхронной разнородной архитектурой, обеспечивающей высокоскоростную реализацию процессов в контурах СУБД с преимуществом в три раза по отношению к аналогу. Разработанная символьная машина баз данных удовлетворяет критериям новизны и существенных отличий, которые заключаются в том, что специализированные устройства, выполняя важные функции СУБД при автономном режиме работы, попарно объединяются в два функциональных модуля: универсальный символьный процессор и процессор сортировки. 4. Использование в архитектуре символьной машины баз данных универсального символьного процессора существенно расширяет ее функциональные возможности и обеспечивает эффективное решение традиционных задан обработки символьной информации: обработка и анализ языков, реализация операций компьютерной алгебры, обработка знаний, объектно-ориентированных структур и т.д. В практическом аспекте результаты исследования и новые технические решения создают основу для дальнейших НИОКР.
