An equational object-oriented data model and its data-parallel query language

ABSTRACT

This paper presents an equational formulation of an object-oriented data model. In this model, a database is represented as a system of equations over a set of oid's, and a database query is a transformation of a system of equations into another system of equations. During the query processing, our model maintains an equivalence relation over oid's that relates oid's corresponding to the same "real-world entity." By this mechanism, the model achieves a declarative set-based query language and views for objects with identity. Moreover, the query primitives are designed so that queries including object traversal can be evaluated in a data-parallel fashion.

References

1. AB91.Serge Abiteboul and Anthony Bonner. Objects and views. In Proc. ACM SIGMOD Conference, pages 238-247, Jun. 1991.
2. ABGO93.Antonio Albano, R. Bergamini, Giorgio Ghelli, and Renzo Orsini. An object data model with roles. In Proc. VLDB Conference, pages 39-51, Aug. 1993.
3. AK89.Serge Abiteboul and Paric C. Kanellakis. Object identity as a query language primitive. In Proc. A CM SIGMOD Conference, pages 159-173, Jun. 1989.
4. BBKV88.Francois Bancilhon, Ted Briggs, Setrag Khoshafian, and Patrick Valduriez. FAD. a powerful and simple database language. in Proc. VLDB Conference, pages 97-105, Sep. 1988.
5. BCD89.Francois Bancilhon, Sophie Cluet, and Claude Delobel. A query language for the 02 object-oriented database system. In Proc. Int. Workshop on DBPL, pages 122- 138, Jun. 1989.
6. BKK88.Jay Banerjee, Won Kim, and Kyung-Chang Kim. Queries in object-oriented databases. In Proc. IEEE ICDE, pages 31-38, Feb. 1988.
7. Bee95.Catriel Beeri A Formal Approach to Object-Oriented Databases. Data and Knowledge Engineering, 5:353-382, 1990.
8. Ble90.G.E. Blelloch. Vector Models for Data- Parallel Computing. MIT Press, 1990.
9. Ble93.G.E. Blelloch. NESL: A nested data parallel language. Technical Report CMU- CS-93-129, Carnegie Mellon University, 1993.
10. BNTW95.Peter Buneman, Shamim A. Naqvi, Val Tannen, and Limsoon Wong. Principles of programming with complex objects and collection types. Theoretical Computer Science, 149(1 ):3--48, Sep. 1995.
11. BO96.Peter Buneman and Atsushi Ohori. Polymorphism and type inference in database programming. ACM Transactions on Database Systems, 21 (1), 30-76, 1996.
12. Car88.Luca Cardelli. A semantics of multiple inheritance. Information and Computation, 76:138-164, 1988.
13. Cat94.R.G.G. Cattell. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1994.
14. CK86.Hong-Tai Chou and Won Kim. A unifying framework for versions in a CAD environment. In Proc. VLDB Conference, pages 336-344, Aug. 1986.
15. Day89.Umeshwar Dayal. Queries and views in an object-oriented data model. In Proc. Int. Workshop on DBPL, pages 80-102, Jun. 1989.
16. DG92.David DeWitt and Jim Gray. Parallel database systems: The future of high performance database systems. CA CM, 35(6):85-98, Jun. 1992.
17. HQ91.Hatcher, P.J. and Quinn, M.J. Data-Parallel Programming on MIMD Computers. The MIT Press, 1991.
18. HY90.Richard Hull and Masatoshi Yoshikawa. ILOG: Declarative creation and manipulation of object identifiers. In Proc. VLDB Conference, pages 455-468, Aug. 1990.
19. HZ90.Sandra Heiler and Stanley B. Zdonik. Object views: Extending the vision. In Proc. IEEE ICDE, pages 86-93, Feb. 1990.
20. Jaj92.J. Jaja. An Introduction to Parallel Algorithm. Addison-Wesley, 1992.
21. Kar87.A. Karp. Programming for parallelism. IEEE Computer, pages 43-57, May 1987.
22. KC86.Setrag Khoshafian and George P. Copeland. Object identity. In Proc. ACM OOPSLA Conference, pages 406-416, Nov. 1986.
23. Kim89.Won Kim. A model of queries for object-oriented databases. In Proc. VLDB Conference, pages 423-432, Aug. 1989.
24. KSW86.Peter Klahold, Gunter Schlageter, and Wolfgang Wilkes. A general model for version management in databases. In Proc. VLDB Conference, pages 319-327, Aug. 1986.
25. LRV88.C. Lecluse, P. Richard, and F. Velz. 02, an object-oriented data model. In Proc. ACM SIGMOD Conference, pages 424-433, Jun. 1988.
26. NO95.S. Nishimura and A. Ohori. A calculus for exploiting data parallelism on recursively defined data (preliminary report). In Proc. International Workshop on Theory and Practice on Parallel Programming, LNCS vol. 907, pages 413-432, 1995.
27. Oho95.Atsushi Ohori. A polymorphic record calculus and its compilation. A CM Transactions on Programming Languages and Systems, 17(6):844-895, 1995.
28. PP93.J. Prins and D. Palmer. Transforming highlevel data-parallel programs into vector operations. In Proc. ACM Symposium on Principles and Practice of Parallel Programming, pages 119-128, 1993.
29. Run92.Elke A. Rundensteiner. Multiview: A methodology for supporting multiple views in object-oriented databases. In Proc. VLDB Conference, pages 187-198, Aug. 1992.
30. SS90.Marc H. Scholl and Hans-Jorg Schek. A relational object model. In Proc. ICDT, LNCS vol. 470, pages 89-105. Springer- Verlag, Dec. 1990.
31. SZ89.Gail M. Shaw and Stanley B. Zdonik. An object-oriented query algebra. In Proc. Int. Workshop on DBPL, pages 103-112, Jun. 1989.
32. TBN91.Val Tannen, Peter Buneman, and Shamim Naqvi. Structural recursion as a query language. In Proc. Int. Workshop on DBPL, pages 9-19, Aug. 1991.
33. YCWT93.Philip S. Yu, Ming-Syan Chen, Joel L. Wolf, and John Turek. Parallel query processing. In Nabil R. Adam and Bharat K. Bhargava, editors, Advanced Database Systems, LNCS vol. 759, chapter 12, pages 229-258, 1993.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

• Information systems

  • Data management systems

    • Data structures

    • Database design and models

    • Database management system engines

      • Database query processing

    • Query languages

  • Information storage systems

    • Record storage systems

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

  • Semantics and reasoning

    • Program constructs

      • Type structures

  • Theory and algorithms for application domains

    • Database theory

      • Data structures and algorithms for data management

      • Database query processing and optimization (theory)