David Maier
Moshe Y. Vardi
Abstract
The universal relation model aims at achieving complete access-path independence in relational databases by relieving the user of the need for logical navigation among relations. We clarify the assumptions underlying it and explore the approaches suggested for implementing it.
The essential idea of the universal relation model is that access paths are embedded in attribute names. Thus attribute names must play unique “roles.” Furthermore, it assumes that for every set of attributes there is a basic relationship that the user has in mind. The user's queries refer to these basic relationships rather than to the underlying database.
Two fundamentally different approaches to the universal relation model have been taken. According to the first approach, the user's view of the database is a universal relation or many universal relations, about which the user poses queries. The second approach sees the model as having query-processing capabilities that relieve the user of the need to specify the logical access path. Thus, while the first approach gives a denotational semantics to query answering, the second approach gives it an operational semantics. We investigate the relationship between these two approaches.
- 1 AHO, A.V. Private communication.Google Scholar
- 2 AHo, A.V., BEEm, C., AND ULLMAN, J.D. The theory of joins in relational databases. ACM Trans. Database Syst. 4 (1979), 297-314. Google ScholarDigital Library
- 3 AHO, A.V., SAGIV, Y., AND ULLMAN, J.D. Equivalence of relational expressions. SIAM J. Comput. 8, 2 (1979), 218-246. See also, Efficient optimization of a class of relational expressions. ACM Trans. Database S;yst. 4 (1979), 435-454. Google ScholarDigital Library
- 4 ARAZ}-GONCZAROWSKI, Z. A high-level interface for naive users in a relational database. Report, Dept. of Computer Science, Hebrew Univ., Jerusalem, 1981.Google Scholar
- 5 ATZENI, P., AND PARKER, D.S. Assumptions in relational database theory. In Proceedings ACM Symposium on Principles o/Database Systems (Los Angeles, Mar. 29-31, 1982), ACM, New York, 1-9. Google ScholarDigital Library
- 6 BABB, B. Joined normal form: A storage encoding for relational databases. ACM Trans. Database Syst. 7 (1982), 588-614. Google ScholarDigital Library
- 7 BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. In Proceedings International Conference on Very Large Data Bases (1978), 113-124.Google Scholar
- 8 BEErtI, C., AND R}SSANEN, J. Faithful representation on relational database schemes. IBM Res. Rep., IBM Research Laboratory, San Jose, Calif., 1980.Google Scholar
- 9 BEERX, C., AND VARDI, M.Y. A proof procedure for data dependencies. Teeh. Rep., Hebrew Univ., Jerusalem, 1980. Also, J. ACM, to appear. Google ScholarDigital Library
- 10 BERNSTEIN, P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. 1 (1976), 277-298. Google ScholarDigital Library
- 11 CARLSON, C.R., AND KAPLAN, R.S. A generalized access path model and its application to a relational database system. In Proceedings A CM SIGMOD International Symposium on Management o{ Data (1976), ACM, New York, 143-154. Google Scholar
- 12 CODD, E.F. A relational model for large shared data banks. Commun. ACM 13, 6 (June 1970), 377-387. Google ScholarDigital Library
- 13 CODD, E.F. Relational databases: A practical foundation for productivity. Comrnun. ACM 25, 2 (Feb. 1982), 109-117. Google ScholarDigital Library
- 14 CODD, E.F., ARNOLD, R.S., CADIOU, J.M., CHANG, C.L., AND ROUSSOPOULOS, N. Rendezvous version I: An experimental English language query formulation system for casual users of relational databases. RJ2144, IBM, San Jose, Calif., 1978.Google Scholar
- 15 FAGIN, R. Horn clauses and database dependencies. J. ACM 29 (1982), 952-983. Google ScholarDigital Library
- 16 FAGIN, R., MENDELZON, A.O., AND ULLMAN, J.D. A simplified universal relation assumption and its properties. ACM Trans. Database Syst. 7 (1982), 343-360. Google ScholarDigital Library
- 17 GALLAIRE, H., AND MINKER, J. (Eds.) Logic and Data Bases. Plenum Press, New York, 1978. Google ScholarDigital Library
- 18 GRAHAM, M.H., AND MENDELZON, A.O. Notions of dependency satisfaction. In Proceedings ACM Symposium on Principles of Database Systems (Los Angeles, Mar. 29-31, 1982), ACM, New York, 177-188. Google ScholarDigital Library
- 19 GRAHAM, M., AND VARDI, M.Y. On the complexity and axiomatizability of consistent database states. In Proceedings Symposium on Principles of Database Systems (Waterloo, 1984), ACM, New York, 281-289. Google ScholarDigital Library
- 20 HONEYMAN, P. Testing satisfaction of functional dependencies. J. ACM, 29 (1982), 668-677. Google ScholarDigital Library
- 21 HONEYMAN, P., LADNER, R.E., AND YANNAKAKIS, M. Testing the universal instance assumption. Inf. Process. Lett. 10, 1 (1980), 14-19.Google ScholarCross Ref
- 22 IMIELINSKI, T., AND LIPSKI, W. On representing incomplete information in a relational database. In Proceedings International Conference on Very Large Data Bases (1981), 388-397.Google Scholar
- 23 KENT, W. Consequences of assuming a universal relation. ACM Trans. Database Syst. 6 (1981), 539-556. Google ScholarDigital Library
- 24 KORTH, H.F., KUPER, G.M., AND ULLMAN, J.D. System/U: A database system based on the universal relation assumption. Res. Rep. STAN-CS-82-944, Stanford Univ., Jan. 1983.Google Scholar
- 25 KOWALSKI, R. Logic as a database language. Report, Dept. of Computing, Imperial College, London, 1981.Google Scholar
- 26 KUCK, S.M., AND SAGIV, Y. A universal relation database system implemented via the network model. In Proceedings ACM Symposium on Principles of Database Systems (Los Angeles, Mar. 29-31, 1982), ACM, New York, 147-157. Google ScholarDigital Library
- 27 LOZINSKI, E.L. Construction of relations in relational databases. ACM Trans. Database Syst. 5 (1980), 208-224. Google ScholarDigital Library
- 28 MAIER, D. The Theory o{ Relational Databases. Computer Science Press, Rockville, Md., 1983. Google ScholarDigital Library
- 29 MAIER, D. Discarding the universal instance assumption. In Proceedings XP/I Workshop (Stony Brook, N.Y., June, 1980).Google Scholar
- 30 MAIER, D., MENDELZON, A.O., SADRI, F., AND ULLMAN, J.D. Adequacy of decompositions in relational databases. J. Cornput. Syst. Sci. 21, 3 (1980), 368-380.Google ScholarCross Ref
- 31 MAIER, D., }V{ENDELZON, A.O., AND SAGIV, Y. Testing implications of data dependencies. ACM Trans. Database Syst. 4 (1979), 455-469. Google ScholarDigital Library
- 32 MAIER, D., ROZENSHTEIN, D., AND WARREN, D.S. Windows on the world. In Proceedings ACM SIGMOD International Symposium on Management of Data (San Jose, Calif, May 23-26, 1983), ACM, New York, 68-78. Google ScholarDigital Library
- 33 MAIER, D., ROZENSHTEIN, D., SALVETER, S., STEIN, J., AND WARREN, D.S. Toward logical data independence: A relational query language without relations. In Proceedings ACM SIGMOD International Symposium on Management of Data (Orlando, Fla., June 2-4, 1982), ACM, New York, 51-60. Google ScholarDigital Library
- 34 MAIER, D., AND ULLMAN, J.D. Maximal objects and the semantics of universal relation databases. ACM Trans. Database Syst., 8, 1 (1983), 1-14. Google ScholarDigital Library
- 35 MAIER, D., ULLMAN, J.D., AND VARDX, M.Y. Beyond representative instances. Manuscript, in preparation, Stanford Univ., Stanford, Calif.Google Scholar
- 36 MAIER, D., AND WARREN, D.S. Specifying connections for a universal relation scheme database. In Proceedings ACM SIGMOD International Symposium on Management of Data (Orlando, Fla., June 2-4, 1982), ACM, New York, 1-7. Google ScholarDigital Library
- 37 MENDELZON, A.O. Database states and their tableaux. Proc. XP2 Workshop (State College, Pa., June, 1981). See also, this issue, 264-282. Google ScholarDigital Library
- 38 NICOLAS, J.M. First-order logic formalization for functional, multivalued, and mutual dependencies. In Proceedings A CM SIGMOD International Symposium on Management of Data (Austin, Tex., May 31, June 1-2, 1978), ACM, New York, 40-46. Google ScholarDigital Library
- 39 OSBORN, S.L. Towards a universal relation interface. In Proceedings International Conference on Very Large Data Bases (1979), 52-60.Google ScholarCross Ref
- 40 REITER, R. Towards a logical reconstruction of relational database theory. Report, Dept. of Computer Science, Univ. of British Columbia, 1981. Also in On Conceptual Modelling: Perspectives from Artificial Intelligence, Databases, and Programming Languages. M. L. Brodie, J. Mylopoulous, and J. Schmidt, Eds., Springer Verlag, 1984, 191-233.Google Scholar
- 41 RISSANEN, J. independent components of relations. ACM Trans. Database Syst. 2 (1977), 317- 325. Google ScholarDigital Library
- 42 SADRI, F., AND ULLMAN, J.D. Template dependencies: A large class of dependencies in relational databases and its complete axiomatization. J. ACM 29, 2 (1982), 363-372. Google ScholarDigital Library
- 43 SAGIV, Y. Can we use the universal instance assumption without using nulls? In Proceedings ACM SIGMOD International Symposium on Management o{ Data (Ann Arbor, Mich., April 29-May 1, 1981), ACM, New York, 108-120. Google ScholarDigital Library
- 44 SAGIV, Y. A characterization of globally consistent databases and their correct access paths. ACM Trans. Database Syst. 8 (1983), 266-286. Google ScholarDigital Library
- 45 SCHENK, K.L., AND PINKERT, J.R. An algorithm for servicing multirelational queries. In Proceedings A CM SIGMOD International Symposium on Management of Data (Toronto, Aug. 3-5, 1977), ACM, New York, 10-19. Google ScholarDigital Library
- 46 ULLMAN, J.D. Principles of Database Systems. Computer Science Press, Potomac, Md., 1983. Google ScholarDigital Library
- 47 ULLMAN, J.D. The U.R. strikes back. In Proceedings ACM Symposium on Principles of Database Systems (Los Angeles, Mar 29-31, 1982), ACM, New York, 10-22 Google ScholarDigital Library
- 48 ULLMAN, J.D. Universal relation interface for database systems. In Proceedings IFIP 1983, R.E.A. Mason, Ed., North-Holland, 243-252.Google Scholar
- 49 VARDI, M.Y. On decomposition of relational databases. In Proceedings IEEE 23rd Annual Symposium on Foundations of Computer Science (Nov. 1982), IEEE, New York, 176-183.Google ScholarDigital Library
- 50 VARm, M.Y. Axiomatization of functional and join dependencies in the relational model. M. Sc. Thesis, Dept. of Applied Math., Weizmann Institute of Science, Rehovot, Israel, 1980.Google Scholar
- 51 YANNAKAKIS, M. Algorithms for acyclic database schemes. In Proceedings International Conference on Very Large Data Bases {1981), 82-94.Google Scholar
- 52 YANNAKAKIS, M., AND PAPADIMITRIOU, C.H. Algebraic dependencies. J. Comput. Syst. Sci. 25 (1982), 2-41.Google ScholarCross Ref
Index Terms
- On the foundations of the universal relation model
Recommendations
Consequences of assuming a universal relation
Although central to the current direction of dependency theory, the assumption of a universal relation is incompatible with some aspects of relational database theory and practice. Furthermore, the universal relation is itself ill defined in some ...
A Universal Relation Data Model with Semantic Abstractions
Two important features of modern database models are support for complex data structures and support for high-level data retrieval and update. The first issue has been studied by the development of various semantic data models; the second issue has been ...
The nested universal relation data model
The nested universal relation (UR) model aims to provide logical data independence to the nested relational model by allowing users to view the database as if it were composed of a single nested relation. Moreover, non-technical users may find the ...
Reviews
Donald W Dearholt
This paper is likely to be most appreciated by the hardcore relational database addict, one who already has a firm grasp of the technical foundations of such systems and of some of the major issues at this stage of their development. The purpose of the paper is to illuminate the universal relation concepts which have been advanced. The authors begin with a discussion of the fundamental assumptions associated with the universal relation concepts; this is well done. They distinguish between two different approaches to the universal relation model: the first approach sees the universal relation as a user view, to be queried by the user; the second approach sees the model as having a query-processing ability that enables the user to pose queries about the actual database relations (without specifying an access path) rather than some abstract universal relation. The authors claim that the main technical contribution of the paper is an exploration of the relationships between these two basic approaches. There is an appropriate discussion of the semantic problems associated with the universal relation (in either version). There is also a brief reference to the computational complexity of testing whether or not a database satisfies the pure universal relation assumption (probably exponential). Then there is a discussion of the weak universal relation approach, setting the stage for the major contributions of the paper. The authors chose several good examples to clarify material which would otherwise be quite obtuse, and the theorems which accompany the discussion are made clearer because of them. Computational definitions of the universal relation are discussed quite thoroughly (in Section 4), and, again, the choice of several suitable examples is of considerable aid. The examples presume, however, a fairly sophisticated understanding of relational database theory. If you, gentle reader, wish to consume this exotica without yet having obtained this level of sophistication, one of the better ways to do so would be to first devour a fair portion of Ullman's book [1]. The paper continues with discussions of lossless tableau mappings and representative instances and applications of their theory to the issues of optimizing queries and storing information about connections. The results on query optimization and the containment property of connections are the principal results of the paper. Having explored three overlapping classes of expressions as possible computation methods which could be used to simulate the effect of the representative instance, the authors also point out three shortcomings of their theory in the last section of the paper. Perhaps, surprisingly, they doubt that the representative instance approach will serve as the “ultimate” universal relation model, primarily because of the lack of adequate semantic support. But, of course, a sequel paper of sufficient scope (and a sequel is promised by the authors) could, when forthcoming, deal with these shortcomings, and perhaps solve even the semantics problem.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments