Concepts for a database system compiler

ABSTRACT

We propose a very simple formalism based on parameterized types and a rule-based algebra to explain the storage structures and algorithms of database management systems. Implementations of DBMSs are expressed as equations If all functions referenced in the equations have been implemented the software for a DBMS can be synthesized in minutes at little cost, in contrast to current methods where man-years of effort and hundreds of thousands of dollars are required. Our research aims to develop a DBMS counterpart to today's compiler-complier technologies

REFERENCES

• Ast76: 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]
• Bat82: D. S. Batory , C. C. Gotlieb, A unifying model of physical databases, ACM Transactions on Database Systems (TODS), v.7 n.4, p.509-539, Dec. 1982 [doi>10.1145/319758.319760]
• Bat83: Don S. Batory, Index coding: a compression technique for large statistical databases, Proceedings of the 2nd international workshop on Proceedings of the Second International Workshop on Statistical Database Management, p.306-314, September 27-29, 1983, Los Altos, California
• Bat84: D. S. Batory, Conceptual-to-internal mappings in commercial database systems, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588023]
• Bat85: D. S. Batory, Modeling the storage architectures of commercial database systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.463-528, Dec. 1985 [doi>10.1145/4879.5392]
• Bat86a: D. S. Batory , J. R. Barnett , J. F. Garza , K. P. Smith , K. Tsukuda , C. Twichell , T. E. Wise, GENESIS: An Extensible Database Management System, IEEE Transactions on Software Engineering, v.14 n.11, p.1711-1730, November 1988 [doi>10.1109/32.9057]
• Bat86b: Don S. Batory , T. Y. Leung, Implementation Concepts for an Extensible Data Model and Data Language, University of Texas at Austin, Austin, TX, 1986
• Bat87a: Don S. Batory, A Molecular Database Systems Technology, University of Texas at Austin, Austin, TX, 1987
• Bat87b: D S Batory, 'Principles of Database Management System Extenslblhty', m {IEE87}, 40-46
• Bat87c: D S Batory, 'Extenslble Cost Models and Query Opttmlzaaon m GENESIS', to appear m IEEE Database Engineering, 1987
• Bat88: D. S. Batory, On the reusability of query optimization algorithms, Information Sciences: an International Journal, v.49 n.1-3, p.177-202, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90027-3]
• Ber81a: 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]
• Ber81b: 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]
• Cha76: D D Chamberlm, et al, 'SEQUEL 2 A Umfied Approach to Data Definmon, MampulaUon, and Control', IBM Jour Res and Dev, 20,6 (Nov 1976), 560 575
• Dat82: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Egg81: S Eggers, F Olken, and A Shosham, 'A Compressmn Techtuque for Large Stattsttcal Databases', Proc VLDB, (1981) 424-434
• Fre87: Johann Christoph Freytag, A rule-based view of query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.173-180, May 27-29, 1987, San Francisco, California, United States
• Gra87: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• Gog84: J Goguen, 'Parametenzed Programming', IEEE Trans Softwai e Engr, SE-10,5 (September 1984), 528-543
• Gut77: John Guttag, Abstract data types and the development of data structures, Communications of the ACM, v.20 n.6, p.396-404, June 1977 [doi>10.1145/359605.359618]
• IEE84: Database Engmeermg, Slansacal Database Systems, 7,1 (March 84), D S Batory, ed
• IEE87: Database Engineering, 10,2 (June 1987), M Carey, ed
• Lis77: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• Olk86: Frank Olken , Doron Rotem, Simple Random Sampling from Relational Databases, Proceedings of the 12th International Conference on Very Large Data Bases, p.160-169, August 25-28, 1986
• Sel79: 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]
• Sho85: Arie Shoshani , Harry K. T. Wong, Statistical and scientific database issues, IEEE Transactions on Software Engineering, v.11 n.10, p.1040-1047, Oct. 1985 [doi>10.1109/TSE.1985.231851]
• Sto76: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• Tur79: M J Turner, R Hammond, and P Cotton, 'A DBMS for Large Stattsttcal Databases', VLDB 1979, 319-327
• Val87: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]
• Won76: 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]
• Won86: H.K.T Wong, J~Z. Lt, F Olken, D Rotem, and L Wong, 'Bit T~Uon for Very Large Scsemsfic and Stattshcal Databases', Algorithmlca, 1 (1986), 289-309
• Yu84a: Clement T. Yu , Z. Meral Ozsoyoglu , K. Lam, Optimization of distributed tree queries, Journal of Computer and System Sciences, v.29 n.3, p.409-445, Dec. 1984 [doi>10.1016/0022-0000(84)90007-2]
• Yu84b: C. T. Yu , C. C. Chang, Distributed query processing, ACM Computing Surveys (CSUR), v.16 n.4, p.399-433, Dec. 1984 [doi>10.1145/3872.3874]
• Zan83: Carlo Zaniolo, The database language GEM, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California