Компактное представление ограничений на основе новой интерпретации понятия "кортеж многоместного отношения"
Автор: Зуенко А.А.
Журнал: Онтология проектирования @ontology-of-designing
Рубрика: Методы и технологии принятия решений
Статья в выпуске: 4 (38) т.10, 2020 года.
Бесплатный доступ
Рассматриваются различные точки зрения на понятие «кортеж многоместного отношения», используемые в математике и информационных технологиях. Особое внимание уделено эволюции понятия «кортеж» в рамках технологии программирования в ограничениях - Constraint Programming , где появление новых интерпретаций понятия «кортеж» связано с попытками разработать более компактное табличное представление качественных зависимостей, чем обычные реляционные таблицы. Подобное компактное представление может служить основой для ускорения процедур удовлетворения качественных ограничений. В работах-прототипах были предложены такие разновидности табличных ограничений как compressed -таблицы и smart -таблицы. При этом понятия compressed - и smart - кортежа существенно отличаются от традиционного понятия кортежа многоместного отношения. Однако, известные виды табличных ограничений не одинаково хорошо подходят для моделирования и обработки всех видов качественных зависимостей, например, возникают неудобства при моделировании продукционных правил. В статье предлагается новый вид табличных ограничений - smart -таблицы D -типа, применение которых позволяет в некоторых случаях существенно сократить расход памяти компьютера по сравнению с использованием известных типов табличных ограничений. В частности, smart -таблицы D -типа хорошо подходят для моделирования продукционных правил, некоторых типов логических выражений, а также некоторых типов глобальных ограничений.
Кортеж многоместного отношения, технология программирования в ограничениях, задача удовлетворения ограничений, табличные ограничения, качественные ограничения
Короткий адрес: https://sciup.org/170178871
IDR: 170178871 | DOI: 10.18287/2223-9537-2020-10-4-503-515
Список литературы Компактное представление ограничений на основе новой интерпретации понятия "кортеж многоместного отношения"
- Кандрашина, Е.Ю. Представление знаний о времени и пространстве в интеллектуальных системах / Е.Ю. Кандрашина, Л.В. Литвинцева, Д. А. Поспелов. Под ред. Д.А. Поспелова. - М.: Наука, 1989. - 326 с.
- Осипов, Г. С. Методы искусственного интеллекта / Г.С. Осипов. - М.: Физматлит, 2011. - 296 с.
- Кузнецов, О.П. Онтологии в современных информационных системах: состояние, проблемы, перспективы / О.П. Кузнецов, В.С. Суховеров, Л.Б. Шипилина // Датчики и системы. - 2011. - №8 (147). - С.67-77.
- Maier, D. The Theory of Relational Databases. / D. Maier - Computer Science Press, 1983. 665 p.
- Bartak, R. Constraint Programming: In Pursuit of the Holy Grail / R. Bartak // Proceedings of the Week of Doctoral Students (WDS99), Part IV. - Prague: MatFyzPress, 1999. - P.555-564.
- Ruttkay, Zs. Constraint satisfaction a survey / Zs. Ruttkay // CWI Quarterly. - 1998. - Vol. 11. - P.163-214.
- Xia, W. Optimizing STR algorithms with tuple compression /W. Xia, R.H.C. Yap // CP 2013. LNCS, 8124. - 2013. - P.724-732.
- Perez, G. Improving GAC-4 for table and MDD constraints / G. Perez, J.C. Regin // CP 2014. LNCS, 8656. -2014. - P.606-621.
- Katsirelos, G. A compression algorithm for large arity extensional constraints / G. Katsirelos, T. Walsh // CP 2007. LNCS, 4741, - 2007. - P.379-393.
- Mairy, J. The Smart Table Constraint / J. Mairy, Y. Deville, C. Lecoutre // In: Michel, L. (eds.) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015. Lecture Notes in Computer Science. - Springer. Cham, - 2015. - Vol. 9075. - P.271-287.
- Кузнецов, О.П. Дискретная математика для инженера / О.П. Кузнецов. - СПб.: Лань, 2009. - 400 с.
- Russel, S. Artificial Intelligence: A Modern Approach. 3rd edition / S. Russel, P. Norvig. - Prentice Hall, 2010. -1132 P.
- Regin, J. A filtering algorithm for constraints of difference in CSPs / J. Regin // Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94). - Seattle: AAAI Press, - 1994. - P.362-367.
- Bessiere, C. Arc consistency for general constraint networks: preliminary results / C. Bessiere, J.C. Regin // Proceedings of IJCAI, - 1997. - P.398-404.
- Jefferson, C. Extending simple tabular reduction with short supports / C. Jefferson and P. Nightingale // Proceedings of IJCAI 2013, - 2013. - P.573-579.
- Zuenko, A. Development of n-tuple algebra for logical analysis of databases with the use of two-place predicates / A. Zuenko, A. Fridman // Journal of Computer and Systems Sciences International. - 2009. - Vol. 48(2). - P.254-261.
- Dao, T.B.H. Constrained Clustering by Constraint Programming / T.B.H. Dao, K.C. Duong, C. Vrain // Artificial Intelligence Journal, - 2017. - Vol. 244. - P.70-94.
- Baptiste, P. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems / P. Baptiste, C. Le Pape, W. Nuijten. - Kluwer Academic Publishers, 2001. - 203 P.
