B. Гиперграфы
Вместо того, чтобы представлять транзакции в виде набора дуг, соединяющих вершины, мы использовали их представление в виде одной гипердуги, соединяющей все вершины, к которым обращается данная транзакция. Это представление является несколько более естественным, поскольку число разрезов гипердуг в точности совпадает с числом распределенных транзакций. Кроме того, мы расчитывали, что разделение гиперграфа позволит обеспечить более высокое качество, основываясь на результатах, которые описаны в литературе о разделении графов , и предыдущих статьях сообщества баз данных, которые посвящены использованию такого подхода . Однако после выполнения активного тестирования с применением наиболее популярных библиотек разделения гиперграфов (hMETIS и Zoltan-PHG) мы установили, что разделение графов выполняется быстрее и обеспечивает лучшие результаты. Мы полагаем, что это объясняется более широким использованием и изучением методов разделения графов, в результате чего соответствующие инструментальные средства обладают большей зрелостью.
В результате нам пришлось аппроксимировать гиперграф набором дуг в графе. Известно, что это трудная задача. После пропуска многочисленных тестов мы решили использовать для представления транзакций полные подграфы (clique), а для репликации – звездообразное представление (меньше дуг для кортежей, доступ к которым происходит очень часто). Эта комбинация представлений обеспечила получение хороших результатов и приемлемые размеры графов.
