Разработка программного обеспечения для формирования базы данных для государственной итоговой аттестации 9 классов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? в РЦОИ.
Раздел IIМатематическое обеспечение
2.1Правила разрешения конфликта версий. Общие положения.
Введем следующие обозначения состояний записей:
nil - с записью ничего не произошло;
ins - запись добавлена;
upd - запись модифицирована;
del - запись помечена на удаление.
Также обозначим через t момент времени, в который произошло изменение. Для состояния nil обозначения момента времени не требуется. Необходимо описать состояние записи во всех базах данных, для обозначения того, к какой базе относится состояние или момент времени будем использовать нижний индекс.
Пусть имеется две БД, одну из которых обозначим DB1, вторую - DB2. Предположим, что некоторая запись была создана в DB1, а затем реплицирована в DB2. После этого предположим, что в DB1 запись была изменена, а в DB2 - удалена, при этом действие в DB2 произведено позже, чем в DB1. В этом случае общее (учитывающее все БД) состояние записи будем обозначать как
1<t2 & upd1 & del2,
где нижний индекс указывает индекс БД, в которой произошло относящееся к ней изменение состояние записи.
Результатом работы алгоритма должны явиться некоторые действия, которые следует предпринять для устранения конфликта версий. Для обозначения таких действий возьмем уже введенные обозначения:
nil - ничего не делать;
ins - добавить запись;
upd - обновить запись;
del - пометить запись на удаление.
Как и при обозначении состояний, нижний индекс будет указывать БД, в которой следует произвести действие.
Правило разрешения конфликтов версий записи выражается в форме логического следования или импликации (если - то), поэтому будем использовать следующую запись:
t1<t2 & upd1 & del2 del1 & nil2.
Запись следует читать следующим образом: если изменение в DB1 произошло раньше, чем в DB2 и запись была изменена в DB1 и удалена в DB2, то необходимо ее пометить на удаление в DB1 и ничего не предпринимать в DB2. Левая часть этого выражения состоит из трех предикатов (соотношение моментов времени - это один предикат), объединенных оператором логической конъюнкции. Приведенное правило может сработать только в случае, если все три предиката в левой части выражения истинны.
В общем случае правила для разрешения конфликта версий для N баз данных записываются в виде:
t1 i1 t2 i2 тАж iN-1 tN & s1 & s2 & тАж & sN a1 & a2 & тАж & aN,
где ti, i = 1...N - момент времени, в который произошло изменение в БД i;j = {, =} или (), j=1тАжN-1 - соотношение моментов времени tj и tj+1;i, i = 1...N - состояние записи в БД i;i, i = 1...N - действие, которое следует предпринять для разрешения конфликта версий записей в БД i.
Левая часть этой импликации состоит из N+1 предикатов, правая - ровно из N действий. Полностью процесс разрешения конфликта версий записей состоит из набора таких правил. Для того, чтобы левые части импликаций были полными по смыслу и непротиворечивыми, необходимо чтобы они содержали все возможные сочетания предикатов только один раз. В противном случае возможно возникновение ситуации, при которой либо невозможно будет разрешить конфликт версий записи (отсутствует соответствующий набор предикатов), либо этот конфликт будет разрешаться неоднозначно (сочетание предикатов встречается более одного раза). Во - первых, в наборе правил левые части должны иметься для любого случая, который может возникнуть при эксплуатации БД. Во - вторых, эти части в одном наборе не могут повторяться.
С точки зрения теории следует взять общее состояние конкретной записи и последовательно перебирать все правила, вычисляя левые части импликации до тех пор, пока не найдется такая импликация, в которой все предикаты левой части будут истины. Тогда для разрешения конфликта следует применить к копиям записи с ключом RK в каждой БД соответствующие действия, которые описаны в правой части импликации. После того, как найдено такое правило дальнейшие вычисления производить не следует и алгоритм может перейти к обработке следующего конфликта версий.
С точки зрения практики решение задачи видится несколько по-иному. Каково бы не было количество баз, количество вариантов этого предиката не превышает 3N-1, если использовать три вида соотношения времен (, =) и 2N-1 - если использовать два вида соотношения (). Таким образом, можно закодировать все соотношения моментов времени изменения записи не более чем 3N-1 значениями, для чего использовать соответствующую функцию. Типы изменения состояний также возможно закодировать, ведь каждая запись может находиться только в одном из состояний. После осуществления этих операций требуется найти такое правило, левая часть которого будет в точности совпадать с полученными кодами.
Как только такое правило найдено, необходимо исполнить действия, описанные в правой его части. При этом полю TransTime присваивается значение реального времени. После урегулирования всех конфликтов версий следует зафиксировать время окончания репликации. Это требуется для того, чтобы внесенные изменения не участвовали в следующей репликации.
2.2Схема Звезда
В центр звезды помещают базу данных, которую считают главной или ведущей. Все прочие базы считаются подчиненными или ведомыми. Обычно, при возникновении конфликта версий он разрешается в пользу состояния, которое имеет запись в главной базе данных. Поскольку рассматриваемые правила позволяют более точно характеризировать состояние записей и предполагают более сложные