Design and implementation of the glue-nail database system

ABSTRACT

We describe the design and implementation of the Glue-Nail database system. The Nail language is a purely declarative query language; Glue is a procedural language used for non-query activities. The two languages combined are sufficient to write a complete application. Nail and Glue code both compile into the target language IGlue. The Nail compiler uses variants of the magic sets algorithm, and supports well-founded models. Static optimization is performed by the Glue compiler using techniques that include peephole methods and data flow analysis. The IGlue code is executed by the IGlue interpreter, which features a run-time adaptive optimizer. The three optimizers each deal with separate optimization domains, and experiments indicate that an effective synergism is achieved. The Glue-Nail system is largely complete and has been tested using a suite of representative applications.

REFERENCES

• 1: Robert Alverson , Tom Blank , Kiyoung Choi , Sun Y Hwang , Arturo Salz , Larry Soule , Thomas Rokicki, Thor user''s manual: tutorial and commands, Stanford University, Stanford, CA, 1988
• 2: Francois Bancilhon, Naive evaluation of recursively defined relations, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• 3: W. Chen, M. Kifer, and D. S. Warren. HiLog: A first-order semantics of higher-order logic programming constructs. In Logic Programming: Proceedings o} North American Conlerence, pages 1090-1114, 1989.
• 4: Marcia A. Derr, Adaptive optimization in a database programming language, Stanford University, Stanford, CA, 1993
• 5: Michael Freeston, The BANG file: A new kind of grid file, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.260-269, May 27-29, 1987, San Francisco, California, United States
• 6: 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]
• 7: David B. Kemp , Kotagiri Ramamohanarao , Zoltan Somogyi, Right-, left-, and multi-linear rule transformations that maintain context information, Proceedings of the sixteenth international conference on Very large databases, p.380-391, September 1990, Brisbane, Australia
• 8: D. B. Kemp, P. J. Stuckey, and D. Srivastava. Query restricted bottom-up evaluation of well-founded models. In Proceedings of the 1992 Joint Conference and Symposium on Logic Programming, Washington DC, 1992.
• 9: J.-M. Kerisit and 3.-M. Pugin. Efficient query answering on stratified databases. In Proceedings of International Conference on F#fth Generation Computer Systems, pages 719-726, 1988.
• 10: Shinichi Morishita, An alternating fixpoint tailored to magic programs, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.123-134, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153861]
• 11: K. Morris, J. F. Naughton, Y. Saraiya, J. D. Unman, and A. Van Calder. YAWN! (Yet Another Window on NAIL!). Data Engineering, 10(4):28-43, 1987.
• 12: Katherine Morris , Jeffrey D Ullman , Allen Van Gelder, Design overview of the NAIL] system, Proceedings on Third international conference on logic programming, p.554-568, September 1986, London, United Kingdom
• 13: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 14: Geoffrey Robert Phipps, Glue: a deductive database programming language, Stanford University, Stanford, CA, 1992
• 15: Geoffrey Phipps , Marcia A. Derr , Kenneth A. Ross, Glue-Nail: a deductive database system, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.308-317, May 29-31, 1991, Denver, Colorado, United States
• 16: Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan, CORAL - Control, Relations and Logic, Proceedings of the 18th International Conference on Very Large Data Bases, p.238-250, August 23-27, 1992
• 17: Kenneth A. Ross, Modular stratification and magic sets for DATALOG programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298558]
• 18: J.A. Thom and J. Zobel. Nu-Prolog Reference Manual, version 1.5.24. Technical Report 86/10, Department of Computer Science, University of Melbourne, 1990.
• 19: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 20: J. Vaghani, K. Ramamohanarao, D. B. Kemp, Z. Somogyi, and P. J. Stuckey. The Aditi deductive database system. In J. Chomicki, editor, Proceedings of the NACLP'90 Workshop on Deductive Databases. Kansas State University Technical Report TR-CS-90-14, 1990.
• 21: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]
• 22: L. Vielle. Recursive axioms in deductive databases: The query/sub-query approach. In L. Kerschberg, editor, Expert Database Systems. The Benjamin/Cummings Publishing Company, 1987.
• 23: L. Vielle, P. Bayer, V. Kiichenhoff, and A. Lefebvre. EKS-V1, a short overview. In AAA1 Workshop on Knowledge Base Management Systems, Boston, USA, 1990.
• 24: Kyu-Young Whang , Ravi Krishnamurthy, Query optimization in a memory-resident domain relational calculus database system, ACM Transactions on Database Systems (TODS), v.15 n.1, p.67-95, March 1990 [doi>10.1145/77643.77646]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Design, Experimentation, Languages