Doklady Tomskogo gosudarstvennogo universiteta sistem upravleniya i radioelektroniki / Archive / Issue of Journal № 2, Vol. 27, 2024 / Methods for storing AND/OR tree structures and their variants in RAM and ROM

Methods for storing AND/OR tree structures and their variants in RAM and ROM

DOI: 10.21293/1818-0442-2024-27-2-44-50

Download article in PDF format

JATS xml

Abstract: Tree structures are widely used to represent information objects containing hierarchical relations between their parts. An example of such tree structures are AND/OR trees, that have found their application in the development of combinatorial generation algorithms and related tasks. This paper explores possible ways to store tree structures in the random access memory (RAM) and read only memory (ROM) of devices that process these structures. The adaptation of these methods to the problem of storing AND/OR tree structures and their variants is also considered. In addition, to organize operational work with stored variants of the AND/OR tree, the authors propose the bijective mapping of an AND/OR tree structure to a relational database schema.

Keywords: tree structure, AND/OR variant, random access memory, read only memory, data structure, linked list, relational database

Funding: This work was supported by the Russian Science Foundation under research project No. 22-71-10052.

For citation:
Shablya Yu. V., Tokareva A. V. Methods for storing AND/OR tree structures and their variants in RAM and ROM. Doklady Tomskogo gosudarstvennogo universiteta sistem upravleniya i radioelektroniki, 2024, vol. 27, no. 2, pp. 44–50. DOI: 10.21293/1818-0442-2024-27-2-44-50

Authors and copyright holders:

Shablya Yu. V. , Tomsk State University of Control Systems and Radioelectronics (Tomsk, Russia)
Tokareva A. V. , Tomsk State University of Control Systems and Radioelectronics (Tomsk, Russia)

1. Subero A. Codeless data structures and algorithms. USA, CA, Berkeley, Apress, 2020, 143 p.
2. Celko J. Trees and hierarchies in SQL for smarties. USA, Morgan Kaufmann Publishers, 2012, 296 p.
3. Aho A.V., Hopcroft J.E., Ullman J.D. Data structures and algorithms. USA, Addison-Wesley, 1983, 427 p.
4. Miheev M.Y. Prokof'ev O.V., Semochkina I.B. [Treemaps to improve quality of support of decision]. Reliability and Quality of Complex Systems, 2021, no. 1, pp. 76–86 (in Russ.).
5. Sharov V.Y., Gorshkova Y.Y., Filonenko I.N. [Preservation of treelike structures in a database and management of them]. Complex Problems of Development of Science, Education and Economics of the Region, 2015, no. 2, pp. 223–231 (in Russ.).
6. Knuth D. The art of computer programming. Volume 1: Fundamental algorithms. USA, Addison-Wesley, 1997, 654 p.
7. Kruchinin V.V., Lukschin B.A. [Method of coding of information objects on the basis of trees and-or]. Proceedings of TUSUR University, 2010, no. 1(21), pp. 170–172 (in Russ.).
8. Zorin Y.A. [The interpreter of programming language for design generators of tests based on AND/OR trees]. Proceedings of TUSUR University, 2013, no. 1(27), pp. 75–79 (in Russ.).
9. Shablya Y.V. [A method for compressing event log data based on combinatorial generation using AND/OR tree structures]. Modern Information Technologies and IT-education, 2023, vol. 19, no. 3 (in Russ.).
10. Tokareva A.V., Kruchinin D.V. [Modification of the method for identifying and tracing complex technical products using combinatorial generation algorithms based on AND/OR trees]. The Herald of the Siberian State University of Telecommunications and Information Science, 2024, vol. 18, no. 3 (in Russ.).
11. Babenko M.A., M.V. Vvedenie v teoriyu algoritmov i struktur dannyh [Introduction to the theory of algorithms and data structures]. Moscow, FMOP, MCNMO Publ., 2012. 144 p. (in Russ.).
12. Wang Z., Chen S. Exploiting common patterns for tree-structured data. Proceedings of the 2017 ACM International Conference on Management of Data. 2017, pp. 883–896.
13. Grebenshchikov N.N. [Representation of tree dependency in a relational database]. Software Products and Systems, 2008, no. 1, pp. 41–44 (in Russ.).
14. Bogdanov D.V. [The optimal way to store and process tree structures in databases]. Software Products and Systems, 2009, no. 1, pp. 140–142.
15. Zasyadko G.E., Karpov A.V. [Problems of graph database development]. Engineering Journal of Don, 2017, no. 1 (in Russ.).
16. Renzo A., Gutierrez C. Survey of graph database models. ACM Computing Surveys, 2008, vol. 40, no. 1, Article 1.
17. Guralnik R.I. [Some problems on graph databases]. Proc. ISP RAS, 2016, vol. 28, no. 4, pp. 193–216 (in Russ.).
18. Monteiro J., Sa F., Bernardino J. Experimental evaluation of graph databases: JanusGraph, Nebula Graph, Neo4j, and TigerGraph. Applied Sciences, 2023, vol. 13, no. 9, Article 5770.