Часть 6: Реализация механизмов поддержки и порождения ссылок уровня хранения на базе системы хранения XML данных XSS

Ведение статистики

Для организации пространства статистики необходимо знать число обращений к различным элементам хранилища. Подсчет статистики обращений на клиентском уровне возложен на модуль ведения статистики, который находится в серверной части системы. При обращении к свойству объекта в экземпляре контейнерного типа серверу посылается отметка о том, что был прочитан элемент с данным идентификатором. При этом сохраняется только факт обращения к свойству, но не число обращений, поскольку с точки зрения актуальности данных невозможно отличить «полезное» пользовательское обращение к свойству от «неполезных» обращений элементов интерфейса, коих может быть много (например, при перерисовке элементов управления).
Собранная статистика каждого клиентского приложения хранится на сервер, где считается общее число обращений к каждому элементу. Оно равно количеству клиентских приложений, в процессе работы которых данный элемент был затребован. Также в задачи модуля ведения статистики входит построение копии пространства при перестроении хранилища.

Автоматическое порождение ссылок

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

Алгоритм кластеризации

Каждый элемент исходной выборки представлен классом Element.

Рис. 1. Класс объекта выборки.
Свойства:
· Id – идентификатор элемента, соответствующий идентификатору элемента пространства .
· P – число обращений к элементу.
· Tau – ресурсная стоимость поддерева элемента.
· Parent – родительский элемент.
· Children – список дочерних элементов первого уровня.
· Cluster – номер кластера, в который входит элемент.
Создаваемые кластеры представлены объектом Cluster.

Рис. 2. Кластер.
Свойства объекта Cluster:
· Number – номер кластера, генерируется случайным образом при создании кластера.
· Parent – родительский кластер.
· Children – список дочерних кластеров первого уровня.
· Elements – список элементов кластера.
Методы объекта Cluster:
· AddElement – добавляет элемент в кластер (добавляет элемент в коллекцию Elements и проставляет ему номер кластера).
Кластеризация осуществляется объектом ClusteringRoutine.

Рис 3. Класс, производящий кластеризацию элементов.
Основные поля и свойства:
· DoAction – делегат, выполняющийся в процессе обхода дерева.
· Clusters – список сформированных кластеров.
· Distances – список, содержащий вычисленные расстояния между объектами.
Основные методы:
· ClusterData – метод кластеризации, принимает на вход массив элементов, формирует список кластеров и каждый элемент помещает в кластер.
· CalculateDistance – вычисляет расстояние между двумя объектами.
· GetThreshold – вычисляет порог расстояния по заданному списку расстояний.
· GetAllChildren – возвращает список всех дочерних элементов.
· GetRootElements – возвращает список корневых элементов
· RemoveBiggestEdges – удаляет ребра, веса которых превышают вычисленный порог.
· TreeWalk – универсальный метод обхода дерева, вызывает выполнение делегата DoAction.

Алгоритм постобработки

Формирование итогового набора деревьев возложено на класс PostProcessingRoutine.

Рис. 4. Класс постобработки кластеров.
Основные методы:
· PostProcess – метод постобработки, принимает в качестве аргумента список кластеров и возвращает список кластеров, которые являются конечным вариантом набора деревьев раздельного хранения.
· GetClusterTau – вычисляет ресурсную стоимость разбора кластера.
· MergeClusters – сливает два кластера.
· MoveElementToAnotherCluster – перемещает элемент из кластера в кластер.
Результаты
В хранилище было помещено три документа общим размером 250 Мб. На рис. 5 приведены времена отклика сервера на запросы одной из инструментальных операций, использующей эти деревья. Операция является «локальной» и популярной. Данные приведены для первого запуска, когда кэш сервера не содержит данных.

Рис. 5. Времена отклика пакета запросов до перестроения хранилища.
На основании собранной в течение месяца статистики было проведено перестроение хранилища, в результате работы алгоритма из 3 деревьев было выделено 54 дерева раздельного хранения. Ниже приведен график времен отклика первого запуска той же операции после перестроения хранилища:

Рис. 6. Времена отклика пакета запросов после перестроения хранилища.
Среднее уменьшение времени отклика составило 63%. При повторном обращении к данным, содержащимся в кэше, уменьшение времени отклика не значительное, в пределах 5%.
За четыре последующих дня работы среднее время отклика сервера уменьшилось на 33%. Отличие среднего времени отклика от приведенных выше измерений можно объяснить наличием «нелокальных» операций, в частности ежедневно производилось резервное копирование данных, не обладающее свойством локальности, поскольку при такой операции обращение происходит ко всем элементам хранилища. Тем не менее, уменьшение времени отклика на треть является существенным результатом, а разработанный метод позволит в принципе хранить работать документы большого объема.
По мере развития XSS для нелокальных операций будет проводиться собственная оптимизация – расширение объединенного протокола (ОП) специальными командами.

Часть 5: Реализация механизмов поддержки и порождения ссылок уровня хранения на базе системы хранения XML данных XSS

Архитектура подсистемы взаимодействия с сервером XSS

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

Рис. 26. Схема взаимодействия клиентских приложений с XSS.
Ниже будут рассмотрены основные модули, принимающие участие в работе системы «XSS – клиент», в т.ч. будет рассмотрена схема работы адаптера.

Ядро

Ядро является основным компонентом системы. Его инициализация происходит при запуске приложения. Одна из функций ядра – поддержания списка типов, с которыми ведется работа, в актуальном состоянии. При запуске ядра производится анализ зарегистрированных и загруженных в домен приложения сборок, составляется и сохраняется список типов (кэш) с учетом наследования. Также в процессе работы приложения производится контролируемая ядром подгрузка и выгрузка дополнительных сборок. Обновления кэша типов при этом происходит автоматически.

Рис. 1. Диаграмма класса ядра в части взаимодействия с типами.
Ключевые методы для работы с типами:
· RegisterAssembly. Загружает сборку, регистрирует содержащиеся в ней типы.
· UnRegisterAssembly. Выгружает сборку из домена приложения, удаляет принадлежащие ей типы из кэша.
· FindType. Возвращает типа из кэша по имени.
· GetInheritTypes. Возвращает список наследников данного типа.
· GetPK. Получение информации о поле/свойстве типа, содержащего идентификатор (id).

Драйвер работы с XSS.

Драйвер работы с XSS (XSS драйвер) – это модуль, обеспечивающий работу с хранилищем: сохранение и загрузку данных. То есть на XSS драйвер возложены обязанности сериализации и десериализации объектов. В были введены правила отображения объектов в XML представлении:
· Текущий объект становится корневым элементом (тэгом)
· Простое свойство объекта становится атрибутом тэга. При этом атрибуты могут отсутствовать, что означает, что свойство будет проинициализировано значением по умолчанию
· Ссылочное свойство становится вложенным элементом относительно корневого
При этом все элементы имеют обязательный атрибут id, идентифицирующий экземпляр объекта.
В рамках был реализован компонент драйвера XSS:

Рис. 2. Диаграммы класса XSS драйвера.
Ключевой особенностью драйвера является возможность работы в двух режимах: онлайн и оффлайн. В первом режиме обмен данными с хранилищем идет в режиме реального времени, то есть сразу при необходимости загрузки, сохранения или удаления объекта. В режиме оффлайн работа с хранилищем ведется с помощью кэша драйвера. Данные, которые необходимо сохранить или удалить, сперва помещаются в кэш, а с хранилищем изменения синхронизируются единовременно при вызове соответствующей команды. Этот режим работы драйвера может пригодиться в случае отсутствия постоянного доступа к хранилищу.
Кэш объектов представляет собой список записей. Каждая запись списка – обертка над объектом, который непосредственно необходимо кэшировать. «Оберточная» запись предоставляет некоторую дополнительную информацию, для того чтобы программисту не пришлось вычислять ее самому.

Рис. 3. Запись кэша драйвера.
Свойства записи в кэше:
· Object – ссылка на сам объект
· Iid – содержит идентификатор объекта
· IidParent – идентификатор родительского объекта
· HashCode – первоначальный хэшкод объекта, добавленного в кэш; также на нем основана проверка, не допускающая повторного добавления объекта в кэш
· CurrentHashCode – текущий хэшкод объекта в кэше
· IsModified – флаг, указывающий на то, что объект был изменен (в случае есть Hashcode отличается от CurrentHashcode)
· IsDeleted – флаг, которым помечаются объекты для удаления (при вызове метода Delete() драйвера в режиме работы rmLazyCommit)
Поведение XSS драйвера при загрузке/сохранении объектов в зависимости от значения свойства WriteMode определяется следующим образом:
· WriteMode = rmDirectCommit (онлайн режим)

• GetObject – получает объект из XSS, помещает его в кэш
  
• SaveObject – сохраняет объект в кэш, помечает запись IsModified = false
  
• DeleteObject – удаляет объект из XSS и из кэша
  
• Commit – сохраняет в XSS объекты, помеченные IsModified, удаляет объекты, помеченные IsDeleted
  
• Reset – очищает кэш

· WriteMode = rmLazyCommit (оффлайн режим)

• GetObject – получает объект из XSS, помещает его в кэш
  
• SaveObject – добавляет объект в кэш, если его там не было
  
• DeleteObject – если объект был в кэше, помечает его как IsDeleted, иначе добавляет в кэш, а потом помечает IsDeleted
  
• Commit – сохраняет в XSS объекты, помеченные IsModified, удаляет объекты, помеченные IsDeleted
  
• Reset – очищает кэш

Методы работы с данными, реализованные в XSS драйвере:
· GetObject. Загрузка объекта с заданным типом и идентификатором.
· GetObjects. Загрузка всех объектов заданного типа.
· SaveObject. Сохранение объекта.
· SaveObjects. Сохранение массива объектов.
· DeleteObject. Удаление заданного экземпляра объекта из хранилища.
· DeleteObjects. Удаление списка объектов из хранилища.
· Commit. Синхронизация содержимое кэша с хранилищем: объекты для сохранения сохраняются, объекты, предназначенные для удаления, удаляются.
· Reset. Очистка кэша драйвера.

Операционная машина

Операционная машина – компонент, предоставляющий генерацию и выполнение дополнительных операций над типам, определенными в приложении. Примером операций над типом могут являться сложение, получение строкового представления и т.д.
Операционную машину можно разделить на несколько частей:
· Генератор операционной машины
· Кэш сборок операций
· Модуль, отвечающий за доступ к операциям
Генератор операционной машины – часть операционной машины, отвечающая за генерацию новых операций на основе данных о типах, содержащихся в загружаемых ядром сборках. Генератор используется при построении кэша сборок операций. Генерация операций ведется при регистрации сборки в ядре.
Кэш сборок операций – это хранилище операций, физически содержащее скомпилированные библиотеки, содержащие код операций над типами. Кэш поддерживается в актуальном состоянии, то есть при регистрации сборки операции над ее типами генерируются, только если сборка с операциями отсутствует, либо если она устарела относительно регистрируемой сборки (например, в нее были добавлены новые типы). Основные функции кэша:
· Контроль соответствия регистрируемой сборки
· Определение набора операций над типами сборки
· Возможность добавления новых операций
Также в рамках операционной машины определено множество операций над кэшем сборок операций.

Разрешение ссылок на уровне представления

Типовое решение отложенной загрузки заключается в прерывании процесса загрузки, при этом необходимо оставлять соответствующую метку в структуре объектов. Это позволяет загрузить необходимые данные только тогда, когда они действительно понадобятся.
Для разрешения ссылок на уровне представления необходима реализация нескольких функций:
· внесение изменений в XSS драйвер
o при разборе XML-тэга, в котором присутствует атрибут link, драйвер не должен загружать и создавать соответствующий объект;
o драйвер должен сохранять информацию о том, какие объекты не были загружены;
· внесение изменений в структуру объектов с тем, чтобы они поддерживали отложенную загрузку

Варианты реализации отложенной загрузки

Существует четыре основных шаблона при реализации отложенной загрузки [10]:
1) Инициализация по требованию
Признаком того, что ссылочное поле незагружено, является ссылка на null. Основная идея данного подхода заключается в том, что при каждой попытке доступа к полю выполняется проверка, не содержит ли оно значение null.

public Department Dept { get { if (_dept == null) { _dept = LoadData(); } return _dept; } }

Листинг 1. Пример реализации инициализации по требованию на языке C#.
Ключевые особенности инициализации по требованию:

• работает только для полей, обращение к которым происходит через свойство даже в пределах самого класса (самоинкапсулированные поля);
  
• требует связи бизнес-объектов с источником данных.

2) Виртуальный прокси-объект
Виртуальный прокси-объект имитирует объект, являющийся значением поля, либо сам бизнес-объект, однако в действительности ничего в себе не содержит. В этом случае загрузка реального объекта будет выполнена только тогда, когда будет вызван один из методов виртуального прокси-объекта. Преимуществом виртуального прокси-объекта является то, что он "выглядит" точно так же, как реальный объект, который должен находиться в данном поле. Во втором случае оба объекта (бизнес и виртуальный) должны имплементировать один и тот же интерфейс для инкапсуляции типа. Соответственно прокси-объект создает «обертку» для полей бизнес-объекта: содержит в себе логику создания и загрузки объектов полей (она может быть реализовано в виде инициализации по требованию).

Рис. 4 Схема взаимодействия типов при реализации виртуального прокси-объекта.
Положительная сторона данного подхода заключается в том, что не нужно вмешивать в бизнес-объекты. Отрицательный момент состоит в увеличении числа классов и интерфейсов, а также в увеличении количества экземпляров объектов в памяти во время работы программы.
3) Фиктивный объект
Фиктивный объект – это реальный объект с неполным состоянием. Когда он загружается из источника данных, то содержит только свой идентификатор. При первой же попытке доступа к одному из его полей объект загружает значения всех остальных полей. Для большей наглядности фиктивный объект можно представить себе в виде объекта, все поля которого одновременно инициализируются по требованию, или объекта, который является собственным виртуальным прокси-объектом. Возможно, все данные не обязательно загружать за один раз; для большего удобства их можно разбить на группы полей, которые часто используются вместе.
4) Диспетчер значений
Диспетчер значения – это объект, который играет роль оболочки для какого-нибудь другого объекта. Чтобы получить значение базового объекта, необходимо обратиться за ним к диспетчеру значения. При первом обращении диспетчер значения извлекает необходимую информацию из источника данных.

private ValueHolder holder; public Department Dept { get { return (Department)holder.GetValue(); } }

Листинг 2. Пример реализации диспетчера значений на языке C#.
Этот способ имеет ряд недостатков:
· класс должен знать о наличии диспетчера значения (необходимо вносить изменения в бизнес-объект);
· теряются преимущества строгой типизации;
Чтобы избежать проблем идентификации, необходимо гарантировать, что диспетчер значения никогда не будет передаваться методам за пределами его класса-владельца.

Контейнеризация типов

В рамках данной работы для реализации отложенной загрузки предлагается использовать комбинированный способ: контейнеризацию типов. Суть этого подхода заключается в том, что для всех бизнес-типов создаются типы-контейнеры – «обертки». Они являются промежуточным слоем между обращением к свойствам объекта и получением их значений.
Контейнеризация реализована следующим образом: для каждого бизнес-типа создает тип-контейнер, который включает в себя поле упаковываемого типа, а также содержит все свойства и методы, которые были определены в исходном типе. Преобразование осуществляется по следующим правилам:
· бизнес-тип тип-контейнер
· базовый тип базовый тип-контейнер (или супертип)
· поле исходного типа свойство
· свойство исходного типа свойство
· метод исходного типа метод
Операция контейнеризации реализована как одна из операций в наборе OperationMachine. Таким образом, в приложении будет две иерархии типов – исходных и контейнеров, а также супертип. Также на уровне ядра (Kernel) реализована таблица соответствий «тип – тип-контейнер». Она понадобится при загрузке данных для подмены исходного типа на тип-контейнер. Это необходимо для работы XSS драйвера – при загрузке данных он должен создавать объекты соответствующих типов-контейнеров. Фактически, клиентские приложения будут работать только с экземплярами объектов-контейнеров.
При генерации типов-контейнеров на основе исходного типа «копированию» подвергаются все публичные поля, свойства и методы (в том числе статические, виртуальные и переопределенные с сохранением атрибутов). Таким образом, соблюдаются принципы инкапсуляции и наследования в иерархии типов-контейнеров. Также переносятся все атрибуты типа, полей, свойств и методов. Поля и свойства, помеченные атрибутом LK, упаковываются особым образом – с реализацией инициализации значения по требованию. В них проверяется, загружено ли соответствующее свойство объекта исходного типа (см. инициализацию по требованию); если нет, то происходит его загрузка. Перечисленные правила генерации гарантируют, что поведение объекта-контейнера не отличается от поведения объекта исходного типа.
Еще одна функция, реализуемая с помощью типов-контейнеров – это сбор статистики использования свойств.

Часть 4: Реализация механизмов поддержки и порождения ссылок уровня хранения на базе системы хранения XML данных XSS

1 Система хранения данных XSS

Общие сведения
XSS (Xml Storage System) – это система долговременного хранения XML данных, состоящая из двух подсистем:
· Подсистемы хранения (ПСХ)
· Подсистемы обеспечения многопользовательского доступа (ПСМД)
Плюс клиентская часть XSS (CXSS).

Рис. 1. Схема сервера XSS.
ПСХ решает задачи хранения XML деревьев. В качестве внутреннего хранилища могут выступать РБД или файловая система. На уровне ПСХ реализуется функциональность разбора линков и построения общего XML дерева (с разобранными ссылками), над которым организуется реализация аппарата XPath.
ПСМД обеспечивает поддержку многопользовательского доступа. ПСМД отслеживает взаимодействие пользователей c ПСХ, хранит текущие занятые пользователями деревья и узлы и, в рамках объединенного протокола, помечает разрешенную/запрещенную коррекцию. Кроме того, ПСМД обеспечивает хранение всех произведенных средствами объединенного протокола изменений, поддерживает операции запроса истории и отката к предыдущим состояниям.
ПСХ может использоваться в двух вариантах – как непосредственный источник XML данных (локальный вариант), так и источник данных для ПСМД (централизованного многопользовательского хранения). В связи с чем, протокол взаимодействия с ПСМД и ПСХ должен быть объединением протоколов ПСХ и ПСМД. Причем, ПСХ должна обеспечивать взаимодействие по объединенному протоколу для использования локальной и централизованной версии XSS без адаптации взаимодействующих подсистем. При работе в локальной версии часть протокола централизованной версии должна возвращать значения в соответствии с логикой отсутствия ограничений на какие-либо операции.
Предлагаемые в рамках системы долговременного хранения XML данных XSS позволяет решить следующие задачи:
· Общая функциональность. В рамках системы XSS реализуется аппарат хранения xml-документов с поддержкой XPath запросов и запросов, реализующих CRUD операции над деревьями, поддеревьями, элементами и атрибутами документов, находящихся в хранилище.
· Взаимодействие с XSS. Работа с хранилищем организуется посредством протокола https с поддержкой удаленного взаимодействия через интернет или в локальном режиме без установки сервера для поставки XSS как части конечной системы.
· Многопользовательский доступ. Единицей, блокируемой в рамках транзакции, является элемент или поддерево, что позволяет обеспечить одновременную работу нескольких пользователей с документами хранилища.
· Работа с большими массивами данных. В рамках аппарата хранения, реализованы механизмы ссылок и операции выделения частей документов как единиц, загрузка которых осуществляется итеративно, при первом обращении. Что позволяет распределить задержки обработки больших документов по времени и увеличить производительность сервера при работе с большими объёмами данных.
· Возможности по администрированию. В рамках системы XSS поставляется подсистема CXSS, позволяющая решать административные задачи от управления пользователями до выполнения операций резервного сохранения/восстановления данных и мониторинга активности.
Подсистема хранения выполняет следующие функции:
· Получение списка дочерних элементов. В качестве параметра передается id корневого элемента. Если id = null, возвращается список корневых элементов всех XML документов ПСХ.
· CRUD[1] операции над элементом. В рамках операции создания передаётся id родительского элемента. Если id = null, генерируется новый XML документ в рамках ПСХ, а созданный узел становится корнем. В остальных операциях в явном виде передается id элемента.
· CRUD операции над деревом элементов. В рамках данного раздела производятся групповые операции над иерархиями элементов. В рамках операции создания передаётся id родительского элемента. Если id = null, генерируется новый XML документ в рамках ПСХ, содержащий передаваемое дерево. В остальных операции в явном виде передаётся id элемента-корня дерева.
· Контроль ссылочной целостности. Ссылки на элементы должны хранится в хэш-таблице, с хэш-индексом по id ссылающихся элементов. Удаление элемента, в случае наличия на него ссылок, должно быть запрещено. При загрузке элемента, с
непустым атрибутом link, должно контролироваться наличие элемента с заданным id и, в случае корректности, ссылка должна фиксироваться в хэш-таблице.
· Контроль типов. Типы элементов уникальны. При создании/коррекции элемента существующего в системе типа, должно контролироваться совпадение структуры элемента. Предлагается организовать такой контроль по средствам хэш-таблицы типов как в предыдущем разделе.
· Контроль типов-ссылок. Тип элемента, на который ссылается link, должен соответствовать типу элемента-ссылки. При этом, структура элемента-ссылки должна не содержать никаких атрибутов и элементов, кроме id и link.
· Понятие совместимости и наследования типов. Представляет собой набор иерархию наследования типов, для реализации свойств ООА над иерархией элементов. Суть – наследование и переопределение структуры элемента.
· Запрос поддерева типа по существенным типам или типам игнорирования. Операция выделяет из дерева, заданного id корневого элемента, поддерево, листья ми которого являются элементы некоторого типа. Узлы поддерева составляют элементы существенных типов (передаётся как массив типов) или элементы типов отличных от типа игнорирования (передаётся массив типов).
· Выполнение XPath запроса над поддеревом элементов. В параметрах передаётся id родительского элемента дерева, над которым выполняется запрос. Если id = null, запрос выполняется над общим деревом.

Протокол взаимодействия
Взаимодействие с хранилищем происходит посредством объединенного протокола (ОП). Это протокол взаимодействия модуля обработки запросов и внешних систем. Он реализует действия с XML данными (работа с элементами и деревьями) и итеративную загрузку файлов.
П3 = (command, data) : (stream, err_code)
command = {“get_sublist” | “get_elem” | “set_elem” | “create_elem” | “del_elem” | “get_subtree” | “set_subtree” | “create_subtree” | “del_subtree” | “get_typedtree” | “get_xPath” }
П3.1 = (“get_sublist”, elem_id | null) : (xml_stream | null, err_code)
П3.2 = (“get_elem”, elem_id) : (xml_stream | null, err_code)
П3.3 = (“set_elem”, xml_stream) : (null , err_code)
П3.4 = (“create_elem”, parent_elem_id | null) : (xml_stream | null, err_code)
П3.5 = (“del_elem”, elem_id) : (err_code)
П3.6 = (“get_subtree”, elem_id) : (xml_stream | null, err_code)
П3.7 = (“set_subtree”, xml_stream) : (null , err_code)
П3.8 = (“create_subtree”, parent_elem_id | null) : (xml_stream | null, err_code)
П3.9 = (“del_subtree”, elem_id) : (err_code)
П3.10 = (“get_typedtree”, parent_elem_id | null, included_types, excluded_types) : (xml_stream | null, err_code)
П3.11 = (“get_xpath”, parent_elem_id | null, xpath_text) : (xml_stream | null, err_code)

Поддержка ссылок и кэширование
В рассмотренной выше иерархической модели данных одним из недостатков называлось избыточное дублирование данных, возникающее из строгого ограничения иерархической модели – у каждого элемента один родитель. Это ограничение можно было бы обойти (таким образом модифицировав саму модель данных) с помощью ссылок. В нотации XML описан механизм определения ссылок в рамках XML представления данных, но его поддержка в различных парсерах либо не реализована, либо реализована без возможности итеративной загрузки. Благодаря равномерному распределению вычислительных ресурсов разбора больших файлов по времени, итеративный разбор частей документа позволил бы работать с XML документами больших объёмов. Кроме того, это позволило бы переиспользовать данные на уровне хранения. В системе XSS поддержана итеративная загрузка документов с помощью механизма ссылок (линковки). Это позволило обойти ограничение иерархической модели, связать элементы разных деревьев и исключить при этом необходимость дублирования данных для раскрытия множественной ссылочности.
Все элементы (тэги), хранящиеся в XSS, имеют обязательный атрибут id, идентифицирующий их, и опциональный атрибут link. Непустой атрибут link содержит идентификатор элемента и таким образом указывает на узел другого дерева. На стороне приложения ссылки указываются разработчиками с помощью программного атрибута LK (Link Key), применяемого к полям или свойствам объекта. При сохранении такого объекта, XML тэг, соответствующий полю или свойству, будет содержать XML-атрибут link, указывающий на другое поддерево.
Кэш хранилища XSS позволяет оперативнее обращаться к одним и тем же документам в течение одного сеанса работы сервера. При первом обращении к документу его содержимое загружается в память, и в дальнейшем выполнение запросов к этим данным происходит быстрее. Выгрузка документов из памяти происходит по необходимости.

2 Сравнение хранилищ данных

При исследовании существующих средств хранения данных в XML представлении и определении областей применимости каждого средства, были выявлены следующие существенные характеристики:
1. Поддержка native XML
Хранение XML документов без приведения к реляционному виду. Операции над документами хранилища выполняются с помощью XPath/XQuery запросов.
2. Поддержка реляционного представления
Хранение XML документов с приведением к реляционному виду. Операции над документами в хранилище выполняются с помощью SQL запросов.
3. Поддержка смешанного представления
Хранение XML документов возможно как с приведением к реляционному виду, так и в native XML формате. Соответственно, операции над документами в хранилище выполняются с помощью SQL и XPath/XQuery запросов.
4. Поддержка итеративного разбора ссылок XLink/XPointer
В нотации XML описан механизм определения ссылок в рамках XML представления данных. Благодаря равномерному распределению вычислительных ресурсов разбора больших файлов по времени, итеративный разбор частей документа позволил бы работать с XML документами больших объемов. Кроме того, механизм линковки должен сопровождаться контролем ссылочной целостности данных сервера.
5. Поддержка мультидоступа
Функциональность параллельной работы пользователей с документами XML. Обеспечение транзакционной целостности данных при мультидоступе.
6. Атомарный элемент блокировки
При транзакционном многопользовательском доступе большое влияние на масштабируемость и область применимости оказывает размер части документа, блокируемой при транзакционной обработке.
7. Поддержка протоколирования изменений и откатов.
Функциональность ведения протоколов операций и откатов системы к предыдущему состоянию позволяет обеспечить высокую безопасность данных не только на низком уровне хранения, но и на логическом уровне.
8. Оценка области применения
На основании проведенного анализа приводится оценка области применения системы на базе рассматриваемого хранилища.
В ходе анализа были рассмотрены следующие хранилища данных: XSS, реляционные БД (MS SQL Server 2005 и MySql 5.0), XML БД Tamino. В таблице 1-1 приведены сравнительные характеристики систем.
Таблица 1‑1. Сравнительные характеристики сервера XSS, реляционных и XML баз данных.

	Файловые	Реляционные	XML БД
	XSS	MS SQL Server 2005	MySql 5.0	Tamino
1	+ Ядро	+ Тип данных	-	+ Ядро
2	-	+	+	-
3	-	+	-	-
4	+	-	-	-
5	+	+	+	+
6	Любое поддерево документа	XML документ	-	XML документ
7	+	-	-	-
8	I	II, III	III	IV

Оценки характеристик хранилищ:
I. Система хранения XML представления данных с поддержкой ссылок, итеративной подгрузкой частей документа, многопользовательского доступа, блокировок и поддержкой механизмов исполнения XPath запросов.
II. Организация систем на базе XML типа данных реляционной БД обеспечивает поддержку многопользовательского доступа и позволяет использовать XPath/XQuery аппарат запросов. На базе таких хранилищ возможно построение системы распределенной обработки данных. Поддержка смешанного хранения XML позволяет максимизировать производительность при чтении данных, но при модификации требует актуализации данных в обоих представлениях.
III. Приведения XML к реляционному виду обеспечивает поддержку групповых операций и всех плюсов использования реляционной модели. Но такое приведение неоптимально и имеет высокую трудоемкость реализации логики взаимодействия хранилища с частями системы и бизнес-логики обработки.
IV. XML база данных обеспечивает богатый аппарат администрирования и использования XPath/XQuery. Но из-за сложности операций над XML спектр разрешимых задач на больших объемах данных ограничен вычислительной мощностью системы.
По оценкам характеристик наиболее подходящей системой для хранения слабоструктурированных иерархических данных большого объема является сервер XSS. Его ключевые особенности – поддержка ссылок и возможность итеративной загрузки данных на уровне хранилища. Однако механизм ссылок должен быть поддержан и на уровне клиента. Также поскольку область задач предполагает изменение структуры данных во времени и изменение частоты обращения к данным во времени, то необходимо реализовать автоматическую расстановку ссылок. За счет распределения нагрузок по времени и минимизации избыточности данных это позволит добиться максимального быстродействия загрузки данных на широком классе задач различных областей применения сервера.

---

[1] CRUD – четверка операций: создание, чтение, обновление, удаление (Create, Read, Update, Delete)

Часть 3: Реализация механизмов поддержки и порождения ссылок уровня хранения на базе системы хранения XML данных XSS

Обзор средств хранения данных

Каждая база данных (БД) и система управления базами данных (СУБД) строится на основе некоторой явной или неявной модели данных. Все СУБД, построенные на одной и той же модели данных, относят к одному типу. Например, основой реляционных СУБД является реляционная модель данных, сетевых СУБД – сетевая модель данных, иерархических СУБД – иерархическая модель данных и так далее.

Microsoft SQL Server
Microsoft SQL Server – система управления реляционными базами данных (СУБД), разработанная корпорацией Microsoft. Основной используемый язык запросов – Transact-SQL
Microsoft SQL Server 2005 является полноценной платформой интеллектуальной обработки данных, предоставляющей возможности, инструменты и функциональность для создания и классических, и инновационных аналитических приложений. SQL Server 2005 предоставляет набор инструментов, которые снижают сложность создания, развертывания, управления и использования приложений обработки и анализа данных предприятия на целом ряде платформ, от мобильных устройств до систем хранения данных масштаба предприятия. Благодаря исчерпывающему набору функций, взаимодействию с существующими системами и автоматизации типовых задач, SQL Server 2005 предоставляет полное решение в области хранения данных для предприятий различных масштабов.
Microsoft SQL Server 2005 представляет собой платформу обработки данных, построенную вокруг ядра, обеспечивающего функциональность реляционной базы данных, а также большого набора сервисов, расширяющих эту функциональность.
Ядро реляционной базы данных обеспечивает безопасные, надежные, масштабируемые, высокодоступные операции над реляционными данными и позволяет работать как со структурированными, так и с неструктурированными XML-данными. Ядро базы данных обеспечивает поддержку .NET CLR (возможность создания хранимых процедур, функций и триггеров, реализованных на управляемом коде, а также определяемых пользователем типов и агрегатных функций) и расширений ADO.
Реляционное ядро БД хранит подробные записи о транзакциях, генерируемых системами оперативной обработки транзакций, а также осуществляет оперативную аналитическую обработку данных по запросу специализированных хранилищ данных. Реляционное ядро БД обеспечивает достоверность и защиту хранимых данных, отказоустойчивость, динамически оптимизирует производительность, а также налагает блокировки для реализации параллелизма.
Ядро реляционной базы данных SQL Server 2005 включает несколько интересных возможностей для создания и поддержки различных приложений с хранилищами данных:
· табличные секции, обеспечивающие быструю загрузку данных и упрощенную поддержку очень больших таблиц
· простое создание сервера отчетности
· улучшения в Transact-SQL, включая новые типы данных и новые аналитические функции
· выполнение онлайновых операций над индексами
· гранулированные операции резервного копирования/восстановления
· быстрая инициализация файлов
Для хранения XML данных в SQL Server 2005 был реализован новый внутренний тип данных. SQL Server 2000 позволяет хранить XML на сервере в виде текста в поле BLOB (Binary Large Objects – бинарные большие объекты), поэтому нет возможности работать с XML или ссылаться на XML на сервере. Для того чтобы работать с данными XML, его нужно было извлечь его на уровень приложения, затем воспользоваться стандартным анализатором XML или Document Object Model (DOM) – программным объектом для обработки документов XML. Microsoft SQL Server 2005 предоставляет принципиально новый подход к использованию XML. Введен новый одноименный тип данных – XML. В этом типе используются методы query(), exist(), value(), nodes() и modify(), которые представляют собой подмножество спецификации XML Query (XQuery). XML-документ перестал быть чем-то неделимым. Благодаря новому типу данных механизм SQL Server понимает данные XML точно так же, как он понимает целые числа или строковые данные. Тип данных XML позволяет создавать как таблицы, которые хранят только XML, так и таблицы, которые хранят и XML, и реляционные данные. Эта гибкость позволяет получить максимальную отдачу от реляционной модели для структурированных данных и пополнить эти данные слабоструктурированными данными XML.
Чтобы извлечь максимальную пользу из этой комбинации слабоструктурированных и реляционных данных, внутренний тип данных SQL Server 2005 XML поддерживает несколько встроенных методов, позволяющих запрашивать и модифицировать данные XML. Эти методы воспринимают XQuery, новый стандартный язык консорциума World Wide Web Consortium (W3C), а также навигационный язык XPath 2.0 и язык модификации данных XML. Язык запросов XML, или XQuery, является развитым и гибким языком запросов над всеми типами данных XML. Он разрабатывался именно как язык запросов для иерархической среды XML и обеспечивает оптимальный поиск в такой среде. В языке манипуляции XML DML SQL Server 2005 XQuery расширен возможностями внесения изменения в данные. При этом учитываются все особенности XML, в частности, возможность использования схемы документа. Имеется возможность комбинировать запросы к методам типа данных XML со стандартным T-SQL, создавая запросы, которые возвращают и реляционные данные, и данные XML.
Для поддержки типа данных XML были добавлены ключевые слова для регистрации и управления схемами XML. Центральные инструменты для работы с XML, FOR XML и OPENXML расширены поддержкой типа данных XML, что позволяет делать запросы к части XML-документа и проверять, что документ соответствует схеме XML. Для большей структурированности или целостности XML-данных SQL Server позволяет связывать схему с конкретным столбцом XML. Если некоторая схема XML связана с некоторым столбцом XML, схема проверяет, правильно ли данные XML вставлены в поле. Но SQL Server 2005 поддерживает несколько схем, сгруппированных в коллекцию, что позволяет применять к столбцу XML разные схемы. Сервер будет проверять правильность всех входящих данных XML по всем схемам. Если XML верен с точки зрения любой из схем коллекции, он может быть сохранен в поле XML.
Для улучшения производительности при наличии XML SQL Server 2005 позволяет создавать индексы по данным XML. Эти индексы работают так же, как стандартные индексы SQL Server и могут существенно увеличить производительность системы во время работы с XML-данными.
Внутренний тип данных XML в SQL Server 2005 позволяет создавать более качественные модели данных, имеющих структуру естественного происхождения. В реальной жизни никакой определенности нет; но сегодня, благодаря комбинированию XML и реляционных данных, мы имеем возможность учесть эту неизбежную неопределенность, что позволит системам более чутко реагировать на изменения и продлит их жизненный цикл. Теперь с содержимым XML-документа можно работать непосредственно, обращаясь к нему по правилам работы с XML-документом, выполнять поиск информации по правилам XQuery и, при этом, пользоваться всей мощью системы индексации SQL Server.

Tamino XML Server
Альтернативный подход в хранении XML данных заключается в том, чтобы создать СУБД, изначально ориентированную на хранение и поиск данных в формате XML, поскольку полная поддержка XML требует применения иных методик, которые выходят за рамки традиционных реализаций баз данных. Такие хранилища называются native XML базами данных.
Термин native XML база данных используется в различных смыслах разными группами. Native XML база данных имеет следующий три характеристики:
· она определяет логическую модель для XML-документа. Данные хранятся и выбираются в соответствии с этой моделью. Модель должна включать в себя элементы, атрибуты и порядок документа;
· XML-документ является базовой единицей логического хранения;
· не требуется никакая специфическая физическая модель хранения. Это означает, что она может быть основана на реляционных, иерархических или объектно-ориентированной базе данных.
В частности, это определение допускает преобразование данных из модели данных XML в другие модели данных для их хранения и обработки. Таким образом, требуется, чтобы native XML база данных также имела следующие два свойства:
· модель данных XML – фундаментальная логическая модель данных, которая и используется внутри базы данных и предоставляется пользователям базы данных, если XML является типом данных;
· модель данных XML является основной единицей физического хранения всех XML-данных, без отображения в другую модель данных.
Это краткое определение означает, что XML – уже не просто расширенный тип данных, это то, как данные обрабатываются, как логически, так и физически. Данные, представленные в XML, соответствуют физической схеме хранения на диске. Эта модель является лучшей для эффективного поиска XML-данных.
Именно такой подход применила компания Software AG в своем продукте Tamino XML Server, реализующем модель хранения и обработки данных в соответствии со стандартами XML:
· XML-документ является, как правило, фундаментальной единицей хранения;
· DTD (Document Type Definition) или XML-схемы используются как «язык определения данных» для описания свойств коллекций документов;
· языки запросов XML (например, XPath) используются для поиска документов;
· клиентские приложения могут обрабатывать XML-данные с помощью SAX, DOM, XSTL и других стандартов на самом ядре сервера, а не посредством внешних утилит.
С практической точки зрения обе стратегии – реляционные СУБД с поддержкой XML и XML-ориентированные СУБД имеют свою нишу. Первый вариант принято применять для доступа к существующим системам обработки данных, а второй - для обработки документов, изначально создаваемых в XML-формате. Однако, учитывая современные тенденции развития информационных систем, можно утверждать, что специализированные XML-серверы оптимальным образом подходят для решения задач интеграции гетерогенных приложений, выступая в роли виртуальных СУБД и управляя данными в формате XML, хранимыми в различных источниках информации.
Tamino XML Server – это продукт, предназначенный для хранения, обслуживания, публикации и обмена документами в формате XML.
Общая схема архитектуры Tamino представлена на рис 1. Физически сервер состоит из набора сервисов, в котором выделяется два уровня - базовый (ядро) и вспомогательный. Сервисы ядра - это неотъемлемая часть Tamino, они доступны сразу после установки продукта. Вспомогательные сервисы включают средства и инструменты для эффективной разработки решений на базе Tamino. Их состав может расширяться за счет продуктов независимых разработчиков.

Рис. 1. Схема работы программной системы с использованием Tamino.
Tamino предназначена для поддержки XML-документов, то есть для хранения XML-данных и извлечения их в наборах, а также реализации обширных возможностей выполнения запросов и полной поддержки транзакций.
Подразумевается, что в Tamino документы хранятся целиком. Чтобы предоставить доступ к имеющимся источникам данных и объединить данные, поступающие из различных источников (в том числе и из Tamino) в один XML-документ, Tamino поддерживает доступ к внешним источникам через компонент X-Node.
Для обработки или выборки частей XML-документов может применяться любой предоставленный пользователем код. Компонент X-Tension позволяет определять расширения для сервера Tamino. Серверные расширения могут передавать XML-документы или части этих документов в функции, предоставленные пользователем, или считывать данные из этих функций для добавления их в XML-документ.
Доступ к Tamino осуществляется посредством протокола HTTP. Документы и команды передаются на сервер Tamino через расширение Web-сервера, называемое X-Port. Ядро XML принимает эти команды и анализирует их с учетом метаданных, находящихся в специальном хранилище Tamino, который называют картой данных.

Часть 2: Реализация механизмов поддержки и порождения ссылок уровня хранения на базе системы хранения XML данных XSS

1. Сетевая модель данных

Сетевая модель данных — логическая модель данных, описывающая структурный аспект, аспект целостности и аспект обработки данных в сетевых базах данных.
Аспект структуры
Как и иерархическая, сетевая модель данных базируется на графовой форме построения данных, и на концептуальном уровне она является наследником иерархической модели данных. Разница между иерархической моделью данных и сетевой состоит в том, что в иерархических структурах запись-потомок должна иметь в точности одного предка, а в сетевой структуре данных у потомка может иметься любое число предков.
К основным понятиям сетевой модели базы данных относятся: уровень, элемент (узел), связь. Узел – это совокупность атрибутов данных, описывающих некоторый объект. На схеме иерархического дерева узлы представляются вершинами графа. В сетевой структуре каждый элемент может быть связан с любым другим элементом.
Сетевая БД состоит из набора экземпляров определенного типа записи и набора экземпляров определенного типа связей между этими записями. Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка.
Аспект манипуляции
Операции над данными:
· ДОБАВИТЬ - внести запись в БД и, в зависимости от режима включения, либо включить ее в групповое отношение, где она объявлена подчиненной, либо не включать ни в какое групповое отношение.
· ВКЛЮЧИТЬ В ГРУППОВОЕ ОТНОШЕНИЕ - связать существующую подчиненную запись с записью-владельцем.
· ПЕРЕКЛЮЧИТЬ - связать существующую подчиненную запись с другой записью-владельцем в том же групповом отношении.
· ОБНОВИТЬ - изменить значение элементов предварительно извлеченной записи.
· ИЗВЛЕЧЬ - извлечь записи последовательно по значению ключа, а также используя групповые отношения - от владельца можно перейти к записям - членам, а от подчиненной записи к владельцу набора.
· УДАЛИТЬ - убрать из БД запись. Если эта запись является владельцем группового отношения, то анализируется класс членства подчиненных записей. Обязательные члены должны быть предварительно исключены из группового отношения, фиксированные удалены вместе с владельцем, необязательные останутся в БД.
· ИСКЛЮЧИТЬ ИЗ ГРУППОВОГО ОТНОШЕНИЯ - разорвать связь между записью-владельцем и записью-членом.
Примерный набор операций манипулирования данными:
· найти конкретную запись в наборе однотипных записей;
· перейти от предка к первому потомку по некоторой связи;
· перейти к следующему потомку в некоторой связи;
· перейти от потомка к предку по некоторой связи;
· создать новую запись;
· уничтожить запись;
· модифицировать запись;
· включить в связь;
· исключить из связи;
· переставить в другую связь и так далее.
Аспект целостности
В сетевой модели данных имеется необязательная возможность потребовать для конкретного типа связи отсутствие потомков, не участвующих ни в одном экземпляре этого типа связи (как в иерархической модели). Таким образом, при удалении записи-родителя все дочерние записи либо будут удалены, либо должны быть присоединены к другому родителю, либо могут остаться в базе без указания родителя.
Достоинства сетевой модели данных:

• достоинством сетевой модели данных является возможность эффективной реализации по показателям затрат памяти и оперативности (например, задача коммивояжера), а также возможность переиспользования данных.

Недостатки сетевой модели данных:

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

2. Объектно-ориентированная модель данных

Строго говоря, общепринятого определения "объектно-ориентированной модели данных" не существует. Можно говорить лишь о неком "объектном" подходе к логическому представлению данных и о различных объектно-ориентированных способах его реализации.
Любая модель данных должна включать три аспекта: структурный, манипуляционный и целостный. Посмотрим, как они реализуются на основе объектно-ориентированной парадигмы программирования.
Структура объектной модели описываются с помощью трех ключевых понятий:
· инкапсуляция - каждый объект обладает некоторым внутренним состоянием (хранит внутри себя запись данных), а также набором методов – процедур, с помощью которых (и только таким образом) можно получить доступ к данным, определяющим внутреннее состояние объекта, или изменить их. Таким образом, объекты можно рассматривать как самостоятельные сущности, отделенные от внешнего мира.
· наследование – подразумевает возможность создавать из классов объектов новые классы объекты, которые наследуют структуру и методы своих предков, добавляя к ним черты, отражающие их собственную индивидуальность. Наследование может быть простым (один предок) и множественным (несколько предков).
· полиморфизм – различные объекты могут по-разному реагировать на одинаковые внешние события в зависимости от того, как реализованы их методы.
Аспект манипуляции
К сожалению, в объектно-ориентированном программировании отсутствуют общие средства манипулирования данными, такие как реляционная алгебра или реляционное исчисление. Работа с данными ведется с помощью одного из объектно-ориентированных языков программирования общего назначения, например, C++, Java или C#, с помощью которых можно реализовать четверку операций создания, чтения, обновления и удаления.
Аспект целостности
Для поддержания целостности объектно-ориентированный подход предлагает использовать следующие средства:
· автоматическое поддержание отношений наследования;
· возможность объявить некоторые поля данных и методы объекта как "скрытые", не видимые для других объектов; такие поля и методы используются только методами самого объекта;
· создание процедур контроля целостности внутри объекта.
В объектно-ориентированных базах данных, в отличие от реляционных, хранятся не записи, а объекты. Объектно-ориентированный подход представляет более совершенные средства для отображения реального мира, чем реляционная модель:
· естественное представление данных. В реляционной модели все отношения принадлежат одному уровню, именно это осложняет преобразование иерархических связей модели "сущность-связь" в реляционную модель. Объектно-ориентированную модель можно рассматривать послойно, на разных уровнях абстракции.
· имеется возможность определения новых типов данных и операций с ними.
Характеристики:
· поддержка сложных объектов. В системе должна быть предусмотрена возможность создания составных объектов за счет применения конструкторов составных объектов;
· поддержка индивидуальности объектов. Все объекты должны иметь уникальный идентификатор, который не зависит от значений их атрибутов;
· поддержка инкапсуляции. Корректная инкапсуляция достигается за счет того, что программисты обладают правом доступа только к спецификации интерфейса методов, а данные и реализация методов скрыты внутри объектов;
· поддержка наследования типов. Подтип должен наследовать атрибуты и методы от его супертипа;
· вычислительная полнота. Язык манипулирования данными должен быть языком программирования общего назначения;
· набор типов данных должен быть расширяемым. Пользователь должен иметь средства создания новых типов данных на основе набора предопределенных системных типов. Более того, между способами использования системных и пользовательских типов данных не должно быть никаких различий.
К достоинствам объектно-ориентированной модели обычно относят:
· возможность для пользователя системы определять свои сколь угодно сложные типы данных (используя имеющийся синтаксис и свойства наследуемости и инкапсуляции);
· наличие наследуемости свойств объектов;
· повторное использование программного описания типов объектов при обращении к другим типам, на них ссылающимся.
К недостаткам объектно-ориентированной модели можно отнести:
· отсутствие строгих определений; разное понимание терминов и различия в терминологии;
· как следствие – эта модель не исследована столь тщательно математически, как реляционная, иерархическая и сетевая;
· отсутствие общеупотребительных стандартов, позволяющих связывать конкретные объектно-ориентированные системы с другими системами работы с данными.

3. Выбор модели данных

Выше были рассмотрены различные модели данных применительно к задаче хранения слабоструктурированных данных и представлены оценки эффективности их использования. Кроме статических особенностей слабоструктурированных данных необходимо также учитывать динамическую составляющую изменения самих структур данных во времени, определенную в п. 1.1. В этой точки зрения важна легкость изменения структуры в хранилище данных. Поддержка этой функциональности в хранилище является большим плюсом, расширяя области применимости аппарата в целом.
· Реляционная модель данных
Чтобы разложить в реляционной модели ссылочные данные, потребуются усилия для создания многих таблиц и связей между ними. А для получения данных из этих таблиц потребуется написание сложных запросов с объединением таблиц (JOIN), что может сильно сказываться на быстродействии. Также при изменении структуры объектов требуется изменение структуры базы данных, что является сложной задачей ввиду отсутствия удобных средств определения структур и перестроения данных в случае их изменения.
· Иерархическая модель данных
Оптимальна для естественного отображения сложных иерархических данных. Есть возможность рассматривать записи «послойно», с учетом абстракции.
· Сетевая модель данных
По сравнению с иерархической моделью обладает расширенными возможностями за счет введения дополнительных связей между записями, в том числе у узла появляется возможность иметь нескольких родителей.
· Объектная модель данных
Является «абстракцией» одной из вышеуказанных моделей, но для работы предоставляет сразу объекты.
Реляционная модель имеет существенные ограничения по отображению данных из объектов. Иерархическая модель органично подходит для отображения объектных данных. Хранилище, построенное на основе сетевой модели, обладает сложной и жесткой структурой, плюс функциональность сетевой модели является избыточной для данной задачи. Таким образом, останавливаемся на выборе иерархической модели данных. Как будет показано дальше, фактически будет использоваться модифицированная иерархическая модель с возможностями сетевой модели данных. Для хранения слабоструктурированных данных оптимальным является применение иерархической модели, расширенной механизмом ссылок – элементом сетевой модели (см. п. 1.3). Поддержка изменяемости структур во времени на уровне хранения также является большим плюсом.

Часть 1: Реализация механизмов поддержки и порождения ссылок уровня хранения на базе системы хранения XML данных XSS

1. Слабоструктурированные данные

В современных программных системах используются различные аппараты для обработки и хранения данных. Модели данных и средства хранения, основанные на них, выбираются исходя из специфики самих данных. Основные модели данных на сегодняшний день – реляционная, иерархическая и сетевая. При выборе оптимальной модели и средства хранения для конкретной задачи нужно опираться на особенности области данных и характеристики алгоритмов разработки, соотнося их с возможностями аппарата.
Модель данных – теория представления и обработки данных в системе управления данными (хранилище данных), включающая три аспекта:
· аспект структуры: методы описания типов и логических структур данных в базе данных;
· аспект манипуляции: методы манипулирования данными;
· аспект целостности: методы описания и поддержки целостности базы данных.
Аспект структуры определяет, что из себя логически представляет хранилище данных, аспект целостности определяет средства описаний корректных состояний хранилища данных, аспект манипуляции определяет способы перехода между состояниями хранилища данных (т.е. способы модификации данных) и способы извлечения данных из хранилища.
В математике принято называть типами (или, иначе, сортами) относительно устойчивые и независимые совокупности элементов, которые можно выделить во всем рассматриваемом множестве (предметной области). При этом разделение элементов предметной области на типы или сорта во многом является условным и носит субъективный характер, так как зависит от эксперта в этой области.
Тип, подобно множеству, может определяться двояко. Во-первых, возможно определение типа посредством явного перечисления всех элементов, принадлежащих типу (такой подход применяется и в математике, и в программировании, где существуют так называемые перечислимые типы). Другим способом определения типа T является формализация общих свойств тех элементов d из предметной области D, которые объединяются в этот тип, посредством задания индивидуализирующей предикатной функции Ψ, значение которой истинно, если элемент принадлежит данному типу и ложно в противном случае:
T = {d: D|Ψ}
Слабоструктурированными называются данные, обладающие определенной структурой, но эта структура может оказаться непостоянной, недостаточно изученной или неполной. Как правило, такие данные не могут быть описаны с помощью какой-либо неизменной схемы, поэтому иногда их называют не имеющими схемы или описывающими сами себя. Характерной особенностью слабоструктурированных данных является то, что описательная информация, которая обычно выделяется в отдельную схему, присутствует в самих данных. В некоторых формах представления слабоструктурированных данных не предусмотрено применение отдельной схемы, а в других она существует, но налагает на представленные в ней данные очень слабые ограничения.
Можно выделить следующие ключевые положения, характеризующие особенности слабоструктурированных данных:
· Не существует фиксированной структуры данных
· Нет четкого различия между собственно данными и их структурой
· Отсутствует строгая типизация
· Изменение структуры данных является рутинной операцией, сравнимой с внесением изменений в данные
· Объем данных сравним с количеством типов в структуре данных
· Структура данных является описывающей, а не предписывающей, и может быть получена из самих данных
· Полное знание структуры данных не является необходимым для построения запросов, возможны запросы, полностью игнорирующие структуру данных
С точки зрения типизации это означает, что количество элементов d:D сравнимо с количеством T, причем в процессе изменения данных могут изменяться как значения, так и структура, то есть T становится функцией времени T(t), как и d(t):
T(t) = {d(t): D|Ψ},
где число уникальных T(t) эквивалентно числу уникальных d(t).
В последнее время обнаруживается значительный интерес к слабоструктурированным данным по многим причинам. Наиболее важные из них перечислены ниже:
· Для дальнейшей автоматизации обработки информации необходимо иметь возможность обращаться к различным источникам данных, как к базам данных, но на эти источники невозможно наложить какую-либо заранее заданную схему.
· Количество разнотипных баз данных постоянно возрастает, поэтому задача создания гибкого формата, обеспечивающего обмен данными между базами различных типов, становится все более важной.
· В связи со становлением языка XML как стандарта представления и обмена данными между приложениями появились перспективы создания новых методов обработки слабоструктурированных данных, поскольку язык XML хорошо подходит для их описания.
Далее рассмотрим модели данных с точки зрения их применимости для работы со слабоструктурированных данными.

2 Модели хранения данных

2.1 Реляционная модель данных

Реляционная модель данных (РМД) – модель данных, основывающаяся на отношениях (relation) и описывающая три аспекта применительно к реляционным базам данных.
· Структурный аспект – данные в базе данных представляют собой набор отношений.
· Аспект целостности – отношения (таблицы) отвечают определенным условиям целостности. РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня отношения и уровня базы данных.
· Аспект манипулирования (обработки) – РМД поддерживает операторы манипулирования отношениями (реляционная алгебра).
Для лучшего понимания РМД следует отметить три важных обстоятельства:
· модель является логической, то есть отношения являются логическими, а не физическими (хранимыми) структурами;
· всё информационное наполнение базы данных представлено одним и только одним способом, а именно – явным заданием значений атрибутов в кортежах отношений; в частности, нет никаких указателей (адресов), связывающих одно значение с другим;
· наличие реляционной алгебры позволяет реализовать декларативное программирование и декларативное описаний ограничений целостности, в дополнение к навигационному (процедурному) программированию и процедурной проверке условий.
РМД характеризуется простотой структуры данных, удобным для пользователя табличным представлением и возможностью использования формального аппарата алгебры отношений и реляционного исчисления для обработки данных.
Реляционная модель ориентирована на организацию данных в виде таблиц. Каждая реляционная таблица представляет собой двумерный массив строк и столбцов и обладает следующими свойствами:
· каждая строка таблицы – один элемент данных (кортеж)
· все ячейки в столбце таблицы однородные, то есть все элементы в столбце имеют одинаковый тип (числовой, символьный и т. д.)
· каждый столбец имеет уникальное имя
· одинаковые строки в таблице отсутствуют
· порядок следования строк и столбцов может быть произвольным
Недостатки реляционной модели с точки зрения применимости аппарата для хранения слабоструктурированных данных:
· Реляционная модель данных не допускает естественного представления данных со сложной иерархической структурой, поскольку в ее рамках возможно моделирование лишь с помощью плоских отношений (таблиц). Все отношения принадлежат одному уровню, многие значимые связи между данными либо теряются, либо их поддержку приходится осуществлять в рамках конкретной прикладной программы в области данных со своей реализацией задач хранения.
· По определению в реляционной модели поля кортежа могут содержать лишь атомарные значения. Однако, во многих приложениях, таких как системы автоматизированного проектирования, геоинформационные системы, пользователи оперируют со сложноструктурированными объектами. Например, необходимо создать базу данных земельных участков. Каждый участок задается координатами узлов ломаной линии, ограничивающей его по периметру. В этом случае весьма затруднительно спроектировать реляционную таблицу, так как заранее неизвестно количество узлов для всех участков. Также трудность представляет написание общих процедур (вычисление площади, нахождение пересечения и так далее) для всех случаев. Кроме того, даже в том случае, когда сложный объект удается "уложить" в реляционную базу данных, его данные распределяются, как правило, по многим таблицам. Соответственно, извлечение каждого такого объекта требует выполнения многих операций соединения (JOIN), что значительно замедляет работу СУБД. Обойти это и предыдущее ограничения можно было бы в том случае, если бы реляционная модель допускала:
o возможность определения новых неатомарных типов данных
o определение наборов операций, связанных с данными определенного неатомарного типа
o ссылки

2.2 Иерархическая модель данных

Иерархическая модель данных (ИМД) – модель представления данных в виде древовидной структуры.

Рис. 1. Пример иерархической структуры.
ИМД представляет собой совокупность элементов, расположенных в порядке их подчинения от общего к частному и образующих перевернутое дерево (граф). Данная модель характеризуется такими параметрами, как уровни, узлы, связи. Узел – информационная модель элемента, представляющего собой объект и находящегося на данном уровне иерархии. Между объектами в ИМД существуют связи, каждый объект может включать в себя несколько объектов более низкого уровня. Такие объекты находятся в отношении предка (объект более близкий к корню) к потомку (объект более низкого уровня), при этом возможно, когда объект-предок не имеет потомков или имеет их несколько, тогда как у объекта-потомка обязательно только один предок. Объекты, имеющие общего предка, называются близнецами.
Организация данных в СУБД иерархического типа определяется в терминах: элемент, агрегат, запись (группа), групповое отношение, база данных.
· Атрибут (элемент данных) – наименьшая единица структуры данных. Обычно каждому элементу при описании базы данных присваивается уникальное имя. По этому имени к нему обращаются при обработке. Элемент данных также часто называют полем.
· Запись - именованная совокупность атрибутов. Использование записей позволяет за одно обращение к базе получить некоторую логически связанную совокупность данных. Именно записи изменяются, добавляются и удаляются. Тип записи определяется составом ее атрибутов. Экземпляр записи – конкретная запись с конкретным значением элементов
· Групповое отношение – иерархическое отношение между записями двух типов. Родительская запись (владелец группового отношения) называется исходной записью, а дочерние записи (члены группового отношения) – подчиненными. Иерархическая база данных может хранить только такие древовидные структуры.
В иерархической модели данных вершине графа соответствует тип записи или просто запись, а дугам – типы связей предок-потомок. В иерархических структурах запись-потомок должен иметь в точности одного предка. Иерархическая модель представляет собой связный неориентированный граф древовидной структуры, объединяющий записи. Иерархическая база данных состоит из упорядоченного набора деревьев.
Корневая запись каждого дерева обязательно должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальное значение только в рамках группового отношения. Каждая запись идентифицируется полным сцепленным ключом, под которым понимается совокупность ключей всех записей от корневой вниз по иерархическому пути.
Преобразование концептуальной модели в иерархическую структуру данных во многом схоже с преобразованием ее в сетевую модель (см. п. 1.4), но и имеет некоторые отличия в связи с тем, что иерархическая модель требует организации всех данных в виде дерева. Преобразование связи типа "один ко многим" между предком и потомком осуществляется практически автоматически в том случае, если потомок имеет одного предка, и происходит это следующим образом. Каждый объект с его атрибутами, участвующий в такой связи, становится логическим сегментом. Между двумя логическими сегментами устанавливается связь типа "один ко многим". Сегмент со стороны "много" становится потомком, а сегмент со стороны "один" становится предком. Ситуация значительно усложняется, если потомок в связи имеет не одного, а двух и более предков. Так как подобное положение является невозможным для иерархической модели, то отражаемая структура данных нуждается в преобразованиях, которые сводятся к замене одного дерева, например, двумя (если имеется два предка). В результате такого преобразования в базе данных появляется избыточность, так как единственно возможный выход из этой ситуации – дублирование данных.
Например, если иерархическая база данных содержала информацию о покупателях и их заказах, то будет существовать объект «покупатель» (родитель) и объект «заказ» (дочерний). Объект «покупатель» будет иметь указатели от каждого заказчика к физическому расположению заказов покупателя в объект «заказ». В этой модели запрос, направленный вниз по иерархии, прост (например: какие заказы принадлежат этому покупателю); однако запрос, направленный вверх по иерархии, более сложен (например, какой покупатель поместил этот заказ).
Операции над данными, определенные в иерархической модели:
· ДОБАВИТЬ в базу данных новую запись. Для корневой записи обязательно формирование значения ключа.
· ИЗМЕНИТЬ значение данных предварительно извлеченной записи. Ключевые данные не должны подвергаться изменениям.
· УДАЛИТЬ некоторую запись и все подчиненные ей записи.
· ИЗВЛЕЧЬ:

• извлечь корневую запись по ключевому значению, допускается также последовательный просмотр корневых записей
  
• извлечь следующую запись (следующая запись извлекается в порядке обхода дерева, определенном в хранилище)

Как видим, все операции изменения применяются только к одной "текущей" записи (которая предварительно извлечена из базы данных). Такой подход к манипулированию данных получил название "навигационного".
Примеры типичных операторов поиска данных:
· найти указанное дерево БД;
· перейти от одного дерева к другому;
· найти экземпляр сегмента, удовлетворяющий условию поиска;
· перейти от одного сегмента к другому внутри дерева;
· перейти от одного сегмента к другому в порядке обхода иерархии.
Примеры типичных операторов поиска данных с возможностью модификации:
· найти и удержать для дальнейшей модификации единственный экземпляр сегмента, удовлетворяющий условию поиска;
· найти и удержать для дальнейшей модификации следующий экземпляр сегмента с теми же условиями поиска;
· найти и удержать для дальнейшей модификации следующий экземпляр для того же родителя.
Примеры типичных операторов модификации иерархически организованных данных, которые выполняются после выполнения одного из операторов второй группы (поиска данных с возможностью модификации):
· вставить новый экземпляр сегмента в указанную позицию;
· обновить текущий экземпляр сегмента;
· удалить текущий экземпляр сегмента.
В иерархической модели автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя. При удалении родительской записи автоматически удаляются все подчиненные (аспект целостности).
Достоинства иерархической модели данных:
· простота представления сложных строго иерархических данных.
Недостатки иерархической модели данных:
· проблемы с преобразованием данных, не имеющих древовидной структуры: часто приходится вводить дублирующие связи, возникает проблема избыточности данных;
· отсутствие переиспользования данных за счет жесткого ограничения на структуру дерева.

Разработка клиент-серверного приложения на основе сокетов.

 
Игра “Крестики-нолики”-это логическая игра,целью которой является расставить 5 крестиков или 5 ноликов в один ряд по горизонтали,по вертикали или по горизонтали.Кто расставил,тот и выйграл.Игра происходит между двумя игроками по локальной сети.При загружении игры один из игроков ставит галочку в меню communication->server,другой же в меню communication->client,вписывает IP адресс сервера и нажимает connect.Далее оба игрока выбирают новую игру(Game->New) и наслаждаются игрой.
Screenshot:

Постановка задачи.

Разработать клиент-серверное приложение, в данном случае игру “Крестики-нолики”, состоящий из клиента и сервера, позволяющего посылать и принимать информацию.
Немного теории.
Применяемая в IP-сетях архитектура клиент-сервер использует IP-пакеты для коммуникации между клиентом и сервером. Клиент отправляет запрос серверу, на который тот отвечает. В случае с TCP/IP между клиентом и сервером устанавливается соединение (обычно с двусторонней передачей данных), а в случае с UDP/IP - клиент и сервер обмениваются пакетами (дейтаграммамми) с негарантированной доставкой.
Каждый сетевой интерфейс IP-сети имеет уникальный в этой сети адрес (IP-адрес). Упрощенно можно считать, что каждый компьютер в сети Интернет имеет собственный IP-адрес. При этом в рамках одного сетевого интерфейса может быть несколько сетевых портов. Для установления сетевого соединения приложение клиента должно выбрать свободный порт и установить соединение с серверным приложением, которое слушает (listen) порт с определенным номером на удаленном сетевом интерфейсе. Пара IP-адрес и порт характеризуют сокет (гнездо) - начальную (конечную) точку сетевой коммуникации. Для создания соединения TCP/IP необходимо два сокета: один на локальной машине, а другой - на удаленной. Таким образом, каждое сетевое соединение имеет IP-адрес и порт на локальной машине, а также IP-адрес и порт на удаленной машине.
Модуль socket обеспечивает возможность работать с сокетами из Python. Сокеты используют транспортный уровень согласно семиуровневой модели OSI (Open Systems Interconnection, взаимодействие открытых систем), то есть относятся к более низкому уровню, чем большинство протоколов.
Уровни модели OSI:
Физический
Поток битов, передаваемых по физической линии. Определяет параметры физической линии.
Канальный (Ethernet, PPP, ATM и т.п.)
Кодирует и декодирует данные в виде потока битов, справляясь с ошибками, возникающими на физическом уровне в пределах физически единой сети.
Сетевой (IP)
Маршрутизирует информационные пакеты от узла к узлу.
Транспортный (TCP, UDP и т.п.)
Обеспечивает прозрачную передачу данных между двумя точками соединения.
Сеансовый
Управляет сеансом соединения между участниками сети. Начинает, координирует и завершает соединения.
Представления
Обеспечивает независимость данных от формы их представления путем преобразования форматов. На этом уровне может выполняться прозрачное (с точки зрения вышележащего уровня) шифрование и дешифрование данных.
Приложений (HTTP, FTP, SMTP, NNTP, POP3, IMAP и т.д.)
Поддерживает конкретные сетевые приложения. Протокол зависит от типа сервиса.
Каждый сокет относится к одному из коммуникационных доменов. Модуль socket поддерживает домены UNIX и Internet. Каждый домен подразумевает свое семейство протоколов и адресацию. Данное изложение будет затрагивать только домен Internet, а именно протоколы TCP/IP и UDP/IP, поэтому для указания коммуникационного домена при создании сокета будет указываться константа socket.AF_INET.
В качестве примера следует рассмотреть простейшую клиент-серверную пару. Сервер будет принимать данные о ходе клиента, и отвечать ему.
Реализация программы.

1 Структура программы.
Для начала определим класс сообщений (XO). В этом классе описаны почти все переменные и функции, с помощью которых реализуются выполнение программы. Это самый основной класс. Здесь идет работа с сокетами, обмен информацией между клиентом и сервером, анализ игры.

class XO : public CFrameWnd { public: void Send(char buf[bufsize]); bool Check(int i1,int i2,int i3,int i4,int i5); bool IsWon(); void CalcCellRect(); void DrawFrame(CPaintDC*); XO(); private: CString sAddr; CMenu menu; CPen pen; Cell cells[25]; mode cur_mod; bool bConnected; bool bGame; bool bServer; bool bClient; int num_cells; bool mymove; protected: protected: virtual BOOL PreCreateWindow(CREATESTRUCT& cs); protected: afx_msg void OnConnectClient(); afx_msg void OnPaint(); afx_msg void OnLButtonDown(UINT nFlags, CPoint point); afx_msg void OnGameNew(); afx_msg void OnGameExit(); afx_msg void OnClose(); afx_msg void OnConnectServer(); afx_msg void OnUpdateConnectClient(CCmdUI* pCmdUI); afx_msg void OnUpdateConnectServer(CCmdUI* pCmdUI); afx_msg void OnUpdateGameNew(CCmdUI* pCmdUI); afx_msg LRESULT OnAsync(WPARAM wparam, LPARAM lparam); DECLARE_MESSAGE_MAP() };

Ещё создана вспомогательная структура(struct Cell),которая содержит характеристики ячейки.

struct Cell { mode mod; bool active; CRect place; Cell() {active = false;} void SetCell(mode m) {mod = m; active = true;} };

Так же создан класс(CDialog),через который реализуется рисование окна и вычисление IP адреса.

class Dlg : public CDialog { public: CString addr; Dlg(CWnd* p=NULL) : CDialog(IDD_CONDIALOG,p){} protected: virtual void DoDataExchange(CDataExchange* pDX); };

И последним создан класс (MyApp)который реализуется рисование окна.

class MyApp : public CWinApp { public: virtual BOOL InitInstance() { AfxSocketInit(); m_pMainWnd = new XO; m_pMainWnd->ShowWindow(SW_SHOWNORMAL); return TRUE; } }; MyApp app;

2.Описание функций.
· Функция задаёт параметры окна.

BOOL XO::PreCreateWindow(CREATESTRUCT& cs) { cs.style &= ~WS_MAXIMIZEBOX; cs.style &= ~WS_THICKFRAME; cs.cx = 400; cs.cy = 400; return CFrameWnd::PreCreateWindow(cs); } LRESULT XO::OnAsync(WPARAM wParam,LPARAM lParam) { WSAEvent = WSAGETSELECTEVENT (lParam); switch (WSAEvent) { case FD_READ: if(bServer) recv(hSock2, buf, bufsize, 0); else recv(hSock, buf, bufsize, 0); if(buf[0]==33) { for(int i=0; i<25; i++) { cells[i].active=false; } cur_mod=X; bGame=true; mymove=false; num_cells=0; Invalidate(); return 0; } if(mymove==false) mymove=true; cells[buf[0]].active=true; cells[buf[0]].mod = buf[1]==1 ? X : O; cur_mod= cur_mod==X ? O : X; num_cells++; IsWon(); Invalidate(); return 0; case FD_ACCEPT: lenaddr=sizeof(myaddr); hSock2=accept(hSock,(LPSOCKADDR)&myaddr,&lenaddr); return 0; } return 1; }

· Функция, реализующая соединение с клиентом.

void XO::OnConnectClient() { bClient=true; WSAStartup(WS_VERSION_REQD, &stWSAData); hSock = socket (AF_INET, SOCK_STREAM, 0); Dlg dlg; dlg.DoModal(); sAddr = dlg.addr; myaddr.sin_family = AF_INET; myaddr.sin_addr.s_addr = inet_addr(sAddr); myaddr.sin_port = htons (2049); connect (hSock, (struct sockaddr *)&myaddr,sizeof(myaddr)); nRet=WSAAsyncSelect(hSock,m_hWnd,WM_ASYNC,FD_READ); bConnected=true; bServer=false; mymove=true; SetWindowText("xo - client"); }

· Функция,реализующая соединение с клиентом.

void XO::OnConnectServer() { bServer=true; WSAStartup(WS_VERSION_REQD, &stWSAData); hSock = socket (AF_INET,SOCK_STREAM,0); WSAAsyncSelect(hSock,m_hWnd,WM_ASYNC, FD_ACCEPT | FD_READ); myaddr.sin_family = AF_INET; myaddr.sin_addr.s_addr = htonl (INADDR_ANY); myaddr.sin_port = htons (2049); bind(hSock,(LPSOCKADDR)&myaddr, sizeof(struct sockaddr)); listen (hSock, 5); bConnected=true; bClient=false; mymove=false; SetWindowText("xo - server"); }

· Функция посылания информации.

void XO::Send(char buf[]) { if(bClient) send(hSock,buf,bufsize,0); else send(hSock2,buf,bufsize,0); } void XO::OnUpdateConnectClient(CCmdUI* pCmdUI) { pCmdUI->Enable(bClient); pCmdUI->SetCheck(int(bClient&&bConnected)); } void XO::OnUpdateConnectServer(CCmdUI* pCmdUI) { pCmdUI->Enable(bServer); pCmdUI->SetCheck(int(bServer&&bConnected)); } void XO::OnUpdateGameNew(CCmdUI* pCmdUI) { pCmdUI->Enable(bConnected); }

· Функция рисования.

void XO::OnPaint() { CPaintDC dc(this); dc.SelectObject(&pen); DrawFrame(&dc); for(int i=0; i<25; i++) { if(cells[i].active==true) { if(cells[i].mod==X) { dc.MoveTo(cells[i].place.left,cells[i].place.top); dc.LineTo(cells[i].place.right,cells[i].place.bottom); dc.MoveTo(cells[i].place.left,cells[i].place.bottom); dc.LineTo(cells[i].place.right,cells[i].place.top); } else if(cells[i].mod==O) { dc.Ellipse(cells[i].place); } } } } void XO::DrawFrame(CPaintDC* dc) { CRect r; GetClientRect(&r); dc->MoveTo(r.left,r.bottom/5); dc->LineTo(r.right,r.bottom/5); dc->MoveTo(r.left,2*r.bottom/5); dc->LineTo(r.right,2*r.bottom/5); dc->MoveTo(r.left,3*r.bottom/5); dc->LineTo(r.right,3*r.bottom/5); dc->MoveTo(r.left,4*r.bottom/5); dc->LineTo(r.right,4*r.bottom/5); dc->MoveTo(r.right/5,r.top); dc->LineTo(r.right/5,r.bottom); dc->MoveTo(2*r.right/5,r.top); dc->LineTo(2*r.right/5,r.bottom); dc->MoveTo(3*r.right/5,r.top); dc->LineTo(3*r.right/5,r.bottom); dc->MoveTo(4*r.right/5,r.top); dc->LineTo(4*r.right/5,r.bottom); } void XO::OnLButtonDown(UINT nFlags, CPoint point) { if(bGame==false || mymove==false) return; for(int i=0; i<25; i++) { if(cells[i].place.PtInRect(point) && !cells[i].active) { buf[0]=i; cells[i].active=true; cells[i].mod=cur_mod; mymove=false; num_cells++; InvalidateRect(cells[i].place); cur_mod= cur_mod== X ? O : X; buf[0]=i; buf[1]= cells[i].mod==X ? 1 : 0; Send(buf); break; } } IsWon(); } void XO::CalcCellRect() { CRect r; GetClientRect(&r); int cx = r.right; int cy = r.bottom; for(int j=0,t=r.top,b=r.top+cy/5; j<5; j++,t+=cy/5,b+=cy/5) { for(int i=0,l=r.left,p=r.left+cx/5; i<5; i++,p+=cx/5,l+=cx/5) { cells[j*5+i].place.left=l+5; cells[j*5+i].place.right=p-5; cells[j*5+i].place.top=t+5; cells[j*5+i].place.bottom=b-5; } } }

· Функция,определяющая победителя.
·

bool XO::IsWon() { bool won=false; won = Check(0,1,2,3,4)||Check(4,9,14,19,24) ||Check(20,21,22,23,24)||Check(0,5,10,15,20) ||Check(1,6,11,16,21)||Check(2,7,12,17,22) ||Check(5,6,7,8,9)||Check(3,8,13,18,23) ||Check(10,11,12,13,14)||Check(15,16,17,18,19) ||Check(0,6,12,18,24)||Check(4,8,12,16,20); if(!won && num_cells==25) { MessageBox("None won ...",""); won=true; } if(won) bGame=false; return won; }

· Функция создания новой игры.

void XO::OnGameNew() { if(bGame==true) return; for(int i=0; i<25; i++) { cells[i].active=false; } bGame=true; mymove=true; num_cells=0; cur_mod=X; buf[0]=33; Send(buf); Invalidate(); }

· Функция,определяющая выйграшные комбинации.

bool XO::Check(int i1,int i2,int i3,int i4,int i5) { bool won=false; mode m; if(!(cells[i1].active && cells[i2].active && cells[i3].active && cells[i4].active && cells[i5].active)) return won; if((m=cells[i1].mod) == cells[i2].mod && cells[i2].mod == cells[i3].mod && cells[i3].mod == cells[i4].mod && cells[i4].mod == cells[i5].mod) { won=true; } if(won==true) { char who= m==X ? 'X' : 'O'; CString message="Victory of "; message += who; MessageBox(message,"Congratulations!"); } return won; }

· Функция выхода.

void XO::OnGameExit() { OnClose(); }

· Функция закрытия.

void XO::OnClose() { nRet = WSACleanup(); CFrameWnd::OnClose(); }