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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:55008", author = "Georgia Garani", title = "A Generalised Relational Data Model", 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.", volume = "4", number = "3", pages = "434-17", }
