Query processing strategies in the PASCAL/R relational database management system

ABSTRACT

In the database language PASCAL/R, the programming language PASCAL and concepts based on the relational data model are integrated. The paper investigates transformation strategies used in the PASCAL/R system to evaluate queries with existential and universal quantifiers. Intermediate data structures are described using a high-level language tool called a reference to a selected variable. The predicate calculus approach used in PASCAL/R offers new insight into recently proposed query optimization techniques and allows some of them to be extended.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 3: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 4: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 5: E.F.Codd: Relational Completeness of Data Base Sublanguages, Courant Computer Science Symposium, New York 1971, 65--98
• 6: Leo R. Gotlieb, Computing joins of relations, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500089]
• 7: M.Jarke: Entwurf und Implementation von Algorithmen zur Behandlung von Anfragen an relationale Datenbanken, unpubl. diploma thesis, Hamburg 1978 (in German)
• 8: M.Jarke, J.W.Schmidt: Evaluation of First-Order Relational Expressions, IFI-HH-B-78/81, Hamburg 1981
• 9: Won Kim, A new way to compute the product and join of relations, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582278]
• 10: W.Kim: Query Optimization for Relational Databases, IBM RJ3081, San Jose 1981
• 11: F.P.Palermo: A Database Search Problem, 4th Computer and Information Science Symposium, Miami Beach 1972, 67--101
• 12: W.V.O.Quine: Mathematical Logic, 5th ed., Cambridge/Mass. 1965
• 13: A.Schmidt: Ueber deduktive Theorien mit mehreren Sorten von Grunddingen, Mathematische Annalen 115 (1938), 485--506 (in German)
• 14: Joachim W. Schmidt, Some high level language constructs for data of type relation, ACM Transactions on Database Systems (TODS), v.2 n.3, p.247-261, Sept. 1977 [doi>10.1145/320557.320568]
• 15: J.W.Schmidt: Parallel Processing of Relations: A Single-Assignment Approach, Proc. 5th VLDB, Rio de Janeiro 1979
• 16: J.W.Schmidt: Generalized Selection Mechanisms for Relations (forthcoming)
• 17: J.W.Schmidt, M.Mall: PASCAL/R Report, IFI-HH-B-72/81, Hamburg 1981
• 18: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 19: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]