архив
Нечеткое сравнение коллекций: семантический и алгоритмический аспекты
Семенов В.А., Морозов С.В., Тарлапан О.А., Энкович И.В.
Труды Института системного программирования РАН
Работа коллектива поддержана РФФИ (грант 07-01-00427).
11. Коллекции прямых и инверсных ассоциаций
Коллекции могут использоваться для реализации множественных ассоциативных связей между объектными типами. В языках объектно-ориентированного моделирования имеется возможность для каждой прямой ассоциации объявить соответствующую инверсную, которая представляется, как правило, неупорядоченным множеством или мультимножеством объектных ссылок и налагает дополнительные семантические ограничения (уникальности или мощности множественной ассоциации) на исходную модель.
Пусть 
и 
— объектные типы, 
— прямая множественная
ассоциация, 
— соответствующая ей
инверсная. Будем считать, что в качестве прямой ассоциации может быть
использована произвольная коллекция, в качестве инверсной — set или multiset. Поскольку
модификация прямой ассоциации подразумевает симметричную коррекцию инверсной,
операции установления и отмены ассоциативных отношений связаны логической
эквивалентностью следующим образом: 
, 
, 
, 
. Поэтому данные операции обязаны совместно участвовать в
итоговой транзакции.
Если инверсная ассоциация представляется множеством, то дополнительно устанавливается ограничение уникальности инверсного отношения. При сочетании в качестве прямой и инверсных ассоциаций различных коллекций более строгое ограничение уникальности в итоге распространится на обе ассоциативные связи. Таким образом, возможны следующие варианты сочетания прямых и инверсных коллекций: «set–set», «multiset–multiset», «list–multiset», «ordered set–set».
Нарушение ограничения уникальности прямой ассоциации автоматически приводит к аналогичному нарушению на стороне инверсной. Поэтому наличие инверсного ассоциативного отношения с уникальными элементами не вносит дополнительных корректив в способы представления и формирования дельты, а также в методы разрешения конфликтов, описанные в предыдущих разделах.
Более интересным с этой точки зрения представляются
ограничения мощности множественной ассоциации 
, 
, 
. В данном случае корректное представление дельты
предполагает выполнение следующих условий:
В силу отношений логической эквивалентности операций над прямыми и обратными ассоциациями, условия приобретают вид:
В случае конкурентных транзакций 
данные условия должны
выполняться также для консолидированной дельты 
.
Заключение
Таким образом, рассмотрены основные типы коллекций, поддерживаемые популярными языками объектно-ориентированного моделирования. Для них определены способы представления, журнализации, вычисления, принятия и согласования изменений. Для каждого выделенного типа дается строгая, семантически состоятельная интерпретация конфликтов и предлагается конструктивный метод их идентификации и разрешения. Результаты предполагается использовать при создании универсальной, основанной на модельном представлении среды коллективной инженерии с развитыми возможностями семантически корректной и функционально содержательной реконсиляции дивергентных реплик данных.
Литература
- Y. Saito, M. Shapiro. Optimistic Replication // In ACM Computing Surveys, Vol. 37, No. 1, March 2005, pp. 42–81.
- Better SCM Initiative: Version Control System Comparison
- Diffutils — GNU Project — Free Software Foundation (FSF)
- Z. Xing, E. Stroulia. UMLDiff: an algorithm for object-oriented design differences. // Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, Long Beach, CA, USA, 2005, pp. 54–65.
- Open Testware Reviews — Data Comparator Survey
- Comprehensive List of File and Folder Comparison and Synchronization Tools
- Сравнение файлов — Soft Софт каталог
- Google directory — Computers > Software > File Management > File Comparison
- Semenov V.A., Karaulov A.A. Semantic-Based Decomposition of Long-Lived Transactions in Advanced Collaborative Environments. // Proceedings of 6 European Conference on product and process modeling, ECPPM 2006, Spain, Valencia, September 11–15, 2006, pp.223–232.
- Семенов В.А., Ерошкин С.Г., Караулов А.А., Энкович И.В. Семантическая реконсиляция прикладных данных на основе моделей. // Труды Института системного программирования: т. 13, ч. 2. / Под ред. В.П. Иванникова — М.: ИСП РАН, 2007, с. 141–164.
- Semenov V.A. Collaborative Software Engineering Using Metamodel-Driven Approach. // Proceedings 16th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, WET ICE 2007, IEEE Computer Society Conference Publishing Services, 2007, pp. 178–179.
- Semenov V.A. Semantics-Based Reconciliation of Divergent Replicas in Advanced Concurrent Engineering Environments. // Complex Systems Concurrent Engineering: Collaboration, Technology Innovation and Sustainability, Springer-Verlag, 2007, pp. 557–564.
- ISO 10303: 1994, Industrial automation systems and integration — Product data representation and exchange.
- OMG. Model Driven Architecture: How systems will be built.
- T. Lindholm. XML three-way merge as a reconciliation engine for mobile data. // Proceedings of the 3d ACM international workshop on data engineering for wireless and mobile access, San Diego, CA, USA, 2003, pp. 93–97.
- J. Katajainen and J. L. Träff. A Meticulous Analysis of Mergesort Programs. // Lecture Notes In Computer Science, vol. 1203, 1997, pp. 217–228.
- Object Constraint Language Specification, Version 2.0
- ISO 10303-11: 2004, Industrial automation systems and integration — Product data representation and exchange — Part 11: Description methods: The EXPRESS language reference manual. Edition 2.
- Д. Кнут. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. — М.: Издательский дом «Вильямс», 2000.
- Д. Гасфилд. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — СПб.: Невский Диалект; БХВ-Петербург, 2003.
- G. Navarro. A Guided Tour to Approximate String Matching. // ACM Computing Surveys, vol. 33, no. 1, March 2001, pp. 31–88.