A Generalised Relational Data Model

Authors: Georgia Garani

Abstract:

A generalised relational data model is formalised for the representation of data with nested structure of arbitrary depth. A recursive algebra for the proposed model is presented. All the operations are formally defined. The proposed model is proved to be a superset of the conventional relational model (CRM). The functionality and validity of the model is shown by a prototype implementation that has been undertaken in the functional programming language Miranda.

Keywords: nested relations, recursive algebra, recursive nested operations, relational data model.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1061932

References:

[1] S. Abiteboul, and N. Bidoit, "Non First Normal Form Relations: An Algebra Allowing Data Restructuring," Journal of Computer and System Sciences, vol. 33, no. 3, pp. 361-393, 1986.
[2] P.C. Fisher, and S.J. Thomas, "Operators for Non-First-Normal Form Relations," in Proc. of the 7th IEEE International Conference on Computer Software and Applications, Chicago, 1983, pp. 464-475.
[3] G. Jaeschke, and H.J. Schek, "Remarks on the Algebra of Non First Normal Form Relations", in Proc. of the ACM Symposium on Principles of Database Systems, Los Angeles, 1982, pp. 124-138.
[4] M.A. Roth, H.F. Korth, and A. Silberschatz, "Extended Algebra and Calculus for Nested Relational Databases," ACM Transactions on Database Systems, vol. 13, no. 4, pp. 389-417, 1988.
[5] H.-J. Schek, and M.H. Scholl, "The Relational Model with Relation- Valued Attributes," Information Systems, vol. 11, no. 2, pp. 137-147, 1986.
[6] S.J. Thomas, and P.C. Fischer, "Nested Relational Structures," International Journal of Artificial Intelligence, vol. 3, pp. 269-307, 1986.
[7] A. Makinouchi, "A consideration on Normal Form of Not-Necessarily- Normalized Relations in the Relational Data Model," in Proc. of the 3rd International Conference on Very Large Data Bases, Tokyo, 1977, pp. 447-453.
[8] V. Tannen, "Tutorial: Languages for Collection Types," in Proc. of the 13th ACM Symposium on Principles of Database Systems, Minneapolis, 1994, pp. 150- 154.
[9] N.A. Lorentzos, and A. Dondis, "Query by Example for Nested Tables," in Proc. of the 9th International Conference on Database and Expert Systems Applications, Vienna, 1998, pp. 716-725.
[10] M.A. Roth, H.F. Korth, and D.S. Batory, "SQL/NF: A Query Language for ¬1NF Relational Databases," Information Systems, vol. 12, no. 1, pp. 99-114, 1987.
[11] L. Wegner, S. Thelemann, S. Wilke, and R. Lievaart, "QBE-like Queries and Multimedia Extensions in a Nested Relational DBMS," in Proc. of the International Conference on Visual Information Systems, Melbourne, 1996, pp. 437-446.
[12] G. Özsoyoglu, Z.M. Özsoyoglu, and V. Matos, "Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions," ACM Transactions on Database Systems, vol. 12, no. 4, pp. 566-592, 1987.
[13] L.S. Colby, "A Recursive Algebra for Nested Relations," Information Systems, vol. 15, no. 5, pp. 567-582, 1990.
[14] M. Levene, "The Nested Universal Relation Database Model," Lecture Notes in Computer Science 595, Berlin: Springer-Verlag, 1992.
[15] Hong-Cheu Liu, and K. Ramamohanarao, "Multiple Paths Join for Nested Relational Databases." in Proc. of the 5th Australian Database Conference, 1994, pp. 30-44.
[16] M. Levene, and G. Loizou, "Correction to Null Values in Nested Relational Databases by M.A. Roth, H.F. Korth and A. Silberschatz," Acta Informatica, vol. 28, pp. 603-605, 1991.
[17] A. Tansel, and L. Garnett, "On Roth, Korth, and Silberschatz-s Extended Algebra and Calculus for Nested Relational Databases," ACM Transactions on Database Systems, vol. 17, no. 2, pp. 374-383, 1992.
[18] V. Deshpande, and P.A Larson, "An Algebra for Nested Relations with Support for Nulls and Aggregates," Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, Tech. Rep. CS-91- 16, 1991.
[19] Hong-Cheu Liu, and K. Ramamohanarao, "Algebraic Equivalences among Nested Relational Expressions," in Proc. of the 3rd International Conference on Information and Knowledge Management, Gaithersburg, 1994, pp. 234-243.
[20] P. Buneman, S. Naqvi, V. Tannen, and L. Wong, "Principles of Programming with Complex Objects and Collection Types," Theoretical Computer Science, vol. 149, no. 1, pp. 3-48, 1995.
[21] J.D. Ullman, Principles of Database and Knowledge-Base Systems. New York: Computer Science Press, 1995.
[22] C.J. Date, An Introduction to Database Systems, 2nd ed. New York: Addison-Wesley, 2000.
[23] G. Garani, and R. Johnson, "Joining nested relations and subrelations," Information Systems, vol. 25, no. 4, pp. 287-307, 2000.
[24] J. Paredaens, and D. Van Gucht, "Converting Nested Algebra Expressions into Flat Algebra Expressions," ACM Transactions on Database Systems, vol. 17, no.1, pp. 65-93, 1992.