The functional guts of the Kleisli query system

ABSTRACT

Kleisli is a modern data integration system that has made a significant impact on bioinformatics data integration. The primary query language provided by Kleisli is called CPL, which is a functional query language whose surface syntax is based on the comprehension syntax. Kleisli is itself implemented using the functional language SML. This paper describes the influence of functional programming research that benefits the Kleisli system, especially the less obvious ones at the implementation level.

REFERENCES

• 1: S. F. Altschul and W. Gish. Local alignment statistics. Methods Enzymology, 266:460-480, 1996.
• 2: S. F. Altschul et. al. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. NAR, 25(17):3389-3402, 1997.
• 3: P. G. Baker and A. Brass. Recent development in biological sequence databases. Curr. Op. Biotech., 9:54-58, 1998.
• 4: Patricia G. Baker , Andy Brass , Sean Bechhofer , Carole A. Goble , Norman W. Paton , Robert Stevens, TAMBIS: Transparent Access to Multiple Bioinformatics Information Sources, Proceedings of the 6th International Conference on Intelligent Systems for Molecular Biology, p.25-34, July 01, 1998
• 5: D. Benton. Bioinformatics | principles and potential of a new multidisciplinary tool. TIBTECH, 14:261-272, 1996.
• 6: Val Breazu-Tannen , Peter Buneman , Shamim Naqvi, Structural recursion as a query language, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.9-19, April 1992, Nafplion, Greece
• 7: Val Tannen , Ramesh Subrahmanyam, Logical and Computational Aspects of Programming with Sets/Bags/Lists, Proceedings of the 18th International Colloquium on Automata, Languages and Programming, p.60-75, July 08-12, 1991
• 8: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 9: C. Burks et. al. GenBank. NAR, 20 Supplement:2065-9, 1992.
• 10: R. G. G. Cattell, editor. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1996.
• 11: J. Chen et. al. Using Kleisli to bring out features in BLASTP results. Genome Informatics, 9:102-111, 1998.
• 12: Jing Chen , Limsoon Wong , Louxin Zhang, A protein patent query system powered by Kleisli, ACM SIGMOD Record, v.27 n.2, p.593-595, June 1998
• 13: 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]
• 14: S. Davidson et. al. BioKleisli: A digital library for biomedical researchers. Int. J. Digital Libraries, 1(1):36-53, 1997.
• 15: Guozhu Dong , Leonid Libkin , Limsoon Wong, Local Properties of Query Languages, Proceedings of the 6th International Conference on Database Theory, p.140-154, January 08-10, 1997
• 16: Allen Goldberg , Robert Paige, Stream processing, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.53-62, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802021]
• 17: ISO. Standard 8824. Information Processing Systems. Open Systems Interconnection. Speci~cation of Abstraction Syntax Notation One (ASN.1), 1987.
• 18: Leonid Libkin , Limsoon Wong, Query languages for bags and aggregate functions, Journal of Computer and System Sciences, v.55 n.2, p.241-272, Oct. 1997 [doi>10.1006/jcss.1997.1523]
• 19: Witold Litwin , Leo Mark , Nick Roussopoulos, Interoperability of multiple autonomous databases, ACM Computing Surveys (CSUR), v.22 n.3, p.267-293, Sept. 1990 [doi>10.1145/96602.96608]
• 20: National Center for Biotechnology Information, National Library of Medicine, Bethesda, MD. NCBI ASN.1 Specification, 1992. Revision 2.0.
• 21: Atsushi Ohori , Peter Buneman , Val Breazu-Tannen, Database programming in Machiavelli—a polymorphic language with static type inference, ACM SIGMOD Record, v.18 n.2, p.46-57, June 1989
• 22: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 23: L. C. Paulson. A higher-order implementation of rewriting. Sci. Comput. Prog., 3:119-49, 1983.
• 24: P. Pearson et. al. The GDB human genome data base anno 1992. NAR, 20:2201-2206, 1992.
• 25: D. Rémy, Type checking records and variants in a natural extension of ML, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.77-88, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75284]
• 26: D. Remy. E~cient representation of extensible records. In Proc. of ACM SIGPLAN Workshop on ML and its Applications, pages 12-16, 1992.
• 27: C. Schoenbach et. al. FIMM, a database of functional molecular immunology. NAR, 28(1):222-224, 2000.
• 28: G. D. Schuler et. al. Entrez: Molecular biology database and retrieval system. Methods Enzymology, 266:141-162, 1996.
• 29: M. Spivey, A functional theory of exceptions, Science of Computer Programming, v.14 n.1, p.25-42, Jun. 1990 [doi>10.1016/0167-6423(90)90056-J]
• 30: Dan Suciu, Bounded fixpoints for complex objects, Theoretical Computer Science, v.176 n.1-2, p.283-328, April 20, 1997 [doi>10.1016/S0304-3975(96)00293-9]
• 31: Dan Suciu , Limsoon Wong, On Two Forms of Structural Recursion, Proceedings of the 5th International Conference on Database Theory, p.111-124, January 11-13, 1995
• 32: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 33: P. Wadler. Comprehending monads. Math. Struct. Comput. Sci., 2:461-493, 1992.
• 34: S. Walsh et. al. ACEDB: A database for genome information. Methods Biochem. Anal., 39:299-318, 1998.
• 35: Limsoon Wong , Peter Buneman, Querying nested collections, 1994
• 36: Limsoon Wong, An introduction to Remy's fast polymorphic record projection, ACM SIGMOD Record, v.24 n.3, p.34-39, Sept. 1995 [doi>10.1145/211990.212013]
• 37: Limsoon Wong, Kleisli, a functional query system, Journal of Functional Programming, v.10 n.1, p.19-56, January 2000 [doi>10.1017/S0956796899003585]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Languages, Management, Performance, Theory