Decompositional Extraction and Retrieval of Conceptual Knowledge

D.O. Terletskyi, S.V. Yershov


An ability to extract hidden and implicit knowledge, their integration into a knowledge base, and then retrieval of required knowledge items are important features of knowledge processing for many modern knowledge-based systems. However, the complexity of these tasks depends on the size of knowledge sources, which were used for extraction, the size of a knowledge base, which is used for the integration of extracted knowledge, as well as the size of a search space, which is used for the retrieval of required knowledge items. Therefore, in this paper, we analyzed the internal semantic dependencies of homogeneous classes of objects and how they affect the decomposition of such classes. Since all subclasses of a homogeneous class of objects form a complete lattice, we applied the methods of formal concept analysis for the knowledge extraction and retrieval within the corresponding concept lattice. We found that such an approach does not consider internal semantic dependencies within a homogeneous class of objects, consequently, it can cause inference and retrieval of formal concepts, which are semantically inconsistent within a modeled domain. We adapted the algorithm for the decomposition of homogeneous classes of objects, within such knowledge representation model as object-oriented dynamic networks, to perform dynamic knowledge extraction and retrieval, adding additional filtration parameters. As the result, the algorithm extracts knowledge via constructing only semantically consistent subclasses of homogeneous classes of objects and then filters them according to the attribute and dependency queries, retrieving knowledge. In addition, we introduced the decomposition consistency coefficient, which allows estimation of how much the algorithm can reduce the search space for knowledge extraction and improves the performance. To demonstrate some possible application scenarios for the improved algorithm, we provided an appropriate example of knowledge extraction and retrieval via decomposition of a particular homogeneous class of objects.

Prombles in programming 2022; 3-4: 139-153


internal semantic dependencies; decomposition consistency; decomposition of classes; knowledge extraction; knowledge retrieval


AMBLER, S. W. (2003) Agile Database Techniques: Effective Strategies for the Agile Software Developer. Indianapolis, IN, USA: John Willey & Sons, Ltd.

AMBLER, S. W. (2004) The Object Primer: Agile Model-Driven Development with UML 2.0. 3rd Ed. New York, NY, USA: Cambridge University Press. CrossRef

APT, K. R. (2003) Principles of Constraint Programming. New York, NY, USA: Cambridge University Press. CrossRef

BAIXERIES, J., KAYTOUE, M. & NAPOLI, A. (2014) Characterizing functional dependencies in formal concept analysis with pattern structures. Annals of Mathematics and Artificial Intelligence. 72 (1-2). pp. 129-149. CrossRef

BAIXERIES, J., KAYTOUE, M. & NAPOLI, A. (2014) Characterization of Database Dependencies with FCA and Pattern Structures. In: IGNATOV, D. I. et al. (Eds.). Analysis of Images, Social Networks and Texts. AIST 2014. Communication in Computer and Information Science, vol. 436. Switzerland AZ: Springer, Cham. CrossRef

BAIXERIES, J. et al. (2022) Computing Dependencies Using FCA. In: MISSAOUI, R., KWUIDA, L. & ABDESSALEM, T. (Eds.). Complex Data Analytics with Formal Concept Analysis. Switzerland AZ: Springer Cham. CrossRef

CARPINETO, C. & ROMANO, G. (2004) Concept data analysis: Theory and application. New York, NY, USA: John Willey & Sons, Ltd. CrossRef

CARUCCIO, L., DEUFEMIA, V. & POLESE, G. (2016) Relaxed Functional Dependencies - A Survey of Approaches. IEEE Transactions on Knowledge and Data Engineering. 28 (1). pp. 147-165. CrossRef

CODOCEDO, V. et al. (2013) Using pattern structures to support information retrieval with Formal Concept Analysis. In: Proceedings of the International Workshop "What can FCA do for Artificial Intelligence?" (FCA4AI at IJCAI 2013). Beijing, China, 5 August 2013. pp. 15-24.

CODOCEDO, V., LYKOURENTZOU, I. & NAPOLI, A. (2014) A semantic approach to concept lattice-based information retrieval. Annals of Mathematics and Artificial Intelligence. 72 (1-2). pp. 169-195. CrossRef

CODOCEDO, V. & NAPOLI, A. (2015) Formal Concept Analysis and Information Retrieval - A Survey. In: BAIXERIES. J., SACAREA, C. & OJEDA-ACIEGO, M. (Eds.). Formal Concept Analysis. ICFCA 2015. Lecture Notes in Computer Science, vol. 9113. Switzerland AZ:Springer Cham. CrossRef

DECHTER, R. (2003) Constraint Processing. Sam Francisco, CA, USA: Morgan Kaufmann Publishers. CrossRef

DEKEL, U. (2002) Applications of Concept Lattices to Code Inspection and Review. In: Proceedings of the Israeli Workshop on Programming Languages and Development Environments. IBM Haifa Research Lab, July 1, 2002.

DEKEL, U. & GIL, Y. (2003) Revealing Class Structure with Concept Lattices. In: Proceedings of the 10th Working Conference on Reverse Engineering (WCRE'03). Victoria, BC, Canada, 13-16 November 2003. USA: The Printing House. pp. 353-363. CrossRef

DOMINICH, S. (2008) The Modern Algebra of Information Retrieval. Berlin, Heidelberg: Springer. CrossRef

DUBOIS, D., PRADE, H. & ROSSAZZA J.-P. (1991) Vagueness, typicality, and uncertainty in class hierarchies. International Journal of Intelligent Systems. 6 (2). p. 167-183. CrossRef

FKIH, F. & OMRI, M. N. (2016) IRAFCA: an O(n) information retrieval algorithm based on formal concept analysis. Knowledge and Information Systems. 48 (2). p. 465-491. CrossRef

FKIH, F. & OMRI, M. N. (2018) FCA_Retrieval: A Multi-operator Algorithm for Information Retrieval from Binary Concept Lattice. In: Proceedings of the 32nd Pacific Asia Conference on Language, Information and Computation, PACLIC 2018. Hong Kong, 1-3 December 2018. Association for Computational Linguistics. pp. 164-171.

FREUDER, E. C. & MACKWORTH, A. K. (2006) Constraint satisfaction: an emerging paradigm. In: ROSSI, F., van BEEK, P. & WALSH, T. (Eds.). Handbook of Constraint Programming. Amsterdam: Elsevier. CrossRef

GANTER, B. & WILLE, R. (1999) Formal Concept Analysis: Mathematical Foundations. Berlin, Heidelberg: Springer. CrossRef

GANTER, B., RUDOLPH, S. & STUMME, G. (2019) Explaining Data with Formal Concept Analysis. In: KROTZSCH M. & STEPANOVA D. (Eds.). Reasoning Web. Explainable Artificial Intelligence. Lecture Notes in Computer Science, vol. 11810. Switzerland AZ: Springer Cham. CrossRef

GOLDBLATT, R. (1984) Topoi. The Categorial Analysis of Logic. Studies in Logic and the Foundations of Mathematics, vol. 98. Revised edition. Amsterdam: Elsevier Science Publishers B.V.

JOSHI, P. & JOSHI, R. J. (2009) Concept Analysis for Class Cohesion. In: 13th European Conference on Software Maintenance and Reengineering. Kaiserslautern, Germany, 24-27 March 2009. IEEE. pp. 237-240. CrossRef

KWUIDA, L. et al. (2014) Generalized pattern extraction from concept lattices. Annals of Mathematics and Artificial Intelligence. 72 (1-2). p. 151-168. CrossRef

MESSAI, N. et al. (2008) Extending Attribute Dependencies for Lattice-Based Querying and Navigation. In EKLUND, P. & HAEMMERLE, O. (Eds.). Conceptual Structures: Knowledge Visualization and Reasoning. ICCS 2008. Lecture Notes in Computer Science, vol. 5113. Berlin, Heidelberg: Springer. CrossRef

TERLETSKYI, D. O. & PROVOTAR, O. I. (2014) Object-oriented dynamic networks. In: SETLAK, G. & MARKOV, K. (Eds.). Computational Models for Business and Engineering Domains. International Book Series Information Science and Computing, vol. 30. Rzeszow-Sofia: ITHEA.

TERLETSKYI, D. O. & PROVOTAR, O. I. (2014) Mathematical foundations for designing and development of intelligent systems of information analysis. Problems in Programming. 16 (2-3). p. 233-241.

TERLETSKYI, D. O. (2020) Run-Time Class Generation: Algorithm for Decomposition of Homogeneous Classes. In: LOPATA, A. et al. (Eds.). Information and Software Technologies. ICIST 2020. Communications in Computer and Information Science, vol. 1283. Switzerland AZ: Springer Cham. CrossRef

TIWARI, M. & JOSHI, P. (2012) Method Cohesion Analysis through Concept Lattices. ACM SIGSOFT Software Engineering Notes. 37 (3). p. 1-4. CrossRef

TONELLA, P. (2003) Using a Concept Lattice of Decomposition Slices for Program Understanding and Impact Analysis. IEEE Transactions on Software Engineering. 29 (6). p. 495-509. CrossRef

WILLE, R. (2006) Methods of Conceptual Knowledge Processing. In: MISSAOUI, R. & SCHMID, J. (Eds.). Formal Concept Analysis. ICFCA 2006. Lecture Notes in Computer Science, vol. 3874. Berlin, Heidelberg: Springer. CrossRef

YAO, H. & HAMILTON, H. J. (2008) Mining functional dependencies from data. Data Mining and Knowledge Discovery. 16 (2). p. 197- 219. CrossRef



  • There are currently no refbacks.