Abstract
By allowing relationship types defined on top of relationship types, the Higher-Order Entity Relationship Model (HERM) enables modeling of complex conceptual structures in a layered way, which usually results in a more compact design than the traditional Entity-Relationship model. Identification of data instances is achieved by composition of the (inherited) key attributes of the referenced instances (foreign keys becoming part of natural keys of higher-order relationships). Well-formedness excludes cycles in the structure. In this paper, we look at the possibility to relax this by allowing structural recursion in the conceptual model. Although it is formally represented as a cycle in the type structure, it will not allow any cycle on the instance (data) level. After looking at some motivating cases and conventional alternatives to this design, and conditions when such a modeling decision is reasonable, we will show how a structurally recursive HERM model can be transformed into an equivalent, conventionally well-formed HERM model, with the utilization of list type construction and complex, variable-length key domains. The analysis reveals some non-trivial aspects of the way of transformation, which may be easily overlooked, but are important to formulate a translation rule for the general case, where derived attributes and aggregation needs are present. The result can be used as a rule for conceptual schema translation for structuring, to obtain an intermediate schema ready for further optimization, and eventually, code generation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Specialization is considered in HERM as a different case where the general type is subsistent, and its subtypes depend on it. To model this, the so-called unary relationships are used, which is not directly relevant for this paper.
References
AlBdaiwi, B., Noack, R., Thalheim, B.: Pattern-based conceptual data modelling. Front. Artif. Intell. Appl. 272, 1–20 (2014). https://doi.org/10.3233/978-1-61499-472-5-1
Arenas, M., Libkin, L.: An information-theoretic approach to normal forms for relational and xml data. J. ACM (JACM) 52(2), 246–283 (2005)
Bahmani, A., Naghibzadeh, M., Bahmani, B.: Automatic database normalization and primary key generation. In: 2008 Canadian Conference on Electrical and Computer Engineering, pp. 000011–000016, June 2008. https://doi.org/10.1109/CCECE.2008.4564486
Chen, P.: Entity-relationship modeling: historical events, future trends, and lessons learned. In: Broy, M., Denert, E. (eds.) Software Pioneers, pp. 296–310. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-642-59412-0_17
Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13(6), 377–387 (1970). https://doi.org/10.1145/362384.362685
Date, C.: Logic and Databases: The Roots of Relational Theory. Trafford Publishing (2007). https://books.google.de/books?id=2egNzTk871wC
Embley, D., Thalheim, B.: Handbook of Conceptual Modeling: Theory, Practice, and Research Challenges. Springer, Heidelberg (2012). https://books.google.de/books?id=oWmp10vBI7cC
Gamma, E., Helm, R., Johnson, R., Vlissides, J.M.: Design Patterns: Elements of Reusable Object-Oriented Software, 1st edn. Addison-Wesley Professional, United States (1994)
Klettke, M., Thalheim, B.: Evolution and migration of information systems. In: Embley, D., Thalheim, B. (eds.) Handbook of Conceptual Modeling, pp. 381–420. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-15865-0_12
Krtzsch, M., Hitzler, P., Zhang, G.: Morphisms in context (2005). www.aifb.uni-karlsruhe.de/WBS/phi/pub/KHZ05tr.pdf
Molnár, A.J.: Conceptual modeling of hiking trail networks with logical rules for consistent signage planning and management. In: Thalheim, B., Tropmann-Frick, M., Jaakkola, H., Kiyoki, Y. (eds.) Proceedings of the International Conference on Information Modelling and Knowledge Bases (EJC 2020). KCSS, vol. 2020/1, pp. 1–25. Department of Computer Science, Faculty of Engineering, Kiel University, June 2020. https://doi.org/10.21941/kcss/2020/1
Paton, N.W., Díaz, O.: Active database systems. ACM Comput. Surv. 31(1), 63–103 (1999)
Thalheim, B.: The conceptual model = an adequate and dependable artifact enhanced by concepts. Front. Artif. Intell. Appl. 260, 241–254 (2014)
Thalheim, B.: Foundations of entity-relationship modeling. Ann. Math. Artif. Intell. 7, 197–256 (1993). https://doi.org/10.1007/BF01556354
Thalheim, B.: Entity-Relationship Modeling: Foundations of Database Technology. Springer, Berlin (2000)
Thalheim, B., Jaakkola, H.: Model-based fifth generation programming. In: Dahanayake, A., Huiskonen, J., Kiyoki, Y., Thalheim, B., Jaakkola, H., Yoshida, N. (eds.) Information Modelling and Knowledge Bases XXXI - Proceedings of the 29th International Conference on Information Modelling and Knowledge Bases, EJC 2019, Lappeenranta, Finland, 3–7 June 2019. Frontiers in Artificial Intelligence and Applications, vol. 321, pp. 381–400. IOS Press (2019). https://doi.org/10.3233/FAIA200026
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Molnár, A.J. (2021). Structurally Recursive Patterns in Data Modeling and Their Resolution. In: Dahanayake, A., Pastor, O., Thalheim, B. (eds) Modelling to Program. M2P 2020. Communications in Computer and Information Science, vol 1401. Springer, Cham. https://doi.org/10.1007/978-3-030-72696-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-72696-6_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-72695-9
Online ISBN: 978-3-030-72696-6
eBook Packages: Computer ScienceComputer Science (R0)