Construction of relations in relational databases
- 1 June 1980
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 5 (2) , 208-224
- https://doi.org/10.1145/320141.320155
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.Keywords
This publication has 10 references indexed in Scilit:
- Database Skeleton and Its Application to Fuzzy Query TranslationIEEE Transactions on Software Engineering, 1978
- Independent components of relationsACM Transactions on Database Systems, 1977
- An algorithm for servicing multi-relational queriesPublished by Association for Computing Machinery (ACM) ,1977
- Data structures and data accessing in data base systems past, present, futureIBM Systems Journal, 1977
- A generalized access path model and its application to a relational data base systemPublished by Association for Computing Machinery (ACM) ,1976
- Computing joins of relationsPublished by Association for Computing Machinery (ACM) ,1975
- Decomposition of a Data Base and the Theory of Boolean Switching FunctionsIBM Journal of Research and Development, 1973
- A relational model of data for large shared data banksCommunications of the ACM, 1970
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952