Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Обучение от Mail.Ru Group.
Онлайн-университет
для программистов с
гарантией трудоустройства.
Набор открыт!
2008 г.

Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

Семенов В.А., Морозов С.В., Тарлапан О.А., Энкович И.В.
Труды Института системного программирования РАН
Работа коллектива поддержана РФФИ (грант 07-01-00427).

Назад Содержание

11. Коллекции прямых и инверсных ассоциаций

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

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

Если инверсная ассоциация представляется множеством, то дополнительно устанавливается ограничение уникальности инверсного отношения. При сочетании в качестве прямой и инверсных ассоциаций различных коллекций более строгое ограничение уникальности в итоге распространится на обе ассоциативные связи. Таким образом, возможны следующие варианты сочетания прямых и инверсных коллекций: «set–set», «multiset–multiset», «list–multiset», «ordered set–set».

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

Более интересным с этой точки зрения представляются ограничения мощности множественной ассоциации , , . В данном случае корректное представление дельты предполагает выполнение следующих условий:

В силу отношений логической эквивалентности операций над прямыми и обратными ассоциациями, условия приобретают вид:

В случае конкурентных транзакций  данные условия должны выполняться также для консолидированной дельты .

Заключение

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

Литература

  1. Y. Saito, M. Shapiro. Optimistic Replication // In ACM Computing Surveys, Vol. 37, No. 1, March 2005, pp. 42–81.
  2. Better SCM Initiative: Version Control System Comparison
  3. Diffutils — GNU Project — Free Software Foundation (FSF)
  4. 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.
  5. Open Testware Reviews — Data Comparator Survey
  6. Comprehensive List of File and Folder Comparison and Synchronization Tools
  7. Сравнение файлов — Soft Софт каталог
  8. Google directory — Computers > Software > File Management > File Comparison
  9. 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.
  10. Семенов В.А., Ерошкин С.Г., Караулов А.А., Энкович И.В. Семантическая реконсиляция прикладных данных на основе моделей. // Труды Института системного программирования: т. 13, ч. 2. / Под ред. В.П. Иванникова — М.: ИСП РАН, 2007, с. 141–164.
  11. 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.
  12. 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.
  13. ISO 10303: 1994, Industrial automation systems and integration — Product data representation and exchange.
  14. OMG. Model Driven Architecture: How systems will be built.
  15. 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.
  16. J. Katajainen and J. L. Träff. A Meticulous Analysis of Mergesort Programs. // Lecture Notes In Computer Science, vol. 1203, 1997, pp. 217–228.
  17. Object Constraint Language Specification, Version 2.0
  18. 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.
  19. Д. Кнут. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. — М.: Издательский дом «Вильямс», 2000.
  20. Д. Гасфилд. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — СПб.: Невский Диалект; БХВ-Петербург, 2003.
  21. G. Navarro. A Guided Tour to Approximate String Matching. // ACM Computing Surveys, vol. 33, no. 1, March 2001, pp. 31–88.

Назад Содержание

Новости мира IT:

Архив новостей

Последние комментарии:

Релиз ядра Linux 4.14  (6)
Пятница 17.11, 16:12
Apple запустила Pay Cash (2)
Четверг 09.11, 21:15
Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...