Database theory column

Abstract

Complex object databases have been proposed as a significant extension of relational databases, with many practical applications. In the second database theory column, we present languages for the manipulation of such databases: a many-sorted algebra and an equivalent calculus. Without attempting to standardize, we try to provide general and short definitions that highlight the two key constructors of complex objects: tuples and (finite) sets. We comment on issues, such as language expressive power and complexity, and we describe equivalent rule-based languages with fixpoint semantics. Finally, we review the state-of-the art in database complex objects and list some interesting open questions.

References

1. [ABe] S. Abiteboul, C. Beeri. "On the Power of Languages for the Manipulation of Complex Objects". INRIA Research Report 846, (1988). Abstract in Proc. International Workshop on Theory and Applications of Nested Relations and Complex Objects, Darmstadt (1987).
2. [ABi] S. Abiteboul, N. Bidoit. "Non first normal form relations: an algebra allowing data restructuring". JCSS, 33:3, 361-371 (1986).
3. [ABGG] S. Abiteboul, C. Beeri, D. van Gucht, M. Gyssens. "An introduction to the completeness of languages for Complex Objects and Nested Relations". Nested Relations and Complex Objects, LNCS 361, Springer Verlag, 1989.
4. [AG] S. Abiteboul, S. Grumbach. "COL: a Language for Complex Objects based on Recursive Rules". To appear in ACM TODS. Abstract in Proc. Workshop on Database Programming Languages, Roskoff (1987).
5. [AH] S. Abiteboul, R. Hull. "IFO, a Formal Semantic Database Model." ACM TODS, 12:4, 525-565 (1987).
6. [AK] S. Abiteboul, P. Kanellakis. "Object Identity as a Query Language Primitive". Proc. ACM SIGMOD, 159-173 (1989).
7. [AV] S. Abiteboul, V. Vianu. "Procedural and Declarative Database Update Language". To appear in JCSS. Proc. 7th ACM PODS, 240-250 (1988).
8. [Ac] P. Aczel. Non-Well-Founded Sets, CSLI Lecture Notes 14, Stanford (1988).
9. [AU] A.V. Aho, J.D. Ullman. "Universality of Data Retrieval Languages". Proc. 6th POPL, 110-117 (1979).
10. [B] F. Bancilhon. "Object-Oriented Database Systems". Proc. 7th ACM PODS, 152-162 (1988).
11. [BK] F. Bancilhon, S. Khoshafian, "A Calculus for Complex Objects". Proc. 5th ACM PODS, 53-60 (1986).
12. [BRS] F. Bancilhon, P. Richard, M. Scholl. "On Line Processing of Compacted Relations". Proc. 8th VLDB, 263-269 (1982).
13. [Be+] C. Beeri, et al. "Sets and Negation in a Logic Database Language (LDL1)". Proc. 6th ACM PODS, 21-37 (1987).
14. [CH1] A.K. Chandra, D. Harel. "Computable Queries for Relational Data Bases". JCSS, 21:2, 156-178 (1980).
15. [CH2] A.K. Chandra, D. Harel. "Structure and Complexity of Relational Queries". JCSS, 25:1, 99-128 (1982).
16. [DM] E. Dahlhaus, J.A. Makowsky. "Computable Directory Queries". Technical Report, Technion, Haifa (1985).
17. [GvG] M. Gyssens, D. van Gucht. "The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra". Proc. ACM SIGMOD, 225-233 (1988).
18. [HMT] L. Henkin, J.D. Monk, A. Tarski. Cylindric Algebras: Part I, North Holland (1971).
19. [H] R. Hull. "A Survey of Theoretical Research on Typed Complex Database Objects". Databases, J. Paredaens ed., Academic Press, 193-256 (1987).
20. [HS1] R. Hull, J. Su. "On the Expressive Power of Database Queries with Intermediate Types". Proc. 7th ACM PODS, 39-51 (1988).
21. [HS2] R. Hull, J. Su. "Untyped Sets, Invention, and Computable Queries". Proc. 8th ACM PODS, 347-360 (1989).
22. [J] B. Jacobs. "On Database Logic". J ACM 29:2, 310-332 (1982).
23. [JS] B. Jaeschke, H.J. Schek. "Remarks on the algebra of non first normal form relations". Proc. 1st ACM PODS, 124-138 (1982).
24. [KRS] H.F. Korth, M.A. Roth, and A. Silberschatz. "Extended Algebra and Calculus for not 1NF Relational Databases". U. Texas Austin Technical Report (1985).
25. [K1] G.M. Kuper. "Logic Programming with Sets". Proc. 6th ACM PODS, 11-20 (1987).
26. [K2] G.M. Kuper. "On the Expressive Power of Logic Programming Languages with Sets". Proc. 7th ACM PODS, 10-14 (1988).
27. [KV1] G.M. Kuper, M.Y. Vardi. "A New Approach to Database Logic". Proc. 3rd ACM PODS, 86-96 (1984).
28. [KV2] G.M. Kuper, M.Y. Vardi. "On the Complexity of Queries in the Logical Data Model". Proc. 2nd ICDT, 267-280 (1988).
29. [M] A. Makinouchi. "A Consideration on Normal Form of Not Necessarily Normalized Relation in the Relational Data Model". Proc. 3rd VLDB, 447-453 (1977).
30. [PvG] J. Paredaens, D. Van Gucht. "Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions". Proc. 7th ACM PODS, 29-38 (1988).
31. [SS] H. Schek, M. Scholl. "The Relational Model with Relation-valued Attributes". Information Systems (1986).
32. [Sc] M. Scholl, et al. "VERSO: A Database Machine Based on Nested Relations". Nested Relations and Complex Objects, Springer Verlag, S. Abiteboul, P. Fisher, H. Schek eds, 27-49 (1989).
33. [S+] J.T. Schwartz, R.B.K. Dewar, E. Dubinsky, E. Schonberg. Programming with Sets: An Introduction to SETL. Springer-Verlag, New-York (1986).
34. [TF] S. Thomas, P. Fischer. "Nested Relational Structures". Advances in Computing Research, Vol. 3, P. Kanellakis, F. Preparata eds, JAI Press, 269-307 (1986).
35. [V1] M.Y. Vardi. "Review of [J]". Zentralblatt fur Mathematic, 497.68061 (1983).
36. [V2] M.Y. Vardi, "The Complexity of Relational Query Languages". Proc. 14th ACM STOC, 137-146 (1982).

Index Terms

• Information systems

  • Data management systems

    • Database design and models

    • Query languages