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

Реферат

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

Введение

Распределенная база данных - это набор данных, которые логически принадлежат одной и той же системе, но распределены по узлам компьютерной сети. Система управления распределенной базой данных (DDBMS) определяется как система программного обеспечения, которая обеспечивает управление системой распределенной базы данных и делает распределение прозрачным для пользователей [1-2]. Нет необходимости в том, чтобы системы баз данных были географически распределены. Узлы распределенной базы данных могут иметь один и тот же сетевой адрес и могут находиться в одной и той же комнате, но связь между ними осуществляется по сети, а не по общей памяти. Сеть связи является единственным общим ресурсом для DDBMS [1]. Поскольку технологии связи, аппаратные средства, программные протоколы стремительно развиваются, а цены на сетевое оборудование снижаются с каждым днем, разработка систем распределенных баз данных становится все более и более осуществимой. Разработка эффективной распределенной базы данных является одной из основных исследовательских задач в области баз данных и информационных технологий.

Распределенная обработка в системах управления базами данных (СУБД) является эффективным способом повышения производительности приложений, которые манипулируют большими объемами данных. Это может быть достигнуто путем удаления не относящихся к делу данных, к которым обращаются во время выполнения запросов, и путем сокращения обмена данными между сайтами, что является двумя основными целями проектирования распределенных баз данных [2]. Основная задача распределенных баз данных systemdesigns состоит в том, чтобы сделать фрагментацию отношений в случае реляционных база данных или классы в случае объектно-ориентированных баз данных, размещение и репликация фрагментов на разных сайтах распределенной системы и локальная оптимизация на каждом сайте [1-3].

Фрагментация - это метод проектирования, позволяющий разделить одно отношение или класс базы данных на два или более разделов, так что комбинация разделов обеспечивает исходную базу данных без потери информации [1]. Это уменьшает количество ненужных данных, к которым обращаются приложения базы данных, тем самым уменьшая количество обращений к диску. Фрагментация может быть горизонтальной, вертикальной или смешанной / гибридной. Горизонтальная фрагментация (HF) позволяет разделить отношение или класс на непересекающиеся кортежи или экземпляры. Вертикальная фрагментация (VF) позволяет разделить отношение или класс на непересекающиеся наборы столбцов или атрибутов, кроме первичного ключа. Также предлагается сочетание горизонтальной и вертикальной фрагментации со смешанной или гибридной фрагментацией (MF) [3]. Распределение - это процесс назначения фрагментов базы данных на сайтах распределенной сети. Когда данные распределены, они могут быть либо реплицированы, либо сохранены как одна копия. Репликация фрагментов повышает надежность и эффективность запросов только для чтения, но увеличивает стоимость обновления [1].

Основными причинами расшатывания отношений являются: увеличение локальности ссылок на запросы, отправляемые в базу данных, повышение надежности и доступности данных и производительности системы, балансировка емкости хранилища и минимизация расходов на связь между сайтами [1-4].

Предыдущие техники HF, VF или MF имеют следующие общие проблемы:

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

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

Остальная часть этой статьи организована следующим образом. Во втором разделе представлены литературные обзоры техники HF, VF и MF. Раздел 3 описывает модель системы, которую мы предложили. Наши результаты и обсуждение представлены в разделе 4. Наконец, раздел 5 завершает работу с дальнейшими направлениями исследований.

Обзор литературы

HF с использованием минимального предиката впервые был предложен Ceri et al. (1982) [5]. Нават и соавт. (1984) использовали матрицу использования атрибутов (AUM) и алгоритм энергии Бонда для получения вертикальных фрагментов [6]. Navathe и Ra (1989) улучшили предыдущую работу по VF, предложив алгоритм с использованием графической техники [7]. Shin и Irani (1991) предложили основанный на знаниях подход, при котором исходные пользовательские кластеры основаны на пользовательских запросах к базе данных и знаниях о данных [8]. Ра (1993) представил основанный на графике алгоритм для HF, в котором предикаты группируются на основе сродства предикатов [9]. Чакраварти и соавт. (1994) представили оценщик разделов для измерения качества VF [10]. Навате и др. (1995) предложили метод MF. Входные данные процедуры содержат таблицу соответствия предикатов и таблицу соответствия атрибутов [3]. Ozsu и Valduriez (1999) предложили итеративный алгоритм COMMIN для генерации полного и минимального набора предикатов из заданного набора простых предикатов [1]. Cheng et al. (2002) представили подход фрагментации на основе генетического алгоритма, который рассматривает горизонтальную фрагментацию как проблему коммивояжера [11]. Бай Су и др. (2004) вводили матрицу сродства предиката для построения графа сродства предиката, таким образом определяя горизонтальные фрагменты класса [4]. Ма и соавт. (2006) использовал атрибут использует частотную матрицу (AUFM) и модель стоимости для VF [12]. Альфарес и др. (2007) использовали AAM для создания групп на основе значений сродства [13]. Марва этал. (2008) использует матрицу запросов экземпляра для горизонтального фрагментирования объектно-ориентированной базы данных [16]. Abuelyaman (2008) предложил статический алгоритм StatPart для VF [15]. Mahboubi H. и Darmont J. (2009) использовали сродство предикатов для HF в хранилище данных [16].

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

Предлагаемый аглоритм

Чтобы решить проблему принятия правильного решения о фрагментации на начальном этапе распределенной базы данных, мы предоставили новый метод фрагментации. То есть фрагментировать отношение по горизонтали в соответствии с местоположением приоритета его атрибутов. Приоритет локальности атрибута (ALP) можно определить как значение важности атрибута по отношению к сайтам распределенной базы данных. Таблица ALP будет построена дизайнером базы данных для каждого отношения DDBMS во время проектирования базы данных с помощью модифицированной матрицы CRUD (Create, Read, Update и Delete) и функций стоимости. Блок-схема нашей системы изображена на рисунке 1.

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

Матрица CRUD данные в местоположение представляет собой таблицу, в которой стрелки указывают атрибуты сущностей отношения, а столбцы указывают различные местоположения приложений [18]. Она используется системными аналитиками и дизайнерами на этапе анализа требований жизненного цикла разработки системы цикл принятия решения о сопоставлении данных в разных местах [17-18]. Мы изменили существующую матрицу CRUD в соответствии с нашим требованием HF и назвали ее Модифицированная матрица создания, считывания, обновления и удаления (MCRUD). Это таблица, построенная путем размещения предикатов атрибутов отношения в виде строк и приложений сайтов DDBMS в качестве столбцов. Мы использовали MCRUD для генерации таблицы ALP для каждого отношения.

Мы рассматривали стоимость как усилие по доступу и изменению определенного атрибута отношения приложением с определенного сайта. Для вычисления приоритета атрибута отношения мы берем матрицу MCRUD отношения в качестве входных данных и используем следующие функции стоимости (рис. 2).

Для простоты мы предположили, что fC, fR, fU и fD = 1 и C = 2, R = 1, U = 3 и D = 2. Обоснование предположения состоит в том, что во время разработки распределенной базы данных разработчик не будет знать фактические частоты чтения, удаления, создания и обновления определенного атрибута из различных приложений сайта и, как правило, обновление требует больше затрат, чем создание и удаление. Чтение из базы данных всегда имеет невысокую стоимость.

После построения таблицы ALP для отношения будет создан предикат setPwill для атрибута с наивысшим значением приоритета в таблице ALP. Наконец, каждое отношение будет фрагментировано горизонтально с использованием предикатов P в качестве предиката выбора. Процедуры могут быть четко поняты из следующего алгоритма и псевдокода (рис. 3, 4).

Результаты

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

Мы вычислили приоритет локальности каждого атрибута из матрицы счетов MCRUD в соответствии с функциями стоимости уравнения (рис. 2).

Значения ALP всех атрибутов отношения были вычислены из его матрицы MCRUD. Атрибут с наивысшим значением приоритета будет рассматриваться как наиболее важный атрибут для фрагментации.

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

Выводы

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

Список использованной литературы

1. M.T. Ozsu and P. Valduriez, Principles of Distributed Database Systems, 2nd ed., New Jersey: Prentice-Hall, 1999.
2. S. Ceri and G. Pelagatti, Distributed Databases Principles and System, 1st ed., New York: McGraw-Hill, 1984.
3. S. Navathe, K. Karlapalem, and M. Ra, A mixed fragmentation methodology for initial distributed database design, Journal of Computer and Software Engineering Vol. 3, No. 4 pp 395–426, 1995.
4. F. Bai, M. Mattoso, and G. Zaverucha, A distribution design methodology for object DBMS, Distributed and Parallel Databases, Springer, Vol. 16, No. 1, pp. 45–90, 2004.
5. S. Ceri, M. Negri, and G. Pelagatti, Horizontal data partitioning in database design, in Proc. ACM SIGMOD, 1982, pp. 128–136.
6. S.B. Navathe, S. Ceri, G. Wiederhold, and J. Dour, Vertical partitioning algorithms for database design, ACM Transactions on Database Systems (TODS), Vol. 9, No. 4, pp. 680–710, 1984.
7. S.B. Navathe, and M. Ra, Vertical partitioning for database design: A graphical Algorithm, ACM SIGMOD Record, Vol. 14, No. 4, pp. 440-450, 1989.
8. D.G. Shin, and K.B. Irani, Fragmenting relations horizontally using a knowledgebased approach, IEEE Transactions on Software Engineering (TSE), Vol. 17, No. 9,pp. 872–883, 1991.
9. M. Ra, Horizontal partitioning fordistributed database design, In Advances in Database Research, World Scientific Publishing, pp. 101–120, 1993.
10. S. Chakravarthy, J. Muthuraj, R. Varadarajan, and S. B. Navathe, An objective function for vertically partitioning relations in distributed databases and its analysis, Distributed and Parallel Databases, Springer, Vol. 2, No. 2, pp. 183–207, 1994.
11. C.H. Cheng, W.K. Lee, and K.F. Wong, A genetic algorithm-based clustering approach for database partitioning, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 32, No. 3, pp. 215–230, 2002.
12. H. Ma, K.D. Schewe, and M. Kirchberg, A heuristic approach to vertical fragmentation incorporating query information, in Proc. 7th International Baltic Conference on Databases and Information Systems (DB&IS), 2006, pp. 69–76.
13. M. AlFares et al, Vertical Partitioning for Database Design: A Grouping Algorithm, in Proc. International Conference on Software Engineering and Data Engineering (SEDE), 2007, pp. 218-223.
14. F.F. Marwa, I.E. Ali, A.A. Hesham, A heuristic approach for horizontal fragmentation andalllocation in DOODB, inProc.INFOS 2008, 2008, pp. 9-16.
15. E.S. Abuelyaman, An optimized scheme for vertical partitioning of a distributed database, Int. Journal of Computer Science & Network Security, Vol. 8, No. 1, 2008.
16. H. Mahboubi and J. Darmont, Enhancing XML Data Warehouse Query Performance by Fragmentation, in Proc. ACM SAC09, 2009, pp. 1555-1562.
17. J. Whitten, L. Bentley, and K. Dittman, Systems Analysis and Design Methods, 6th ed, McGraw-Hill, 2004.
18. P. Surmsuk, The integrated strategic information system planningMethodology, IEEE Computer Society Press, pp. 467-475, 2007.