20.31.Oszu М. Т., Valduriez P. Principles of Distributed Database Systems (2nd edition).- Englewood Cliffs, N.J.: Prentice-Hall, 1999.

20.32. Rennhackkamp M. Mobile Database Replication DBMS. - October, 1997. - 10, № 11. Благодаря невысокой стоимости и портативности компьютеров, а также наличию беспроводных коммуникаций стало возможным появление систем распределенных баз данных нового типа, которые имеют свои специфические преимущества и недостатки. В частности, данные в таких системах могут быть реплицированы буквально на тысячи узлов , но эти узлы мобильны, часто отключаются, их операционные характеристики очень отличаются от характеристик обычных узлов (например, в стоимость соединений входит и использование аккумуляторных батарей, и время соединения) и т.д. Исследования таких систем начаты сравнительно недавно (см. [20.1], [20.21]). В этой краткой статье освещены некоторые принципиальные концепции и проблемы.

20.33.Rothnie J. В., Goodman N. А Survay of Research and Development in Distributed Database Management Proc. 3rd Int. Conf on Very Large Data Bases. - Tokyo, Japan, October, 1977. (Эта статья также опубликована в [20.4].) Очень полезный обзор следующих тем.

1. Синхронизация транзакций обновления.

2. Обработка распределенного запроса.

3. Управление при неисправностях компонентов.

4. Управление каталогом.

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

Последняя тема относится к проблеме физического проектирования, которая в разделе 20.8 называется проблемой размещения.

20.34.Rothnie J.B. et al. Introduction to a System for Distributed Databases (SDD-1) ACM TODS. - March, 1980. - 5, № 1.

Работы [20.5], [20.6], [20.24], [20.34] и [20.40] связаны с ранним вариантом распределенной системы SDD-1, которая работала на нескольких компьютерах PDP-10s фирмы DEC, подключенных к сети Aфanet. В этой системе обеспечивалась полная независимость от размещения, фрагментации и репликации. Ниже приводится несколько замечаний по поводу некоторых ее особенностей.

Обработка запросов. Оптимизатор запросов в системе SDD-1 (см. [20.5] и [20.40]) в значительной мере использует оператор полусоединения, который упоминался в главе 6. Преимущество использования полусоединений при обработке распределенных запросов заключается в том, что они могут привести к сокращению объема данных, пересылаемых по сети. Предположим, например, что переменная-отнощение поставщиков S хранится на узле А, переменная-отнощение поставок SP - на узле В, а запрос формулируется следующим образом: Определите результат соединения отношений поставщиков и поставок . Вместо того чтобы пересылать все отношение S на узел В, можно выполнить перечисленные ниже действия.

Вычислить проекцию (TEMPI) переменной-отношения SP по атрибуту St на узле В.

Переслать проекцию TEMPI на узел А.

Вычислить полусоединение (ТЕМР2) проекции TEMPI и отношения S по атрибуту St на узле А.

Переслать полусоединение ТЕМР2 на узел В.

Вычислить полусоединение проекции ТЕМР2 и отношения SP по атрибуту Si на узле В. В результате будет получен ответ на сформулированный выше запрос.

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

size (TEMPI) + size (ТЕМР2) < size (S)

Здесь функция size() возвращает кардинальность отношения, указанного в качестве аргумента, умноженную на длину отдельного кортежа (скажем, в битах). Это позволяет оптимизатору оценивать размер промежуточных результатов типа TEMPI и TEMP2.

Распространение обновления. Алгоритмом распространения обновления в системе SDD-1 предусматривается немедленное распространение (понятие первичной копии в ней не вводится).

Управление параллельностью. Управление параллельностью основано не на механизме блокировок, а на методе синхронизации с использованием времен-H6/X отметок. Цель выбора этого метода состоит в попытке избежать дополнительных накладных расходов на отправку сообщений о блокировке, однако расплатой за это будет относительно небольшая степень параллельности! Дополнительные подробности в этой книге не приводятся, хотя в аннотации к [15.3] очень кратко описана основная идея. Более подробную информацию можно получить в [20.6] и [20.13].

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

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

20.35.Selinger Р. G., Adiba М Е. Access Path Selection in Distributed Data Base Management Systems S.M. Deen and P, Hammersley. Proc. Int. Conf. On Data Bases. - Aberdeen, Scotland; England: Heyden and Sons Ltd., 1980. Cm. комментарий к [20.39].

20.36.Stonebraker M. R., Neuhold E. J. Distributed Data Base Version of Ingres Proc. 2nd Berkley Conf On Distributed Data Management and Computer Networks. - Lowrence Berkley Laboratory, May, 1977.

Работы [20.17], [20.36] и [20.37] связаны с прототипом распределенной системы INGRES. Распределенная система Distributed Ingres состоит из нескольких копий программного обеспечения University Ingres, установленных и запущенных на нескольких компьютерах PDP-lls фирмы DEC. Она поддерживает независимость от расположения (как в системах SDD-1 и R*), независимость от фрагментации, репликацию данных для фрагментов и независимость от репликации. В отличие от систем SDD-1 и R* в системе Distributed Ingres не предполагается, что передача данных в сети обязательно должна быть медленной; наоборот, эта система спроектирована как для медленных сетей дальней связи, так и для сравнительно быстрых локальных сетей. Причем оптимизатор запросов может обнаружить разницу между двумя этими случаями. Алгоритм оптимизации запросов является расщирением стратегии декомпозиции системы Ingres, описанной в главе 17. Более подробно он рассматривается в [20.17].

В системе Distributed Ingres обеспечиваются два алгоритма распространения обновления: эффективный алгоритм, согласно которому обновляется первичная копия и управление возвращается данной транзакции (причем распространение обновлений выполняется параллельно с помощью набора подчиненных процессов), а также надежный алгоритм, согласно которому все копии обновляются одновременно [20.37]. В обоих случаях управление параллельностью основано на механизме блокировки, а управление восстановлением - на протоколе двухфазной фиксации (с некоторыми усоверщенствованиями).

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

20.37. Stonebraker М. R. Concurency Control and Consistency of Multiple Copies in Distributed Ingres IEEE Transactions on Software Engineering, - May, 1979. - 5, № 3.

Cm. комментарий к [20.36].

20.38. Wen-Syan Li and Clifton C. Semantic Integration in Heterogeneous Databases Using Neural Networks Proc. 20th Int. Conf. on Very Large Data Bases. - Santiago, Chile, September, 1994.

20.39. Williams R. et al. R*: An Overview of the Architecture P. Scheuermann. Improving Database Usability and Responsiveness. - New York, N.Y.: Academy Press, 1982. (Эта работа также опубликована в виде отчета: IBM Research RJ3325. - December, 1981.)

В работах [20.12], [20.29], [20.35] и [20.39] обсуждается система R*, которая является распределенной версией системы System R. В системе R* обеспечивается независимость от расположения, но не поддерживаются фрагментация и репликация, а значит, не обеспечивается независимость от фрагментации и репликации. По той же причине для данной системы не возникает вопрос о распространении обновления. Управление параллельностью основано на механизме блоки-