Converting nested algebra expressions into flat algebra expressions

ABSTRACT

Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive power of the nested algebra relative to its operation on flat relational databases. We show that the flat relational algebra is rich enough to extract the same “flat information” from a flat database as the nested algebra does. Theoretically, this result implies that recursive queries such as the transitive closure of a binary relation cannot be expressed in the nested algebra. Practically, this result is relevant to (flat) relational query optimization.

REFERENCES

• 1: ABITEBOUL, S., AND BEEm, S. On the power of languages for the manipulation of complex objects. INRIA Tech. Rep. 846. 1988.
• 2: Serge Abiteboul , Nicole Bidoit, Non first normal form relations: An algebra allowing data restructuring, Journal of Computer and System Sciences, v.33 n.3, p.361-393, Dec. 1986 [doi>10.1016/0022-0000(86)90058-9]
• 3: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 4: Hiroshi Arisawa , Kunihiko Moriya , Takao Miura, Operations and the Properties on Non-First-Normal-Form Relational Databases, Proceedings of the 9th International Conference on Very Large Data Bases, p.197-204, October 31-November 02, 1983
• 5: Francois Bancilhon, A logic-programming/object-oriented cocktail, ACM SIGMOD Record, v.15 n.3, p.11-21, Sept. 1986 [doi>10.1145/15833.15835]
• 6: Francois Bancilhon , Setrag Khoshafian, A calculus for complex objects, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.53-60, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15404]
• 7: François Bancilhon , Philippe Richard , Michel Scholl, On Line Processing of Compacted Relations, Proceedings of the 8th International Conference on Very Large Data Bases, p.263-269, September 08-10, 1982
• 8: Catriel Beeri , Yoram Kornatzky, The Many Faces of Query Monotonicity, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.120-135, March 26-30, 1990
• 9: C. Beeri , S. Naqvi , R. Ramakrishnan , O. Shmueli , S. Tsur, Sets and negation in a logic data base language (LDL1), Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.21-37, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28662]
• 10: N. Bidoit, The Verso algebra or how to answer queries with fewer joins, Journal of Computer and System Sciences, v.35 n.3, p.321-364, Dec. 1987 [doi>10.1016/0022-0000(87)90019-5]
• 11: CODD, E. F. Relational completeness of database sublanguages. In Database Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J, 1972, pp. 65-98.
• 12: Latha S. Colby, A recursive algebra and query optimization for nested relations, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.273-283, June 1989, Portland, Oregon, United States
• 13: P. Dadam, Advanced information management (AIM): research in extended nested relations, Data Engineering, v.11 n.3, p.4-14, September 1988
• 14: P. Dadam , K. Kuespert , F. Andersen , H. Blanken , R. Erbe, A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.356-367, May 28-30, 1986, Washington, D.C., United States
• 15: U. Deppisch , H.-B. Paul , H.-J. Schek, A storage system for complex objects, Proceedings on the 1986 international workshop on Object-oriented database systems, p.183-195, September 23-26, 1986, Pacific Grove, California, United States
• 16: DE$HPANDE, A., AND VAN GUCHT, D. A storage structure for unnormalized relations. In Proceedings of the GI Conference on Database Systems for Office Automation, Eng~neering and Scientific Applications (Apr. 1987, Darmstadt, Germany) Inf Fachber~chte 136 (1987), 481-486.
• 17: Anand Deshpande , Dirk Van Gucht, An Implementation for Nested Relational Databases, Proceedings of the 14th International Conference on Very Large Data Bases, p.76-87, August 29-September 01, 1988
• 18: DES~PANDE, V., AND LARSON, P. A. An algebra for nested relatmns. Res. Rep CS-87-65, Dept. of Computer Science, Univ. of Waterloo, Ontario, 1987.
• 19: Marc Gyssens , Dirk van Gucht, The powerset algebra as a result of adding programming constructs to the nested relational algebra, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.225-232, June 01-03, 1988, Chicago, Illinois, United States
• 20: Marc Gyssens , Dirk Van Gucht, The powerset algebra as a natural tool to handle nested database relations, Journal of Computer and System Sciences, v.45 n.1, p.76-103, Aug. 1992 [doi>10.1016/0022-0000(92)90041-G]
• 21: Marc Gyssens , Dirk van Gucht, A uniform approach toward handling atomic and structured information in the nested relational database model, Journal of the ACM (JACM), v.36 n.4, p.790-825, Oct. 1989 [doi>10.1145/76359.76364]
• 22: HOUBEN, G., AND PAREDAENS, J. The R2-algebra: An extension of an algebra for nested relatmns. Tech. Rep., Computer Science Dept., Techmcal Univ., Eindhoven, The Netherlands, 1987.
• 23: Richard Hull , Jianwen Su, On the expressive power of database queries with intermediate types, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.39-51, March 1988, Austin, Texas, United States [doi>10.1145/308386.308409]
• 24: G. Jaeschke , H. J. Schek, Remarks on the algebra of non first normal form relations, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588133]
• 25: Gabriel M. Kuper, Logic programming with sets, Journal of Computer and System Sciences, v.41 n.1, p.44-64, August 1990 [doi>10.1016/0022-0000(90)90033-H]
• 26: G. M. Kuper , M. Y. Vardi, On the complexity of queries in the logical data model, Lecture notes in computer science on ICDT '88, p.267-280, October 1988, Bruges, Belgium
• 27: P. Larson, The data model and query language of LauRel, Data Engineering, v.11 n.3, p.23-30, September 1988
• 28: Volker Linnemann, Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach, Proceedings of the Third International Conference on Data Engineering, p.591-598, February 03-05, 1987
• 29: MAKINOUCm, A. A consideration of normal form of not-necessarily-normalized relations in the relational data model. In Proceedings of the 3rd VLDB (Oct. 1977, Tokyo). VLDB Endowment, 1977, pp. 447-453.
• 30: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 31: G. Özsoyoğlu , Z. M. Özsoyoğlu , V. Matos, Extending relational algebra and relational calculus with set-valued attributes and aggregate functions, ACM Transactions on Database Systems (TODS), v.12 n.4, p.566-592, Dec. 1987 [doi>10.1145/32204.32219]
• 32: Jan Paredaens , Paul De Bra , Marc Gyssens , Dirk Van Gucht, The structure of the relational database model, Springer-Verlag New York, Inc., New York, NY, 1989
• 33: H. B. Paul , H. J. Schek , M. H. Scholl, Architecture and implementation of the Darmstadt database kernel system, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.196-207, May 27-29, 1987, San Francisco, California, United States
• 34: Peter Pistor , F. Andersen, Designing A Generalized NF2 Model with an SQL-Type Language Interface, Proceedings of the 12th International Conference on Very Large Data Bases, p.278-285, August 25-28, 1986
• 35: P Pistor , R Traunmueller, A database language for sets, lists and tables, Information Systems, v.11 n.4, p.323-336, Oct. 1986 [doi>10.1016/0306-4379(86)90012-8]
• 36: Mark A. Roth , Henry F. Korth , Don S. Batory, SQL/NF: a query language for ¬ 1NF relational databases, Information Systems, v.12 n.1, p.99-114, Jan. 1987 [doi>10.1016/0306-4379(87)90021-4]
• 37: Mark A. Roth , Herry F. Korth , Abraham Silberschatz, Extended algebra and calculus for nested relational databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.389-417, Dec. 1988 [doi>10.1145/49346.49347]
• 38: H J Schek , M H Scholl, The relational model with relation-valued attributes, Information Systems, v.11 n.2, p.137-147, 1986 [doi>10.1016/0306-4379(86)90003-7]
• 39: H. -J. Schek , H. -B. Paul , M. H. Scholl , G. Weikum, The DASDBS Project: Objectives, Experiences, and Future Prospects, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.25-43, March 1990 [doi>10.1109/69.50904]
• 40: Marc H Scholl, Theoretical foundation of algebraic optimization utilizing unnormalized relations, Proceedings on International conference on database theory, p.380-396, December 1986, Rome, Italy
• 41: Marc H. Scholl , H.-Bernhard Paul , Hans-Jörg Schek, Supporting Flat Relations by a Nested Relational Kernel, Proceedings of the 13th International Conference on Very Large Data Bases, p.137-146, September 01-04, 1987
• 42: Gail M. Shaw , Stanley B. Zdonik, A Query Algebra for Object-Oriented Databases, Brown University, Providence, RI, 1989
• 43: THOMAS, S. J., AND F~SCHER, P.C. Nested relational structures. In Advances in Computing Research III, The Theory of Databases~ P. C. Kanellakis, Ed. JAI Press, Greenwich, Conn., 1986, pp. 269-307.
• 44: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Languages, Theory

Keywords:
algebraic query transformation, nested algebra, nested calculus, nested relations, relational databases