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

р Г о СЗ

• " РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ КИБЕРНЕТИКИ

На правах рукописи УДК 681.3

КУЗНЕЦОВ Сергей Дмитриевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА БСЗЬ-СЕРВЕРА

Специальность 05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва 1993

Работа выполнена в Институте проблем кибернетики Российской Академии наук.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

Доктор физико-математических наук, .профессор

Доктор физико-математических наук, профессор Гребенников Е.А.

ВЕЛУЩАЯ ОРГАНИЗАЦИЯ:

Факультет вычислительной математики и кибернетике

Московского государственного университета ни. , М.В.

Ломоносова

Защита состоится "——"--19— года в - часов на

заседании Специализированного Совета Д 003.78.01 по защите диссертаций на соискание ученой степени доктора наук при Институте проблем кибернетики РАН по адресу: 117312, Москва, ул. Вавилова,

Калнниченко АЛ.

Доктор физико-математических наук, профессор Любимский ЭД.

37.

г

С диссертацией можно ознакомиться в библиотеке ИПК РАН.

Автореферат разослан

г

Ученый секретарь Специализированного Совета-кандидат физ.-мат. наук

Диссертационная работа посвящена главным образом научным и практическим результатам, полученным при проектировании и разработке свободно распространяемого SQL-сервера. Речь идет о современной мобильной реляционной СУБД, ориентированной на применение стандартного языка . баз данных SQL, основанной на использовании архитектуры клиент-сервер, предназначенной для применения в открытых распределенных системах в стандартной среде ОС UNIX и, наконец, входящей в Фонд свободного программного обеспечения, т.е. доступной бесплатно вместе с исходными текстами и документацией для всех желающих.

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

В работе пол учены следующие основные новые научные результаты:

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

на основе применения кластерной технологии проектирования программных систем со внутренней асннхронностыо разработана I архитектура ядра реляционной СУБД, сочетающая естественность организации, должный уровень эффективности и высокую степень' мобильности; j •

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

асинхронности доступа и надежности хранения данных при сравнительно низких расходах ресурсов процессора и внешней памяти;

проанализированы проблемы и намечены пути исследований и разработок объектно-ориентированных, темпоральных и дедуктивных систем баз данных на основе реализованных инструментальных средств.

Основное практическое значение работы состоит в предоставлении для использования современной мобильной реляционной системы управления базами данных с полной реализацией стандартного языка баз данных SQL, пригодной для построения прикладных . информационных систем, инструментальных систем высокого уровня, применения в учебных целях и для. проведения научно-исследовательских работ. Особое значение имеют свободный характер распространения системы вместе с документацией и исходными текстами и наличие отечесгвнного сопровождения и технической поддержки. Следует отметить также, что система разрабатывалась в рамках международного проекта GNU и должна быть включена с .,Фонд свободного программного обеспечения, доступный программистам рсего мира.

Результаты диссертационной работы опубликованы в научной печати и докладывались на различных представительных конференциях и семинарах: Всесоюзных конференциях по базам данных и знаний, конференциях и семинарах Ассоциации пользователей ОС UNIX, семинаре Московской секции ACM SIGMOD, семинаре отдела вычислительных систем и сетей CWI (Нидерланды) и т.д. Материалы диссертации использовались в учебных курсах, прочитанных автором в 9 Московском инженерно-физическом институте и Высшей компьютерной школе МГУ им. М.В. Ломоносова.

Содержание диссертационной работы

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

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

Система управления реляционными базами данных System R разрабатывалась в исследовательской лаборатории фирмы IBM в 19751979 г.г. Эта работа оказала революционизирующее влияние на развитие теории и практики реляционных систем во всем мире. Именно System R практически доказала жизнеспособность реляционного подхода к управлению базами данных. После успешного завершения работ по созданию этой системы и получения .экспериментальных результатов ее Л использования был разработан целый ряд коммерчески доступных реляционных систем, в том числе и на основе непосредственного развития System R.

Этот аспект System R, безусловно, очень важен, но не менее, а может быть и более важен практический опыт, преобретенный при разработке этой системы. Практически во всех более поздних реляционных СУБД в той или иной степени используются методы, примененные в System R.

Далее рассматриваются некоторые распространенные в настоящее время коммерческие реляционные СУБД. Основная цель этого раздела

показать требования к СУБД со стороны рынка' и продемонстрировать важность соответствия возможностей СУБД требованиям открытых систем.

В качестве образцов выбраны четыре СУБД - DB2, Ingres, Oracle и Informix, чтобы иметь возможность выявить трн разных подхода в мире современных реляционных коммерческих СУБД:

ориентация на класс аппаратных средств соответствующими операционными системами (подход DB2);

ориентация па . класс родственных операционных . систсмсемейства UNIX (подход Ingres);

создание "независимого" от аппаратуры и операционных систем пакета с возможностью его • настройки на конкретную аппаратуру и ОС (подход Oracle и Informix).

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

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

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

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

15 следующем разделе конспективно описываются наиболее важные с точки зрения автора направления современных исследований н разработок в области СУБД. Мы стремимся показать, что в ,большинстве случаев реляционные системы являются основным средством исследований и построения прототипов новых систем, рассмотрены основные черты следующих направлений:

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

активные базы данных; дедуктивные "базы данных; темпоральные базы данных;

интегрированные или федеративные системы и мультибазы

« данных;

СУБД следующего поколения; объектно-ориентированные базы данных.

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

Эта диссертационная работа в основном посвящена реализации свободно доступного SQl.-cepuepa. Поэтому нтораи глаиа целиком посвящается языку SQL. В ней кратко рассматривается история языка

SQL и его современное состояние, а также описываются основные свойства варианта языка, реализуемого в данной СУБД.

Глава начинается с рассмотрения особенностей языка, реализованного в System R. Вся история SQL началась именно с этой системы, и этот вариант языка, хотя и не был до конца проработан, содержал практически все идеи.

Язык для взаимодействия с БД SQL появился в середине 70-х и был разработан в рамках проекта экспериментальной реляционной СУБД System R. Исходное название языка SEQUEL (Structured English Query Language) только частично отражает суть этого языка. Конечно, язык был ориентирован главным образом на удобную и понятную пользователям формулировку запросов к реляционной БД, но на самом деле уже на начальной стадии являлся полным языком {ЗД, содержащим помимо операторов формулирования запросов и манипулирования БД средства определения н манипулирования схемой БД; определения ограничений целостности и триггеров; представлений БД; структур физического уровня, поддерживающих эффективное выполнение запросов; авторизации доступа к отношениям и нх полям; точек сохранения транзакции и откатов. В языке отсутствовали средства синхронизации доступа к объектам БД со стороны параллельно выполняемых транзакций: с самого начала предполагалось, что необходимую синхронизацию неявно выполняет СУБД.

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

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

Наиболее близкими к System R являлись две системы фирмы IBM - SQL/DS и DB2. Как кажется (документальных подтверждений этому автор ' не имеет), обе эти системы прямо использовали реализацию System R. Отсюда предельная близость реализованных диалектов SQL к SQL System R. Из SQL System R были удалены только те части, которыс^были недостаточно проработаны (например, точки сохранения) или реализация которых вызывала слишком большие технические трудности (например, ограничения целостности и триггеры). Можно

назвать этот путь к коммерческой реализации SQL движением сверху вниз.

Другой подход применялся в таких системах, как Oracle и Informix. В этих системах, реализация SQL происходила "снизу вверх". В первых выпущенных на рынок реализациях SQL в этих системах использовалось минимальное и очень ограниченное подмножество SQL System R. В частности, в первой известной автору реализации SQL в СУБД Oracle' в операторах выборки. не допускалось использование вложенных подзапросов.

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

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

Принятый в 1989 г. Международный стандарт SQL во многих частях имеет чрезвычайно общий характер и допускает очень широкое толкование. В этом стандарте полностью отсутствуют такие важные разделы, как манипулирование схемой БД и динамический SQL Многие важные аспекты языка в соответствии со стандартом * определяются в реализации.

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

Наконец, d заключительном разделе этой главы рассматривается реализуемый в нашей системе вариант языка SQL и разновидности его использования.

Учитывая практическую направленность этого проекта, мы не. могли взять за основу SQL System R: в этом случае работа носила бы исключительно исследовательский характер. Отсутствие, полных описаний не позволяла воспользоваться диалектом SQL какой-либо коммерческой СУБД. Выполнение проекта было начато в конце 1991 г., когда еще не был принят стандарт SQL2. Доступные проекты этого стандарта были стишком "сырыми" для их практического использования. Поэтому единственной реальной возможностью была опора на Стандарт SQL с необходимыми уточнениями и расширениями.

Уточнения диктовались тем, что проект ориентирован главным образом на использование среды ОС UNIX (большинство неточностей стандарта связаны как раз с отсутствием ориентации в нем на какую-либо операционную среду). Расширения определялись в основном на ; основании здравого смысла в совокупности с анализом доступных j диалектов коммерческих систем и проектов стандарта SQL2. Так, | например, для упрощения реализации мы решили в первой версии I системы строго следовать стандарту SQL, не разрешая в одной транзакции смешивать операторы определения схемы БД с другими операторами SQL (в большинстве коммерческих систем это разрешается, хотя и с оговорками), но добавили к стандартному SQL операторы управления индексами и средства динамического SQL.

В третьей глаис рассматриваются вопросы общей организации свободного SQL-сервера. Обосновываются основные проектные решения, принятые на базе анализа известного опыта проектирования и разработки реляционных СУБД; требований к современным сервером БД; особенностей операционной среды и .т.д.

Глава начинается с описания структуры системы. Выделяются два представления структуры: сетевое представление с выделением серверной и клиентской частей и функциональное представление.

Система основана "на использовании архитектуры "клиент-сервер" и предназначена для применения в распределенных открытых системах ' в среде ОС UNIX. Базовым языком СУБД является . SQL, широко распространенный и стандартизованный язык баз данных. В системе выделяются клиентская и серверная части.

Функциональная структура системы включает четыре основных компонента.

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

Компилятор SQL - компонент,' используемый в статике для компиляции операторов языка SQL, встроенных в программу на языке Си (основная часть компилятора не зависит от языка, используемого для встраивания SQL), и в динамике при выполнении операторов динамического SQL.

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

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

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

Исходным является текст программы на традиционном «зыке программирования с включенными в этот текст операторами SQL. Текст программы прежде всего подвергается обработке прекомниляюром. Прекомпилытор разбирает исходный текст и обнаруживает в 'нем операторы SQL. Для каждого такого оператора вызывается компилятор SQL, выполняющий полный разбор оператора и формирующий программу его выполнения. Прекомпшн1тор заменяет в исходном тексте оператор SQL на вызов сопутствующей программы (с параметрами, если это следует из вила оператора SQL). Так обрабатывается любой оператор SQL, даже оператор динамической компиляции PREPARE. В последнем случае в исходном тексте оператор PREPARE фактически заменяется на вызов компилятора SQL.

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

На организацию системы • в большой степени повлияла ее ориентация на использование в качестве базового языка SQL, Это влияние обсуждается в третьем разделе. Язык SQL представляет собой не просто язык запросов, а полный язык БД, обеспечивающий средства определения схемы БД, включая, ограничения целостности, представлений БД, авторизации доступа и т.д. Естественно, что выбор этого языка в качестве базового языка SQL существенно влияет на реализацию. Можно даже сделать более сильное заявление: весьма затруднительно, если вообще возможно, выполнить полную реализацию SQL для СУБД, которая не проектировалась с самого начала соответствующим образом.

Подсистема управления данными и транзакциями SQL-сервера, ориентированного на использование в среде открытых систем на основе ОС UNIX, проектировалась н разрабатывалась в среде другой ОС -- кластерной операционной системы (КЛАСТОС). Влияние этой среды на структурную организацию системы и внутренние и промежуточные интерфейсы рассматривается в четвертом разделе третьей главы.

Созданне сложных программных комплексов часто требует внутренней асннхронносги, что на языке кластерной технологий означает создание подсистем, состоящих из нескольких взаимодействующих между собой и с "внешним миром" кластеров. С точки зрении использования подсистема аналогична кластеру.: она тоже соответствует некоторому объекту, но. в отличии от кластера -| сложному, составному объекту. Имеется возможность построения! подсистем, компоненты которых имеют равноправный доступ к общим) сегментам. Кластерная технология программирования включает в ceoaj не только средства программирования кластеров, но и средства,' проектирования и "сборки" подсистем из компонентов - уже готовый' кластеров и подсистем. |

В ¿том разделе описываются основные решения, принятые при переносе системы н среду ОС "UNIX. Формулируются минимальныр требования к варианту ОС UNIX, под управлением которой мажет

работать система. Описываются усилия, затраченные на достижение Переносимости SQL-сервера, и имеющийся практический опыт.

Необходимо было ответить на вопрос: соответствует ли общая структура ПУДС и .СУБД в целом возможностям среды ОС UNIX? Если бы ответ на этот вопрос был отрицательным, то это означало бы, во-первых, что нужно заново проектировать всю систему, и во-вторых, что в среде ОС UNIX невозможно реализовать правильно спроектированную систему (исходя из общей логичности проекта, выполненного в среде KJIACTOC). Если бы в современных вариантах ОС UNIX, как и двадцать лет назад, было бы только одно средство общения процессов - программный канал (pipe), это поставило бы проект свободного SQL-сервера в очень трудное полжение.

К счастью, распространенность ОС UNIX и его использование при разработки сложных внеядерных программных систем заставили разработчиков этой системы обратить большее внимание на механизмы межпроцессных взаимодействий (IPC). В настоящее время в наиболее' «распространенных вариантах ОС UNIX System V,4 и BSD 4.3 (и в более новых версиях этих систем) одновременно поддерживаются три различных механизма IPC: программные каналы ^включая именованные, позволяющие взаимодействовать процессам, не связанным иерархией родства), очереди сообщений и программные гнезда (sockets).

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

Во всех коммерческих системах наряду со средствами программирования и интерактивной работы с БД на основе SQL поддерживаются средства более высокого уровня: генераторы отчетов, языки запросов на основе форм, средства построения меню и быстрого прототипирования прикладных информационных систем (так называемые языконые с редс7«а четвертою поколения - 4GL), В настоящее время 'трудно ожидать широкого распространения СУБД, не оснащенной такими средствами. Включаются они и н состав программного обеспечения SQL-ccpuepa0

В четвертой глане рассматриваются ociioi.iii.ie решения, принятые и компиляторе SQL свободного SQL-сервера. Компилятор SQL является исключительно важным компонентом любой SQL-ориентиронанной СУБД. Грубо говори, основной функцией компилятора является преобразование непроцедурною представления операторов, заданных на

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

В начале главы описываются основные этапы компиляции операторов SQL. Только в этом разделе некоторое внимание уделяется вопросам организации лексического и синтаксического анализаторов. В следующих разделах рассматриваются только аспекты оптимизации.

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

Для большинства операторов срабатывает вторая фаза компиляции замена имен объектов БД на соответствующие внутренние идентификаторы и проведение полного контроля (существования и схем таблиц, типов столбцов и т.д.) Информация о хранимых в базе данных объектах выбирается из системных каталогов базы данных. На этой же фазе производится контроль авторизации доступа (для тех операторов, для которых это уместно).

На третьей фазе оператор SQL в своем внутреннем представлении подвергается логической оптимизации. В компиляторе SQL-сервера применяются различные преобразования, "улучшающие" начальное представление операторов. Среди этих преобразовании эквивалентные преобразования, после проведения которых получается внутреннее представление, синтаксически эквивалентное начальному (например! приведение запроса к некоторой канонической форме). Применяются и семантические преобразования, когда получаемое представление не является синтаксически эквивалентным начальному, но гарантируется, что результат выполнения преобразованного оператора совпадает Cj результатом оператора в начальной форме прн соблюдении! ограничений целостности, существующих в базе данных. оптимизационным преобразованиям третьей фазы компиляции можно отнести и подстановку (когда это возможно) во внутреннюю форму оператора SQL, определенного на представлении (view) БД, внутренней

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

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

На пятой фазе по внутреннему представлению наиболее оптимального плана выполнения запроса формируется выполняемое ?

,, представление плана. В компиляторе SQL-сервера для этого применяется внутренний процедурный язык, интерпретируемый ' при выполнении оператора.

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

приведение арифметических и логических выражений, « входящих в компилируемый оператор SQL, к канонической форме; подстановка представлений; подстановка ограничений целостности;

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

Наконец, в завершающем г лапу третьем разделе рассматриваются методы проиедурнлации операторов SQL, применяемые на последних этапах компиляции - аналоге фазы генерации кода и компиляторах традиционных языков программирования.

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

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

В пятом главе обосновываются функции, описываются структура подсистемы управления данными и транзакциями (ПУДТ) свободного SQL-сервера и основные решения, примененные при ее реализации.

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

Первый раздел главы посзящен общей организации ПУДТ. В этом ixe разделе коротко описываются основные структуры данных во внешней памяти и внешний интерфейс подсистемы.

С точки зрения внешнего представления ПУДТ - это подсистема, ! состоящая из набора взаимодействующих кластеров (п случае I IOIACTOC) или процессов (в случае UNIX). Специальный компонент ПУДТ - Администратор сразу посте инициализации подсистемы j находится в состоянии приема заявок на установление соединений С j клиентами.

При каждом таком обращении Администратор создает новый экземпляр кластера/процесса Транзакции. Все операции ПУДТ, выполняемые н пределах одной транзакции, выполняются сответствующнм клатером/процессом Транзакции. Поэтому внешний интерфейс именно этого кластера/процесса составляет основу внешнего интерфейс;! ПУДТ в целом. Функционально интерфейс ПУДТ является расширением интерфейса подсистемы RSS СУБД System R. Резидентными компонентами ПУДТ являются кластеры/процессы] ответственные за синхронизацию, журпализацпю, управлению буферами оперативной памяти и сортировку. • !

В следующем разделе обосиопываегса н описывается применяемы: в ПУДТ метод сериалнзашш транзакций - двухфазный протокол иредикфгиых синхронизационных захватов.

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

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

Но в свободном SQL-сервере синхронизация транзакций происходит на уровне ПУДТ, в которой ничего не известно про предикаты исходных запросов на SQL., На этом уровне в роли "языка запросов" выступает интерфейс ПУДТ, а в этом интерфейсе допускаются только очень простые предикаты, а именно, предикаты, представленные в виде логических формул, в которых через конъюнкцию соединены простые условия но поля отношения. Если синхронизацию основывать на захватах таких предикатов, то это вполне разрешимая задача, допускающая простую и наглядную геометрическую интерпретацию.

Третий раздел содержит описание используемого в ПУДТ механизма работы с буферами оперативной памяти и сопутствующих -■'средств синхронизации нижнего, постраничного уровня.

Главное назначение пула буферов - уменьшение числа обменов с внешней памятью за счет удержания в- оперативной памяти копий страниц сегментов. В этом смысле пул буферов - это программно организованный кэш для доступа к базе данных; он подобен системному пулу буферов, через который происходит работа с блочно-ориентированными устройствами в ОС UNIX. Главным отличием пула буферов ПУДТ от системного пула ОС UNIX является то, что назначение первого из них не универсально. В нем находятся только страницы сегментов БД, поэтому буферами можно управлять более оптимально.

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

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

о

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

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

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

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

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

Являясь типичной реляционной СУБД, основанной на архитектуре "клиент-сервер" и функционирующей в открытых распределении}!' вычислительных системах в стандартной среде ОС UNIX, свободны|| SQL-ceiysep может использоваться наиболее естественным образом для производства традиционных для реляционных систем БД приложений: банковских систем, систем учета и резервирования, оффненых систем и т.д.

/

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

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

»> Второй раздел описывает комплекс работ, которые необходимо выполнить для обеспечения соответствия SQL-сервера стандарту языка SQL образца 1992 г.

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

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

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

Второе направление - проектирование и разработка языка запросов к объектно-ориен тированном базе данных. Большинство существующих языков запросов к объектно-ориентированным базам данных относится к классу языков с явной навигацией. Хотя это часто обосновывают стремлением избежать семантического разрыиа ме;»ду языком программирования и языком запросов, одной из объективных причин является отсутствие алгебраической основы обт.ектно-

ориентированных моделей данных, подобной реляционной алгебре для реляционной модели данных.

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

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

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

Заключение содержит краткую сводку основных результатов работы и указание лиц, внесших вклад к ее осуществление.

Заключение

В диссертационной работе получены следующие основные результаты:

1. Спроектирован н реализован мобильный, свободно распространяемый SQL-сервер, поддерживающий стандарт языка SQL 1989 г. и функционирующий в распределенных открытых системах в стандартной среде ОС UNIX.

2. При - реализации компилятора языка SQL обобщены, ■ систематизированы и комплексно применены наиболее современные

методы оптимизации запросов, включая методы логической,! алгебраической и семантической оптимизации. I

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

4. На основе применения Кластерной технологии проектирования программных систем со внутренней асинхроиностмо разработана архитектура ядра реляционной СУБД, сочетающая естественность

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

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

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

7. Проанализированы проблемы и намечены пути исследований и разработок объектно-ориентированных, темпоральных и дедуктивных систем баз данных на основе реализованных инструментальных средств.

Основные результаты диссертации опубликованы и следующих работах:

1. Бяков А.Ю., Иванников В.П., Кузнецов С.Д. Типовая операционная система для центрального процессора вычислительного комплекса // ИТМ и ВТ АН СССР, 1974, препринт

2. Бяков А.Ю':, Иванников В.П., Кузнецов С.Д. Архив центрального процессора // ИТМ и ВТ АН СССР, 1980, препринт

3. Бяков А.Ю., Гонтаренко C.B., Кузнецов С.Д. Кластеры ° операционной системы центрального процессора // ИТМ и ВТ АН

СССР, 1980, препринт

4. Иванников В.П., Бурдонов И.Б., Кузнецов С.Д., Смирнов Ю.П., Юдин В.II. Технологический подход к организации информационных систем / Труды III Всесоюзной конференции "Банки данных" // Таллиннский политехнический институт, 1985, стр. 165174.

5. Кузнецов С.Д., Юдин Ii.ll. Распределенная файловая система с гибкой структурой связей / Тезисы докладов XIX Всесоюзной школы "Автоматизация научных исследований" // Новосибирск, Ин-т автоматики и электрометрии СО АН СССР, I9S5, стр. 63-64

6. Кузнецов С.Д., Юдин H.H. Эволюция файловой системы ОС UNIX / Сб. "Машинно-независимые операционные системы и их

применение в информационных системах" // Москва, МЦНТИ, 1986, стр. 65-76

7. Бурдоноз И.Б., Копытов Г.В., Косачев A.C., Кузнецов С.Д., Смиронов Ю.П. KJIOC: операционная система и технология программирования / Сб. "Вопросы кибернетики. Программное обеспечение высокопроизводительной системы" // Москва, ИСК, 1986, стр. 34-57

8. Кузнецов С.Д., Юдин В.Н. Управление файлами в кластерной операционной системе // Ж. "Автометрия", Новосибирск, N 5, 1986, стр. 19-25

9. Кузнецов С.Д., Миронова 1\Я. Состояние и тендеицни развития баз данных на XI Международной конференции по ОББД / Сб. "Прикладная информатика", Вып. 2 (13) // Москва, Финансы и статистика, , 1987 , стр. 43-59

10. Бурдонов И.Б., Копытов Г.В., Кузнецов С.Д. Структуризация асинхронных программ в кластерной операционной системе / Сб. "Машинно-независимые операционные системы" // Москва, МЦНТИ, 1987, стр. 85-87

11. Бурдоиов И.Б., Иванников В.П., Кретов A.B., Кузнецов С.Д., Юдин В.Н. Переносимая система управления файлами / Сб.

• "Машинно-независимые операционные системы"/ Москва, МЦНТИ, 1987, стр. 88-93

12. Кузнецов С.Д., Юдин В.Н. Освобождение памяти в условиях мультидоступа к базе данных // Ж. "Программирование", N 5, 1988, стр. 29-34

13- Кузнецов С.Д. Состояние и перспективы теории и практики баз данных: опыт аналитического обзора / Сб. "Прикладная информатика", Вып. 15 // Москва, Финансы и статистика, 1989, стр. 153-172.

14. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД // Ж. "Программирование", N 6, 1989, стр. 46-59

15. Кузнецов С.Д. Развитие идей и приложений реляционной СУБД System R / Тем. изд. "Итоги науки и техники. Вычислительные науки", Т.1. // Москва, ВИНИТИ, 1989, стр. 3-75

16. Кузнецов С.Д. Методы оптимизации выполнения запросов О реляцнсушых СУБД / Тем. изд. "Итоги науки н техники! Вычислительные науки". Т.1 // Москва, ВИНИТИ, 1989, стр. 76-153 I

17. Кузнецов С.Д. Выработка оптимальных планов выполнение запросов в реляционных СУБД // Ж."Программирование", N.2, 1У90, стр. 28-43

18. В.П.Иванников, И.Б.Бурдонов, А.С.Косачев, Г.В.Копытов, С.Д.Кузнецов. Принципы организации KJ10C - кластерной операционной системы // Ж."Программирование",Ы.6, 1990, стр. 66-80

19. l.Burdonov, V.lvannikov, G.Kopytov, A.Kosachev, S.Kuznetsov. The CLOS Project: Towards an Object-Oriented Environment for Application Development / In Next Generation Information System Technology, Lecture Notes in Computer Science, V. 504 // Springer Verlag, 1991, pp. 422-427

20. С.Д.Кузнецов, В.Н.Пономаренко. Модульная мобильная система управления данными и транзакциями / Труды 5-й Всесоюзной конференции по базам данных и знаний // ж."УСиМ", N.7, 1991, стр. 37-45

21. Кузнецов С.Д. Объектно-ориентированные базы данных: основные концепции, организация и управление / Труды 5-й

^Всесоюзной конференции по базам данных и знаний // Львов, 1991, препринт, стр. 3-29

22. Кузнецов С.Д. Фонд свободного программного обеспечения и проект GNU / Тезисы докладов Всесоюзного семинара "Прикладные системы для ОС UNIX" // Москва, МЦНТИ, 1991, стр. 5-8

23. И.Б.Бурдонов, Н.В.Игнатьева, С.Д.Кузнецов, В.Н.Пономаренко, С.В.Шпекторов. Функции и организация подсистемы управления памятью и синхронизацией реляционной СУБД / Сб. "Вопросы кибернетики", вып. 165 // Москва, НСК АН СССР, 1991,

' стр. 71-97

24. Кузнецов С.Д. Идеология свободного программного обеспечения и проект GNU: текущее состояние и ближайшие задачи // Ж. "Программирование" N 1, 1992, стр. 3-7

25. Кузнецов С.Д. Свободный SQL-сервер для разработки приложений и проведения исследований в области баз данных / Тезисы докладов Международной конференции SUUG-92 // Ст. Петербург, МЦНТИ, SUUG, 1992, стр. 16-18.