Eliezer L. Lozinskii
Abstract
Using a nonprocedural language for query formulation requires certain automatization of a query answering process. Given a query for creation of a new relation, the problem is to find an efficient procedure which produces this relation from a given relational database. We concentrate upon sequences of join operations which losslessly produce a relation required by a query. A new property of such sequences is analyzed which provides a basis for the presented algorithms that construct an efficient join procedure. The algorithms have polynomial complexity. A modified AND/OR graph is used for the display of a given set of dependencies and a collection of relations representing a database.
- 1 AHO, A.V., BEERI, C., AND ULLMAN, J.D. The theory ofjoins in relational data bases. Proc. 18th IEEE Syrup. Foundations of Computer Science, 1977, pp. 495-504.Google Scholar
- 2 ARMSTRONG, W.W. Dependency structures of data base relationships. Information Processing 74, North-Holland, Amsterdam, 1974, pp. 580-583.Google Scholar
- 3 BERNSTEIN, P.A., AND BEERI, C. An algorithmic approach to normalization of relational data base schemes. Tech. Rep. CSRG-73, Computer Systems Research Group, Univ. Toronto, Toronto, Canada, 1976.Google Scholar
- 4 CARLSON, C.R., AND KAPLAN, R.S. A generalized access path model and its application to a relational data base system. Proc. ACM-SIGMOD Int. Conf. Management of Data, June 1976, pp. 143-154. Google ScholarDigital Library
- 5 CHANG, S.K., AND KE, J.S. Database skeleton and its application to fuzzy query translation. IEEE Trans. Software Engineering SE-4, 1 (Jan. 1978), 31-44.Google ScholarDigital Library
- 6 CODD, E.F. A relational model of data for large shared data banks. Comm. ACM 13, 6 (June 1970), 377-387. Google ScholarDigital Library
- 7 CODD, E.F. Further normalization of the data base relational model. In Courant Computer Science Symposium, vol. 6, Data Base Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.Google Scholar
- 8 CODD, E.F. Recent investivations in relational data base systems. Information Processing 74, North-Holland, Amsterdam, 1974, pp. 1017-1021.Google Scholar
- 9 CODD, E.F. Relational completeness of data base sublanguages. In Courant Computer Science Symposium, vol. 6, Data Base Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 65-98.Google Scholar
- 10 DELOBEL, C., AND CASEY, R.G. Decomposition of a data base and the theory of Boolean switching functions. IBM'J. Res. Dev. 17, 5 (Sept. 1973), 374-386.Google ScholarDigital Library
- 11 DIJKSTRA, E.W. A note on two problems in connection with graphs. Numer. Math. 1 {1959), 269-271.Google Scholar
- 12 GHOSH, S.P. Data Base Organization for Data Management. Academic Press, New York, 1977. Google ScholarDigital Library
- 13 GOTLIEB, L.R. Computing joins of relations. Proc ACM-SIGMOD Int. Conf. Management of Data, San Jose, Calif., 1975, pp. 55-63. Google ScholarDigital Library
- 14 HUFFMAN, D.A. A method for the construction of minimum redundancy codes. Proc IRE 40, 10 (Sept. 1952), 1098-1101.Google ScholarCross Ref
- 15 KNUTH, D.E. The Art of Computer Programming, vol. 1. Addison-Wesley, Reading, Mass., 1975, pp. 402-404. Google ScholarDigital Library
- 16 LOZINSKII, E.L. Performance consideration in relational data base design. In Databases: Improving Usability and Responsiveness, B. Shneiderman, Ed. Academic Press, New York, 1978, pp. 272-294.Google Scholar
- 17 NXLSSON, N.J. Problem-Solving Methods in Artificial Intelligence. McGraw-Hill, New York, 1971. Google ScholarDigital Library
- 18 RISSANEN, J. Independent components of relations. ACM Trans. Database Syst. 2, 4 (Dec. 1977), 317-325. Google ScholarDigital Library
- 19 SCHENK, K.L., AND PINKERT, J.R. An algorithm for servicing multirelational queries. Proc. A CM.S{GMOD Int. Conf. Management of Data, Toronto, Canada, 1977, pp. 10-20. Google ScholarDigital Library
- 20 SENKO, M.E. Data structures and data accessing in data base systems: Past, present, future. IBM Syst. J. 16, 3 (1977), 208-257.Google ScholarDigital Library
Index Terms
- Construction of relations in relational databases
Recommendations
The theory of joins in relational databases
Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the join of ...
Query Interoperation Among Object-Oriented and Relational Databases
ICDE '95: Proceedings of the Eleventh International Conference on Data EngineeringWe develop an efficient algorithm for the query interoperation among existing heterogeneous object-oriented and relational databases. Our algorithm utilizes a canonical deductive database as a uniform representation of object-oriented schema and data. ...
Cooperative querying in relational databases
SCCC '97: Proceedings of the 17th International Conference of the Chilean Computer Science SocietyThis paper proposes an architecture for cooperative access to databases, and describes a cooperative interface for querying relational databases (i.e., an interface that assists non-experienced and casual users to get useful answers from a relational ...
Comments