×

Database query languages and functional logic programming. (English) Zbl 1108.68026

Summary: Functional logic programming is a paradigm which integrates functional and logic programming. It is based on the use of rewriting rules for defining programs, and rewriting for goal solving. In this context, goals, usually, consist of equality (and, sometimes, inequality) constraints, which are solved in order to obtain answers, represented by means of substitutions. On the other hand, database programming languages involve a data model, a data definition language and, finally, a query language against the data defined according to the data model. To use functional logic programming as a database programming language, (1) we will propose a data model involving the main features adopted from functional logic programming (for instance, handling of partial and infinite data), (2) we will use conditional rewriting rules as data definition language, and finally, (3) we will deal with equality and inequality constraints as query language. Moreover, as most database systems, (4) we will propose an extended relational calculus and algebra, which can be used as alternative query languages in this framework. Finally, (5) we will prove that three alternative query languages are equivalent.

MSC:

68N17 Logic programming
68N18 Functional programming and lambda calculus
68P15 Database theory
68Q42 Grammars and rewriting systems

Software:

ML; TOY; BABEL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiteboul, S. and Beeri, C., ”The Power of Languages for the Manipulation of Complex Values,”The VLDB Journal, 4, 4, pp. 727–794, 1995. · doi:10.1007/BF01354881
[2] Abiteboul, S., Hull, R. and Vianu, V.,Foundations of Databases, Addison-Wesley, 1995. · Zbl 0848.68031
[3] Almendros-Jiménez, J.M. and Becerra-Terón, A., ”A Framework for Goal-Directed Bottom-Up Evaluation of Functional Logic Programs, inProc. of International Symposium on Functional and Logic Programming, FLOPS, LNCS 2024, pp. 153–169. Springer, 2001. · Zbl 0977.68580
[4] Almendros-Jiménez, J. M. and Becerra-Terón, A., ”A Relational Algebra for Functional Logic Deductive Databases,”Procs. of Perspectives of System Informatics, PSI, LNCS 2890, pp. 494–508, Springer, 2003. · Zbl 1254.68103
[5] Almendros-Jiménez, J.M. and Becerra-Terón, A., ”A Safe Relational Calculus for Functional Logic Deductive Databases, Selected Papers of the International Workshop on functional and (Constraint) Logic Programming,”WFLP, Electronic Notes on Theoretical Computer Science, ENTCS,86,3, 2003. · Zbl 1270.68101
[6] Almendros-Jiménez, J.M., Becerra-Terón, A. and Sánchez-Hernández, J., ”A Computational Model for Functional Logic Deductive Databases,”Proc. of International Conference on Logic Programming, ICLP, LNCS 2237, PP. 331–347, Springer, 2001. · Zbl 1053.68563
[7] Belussi, A., Bertino, E. and Catania, B., ”An Extended Algebra for Constraint Databases,”IEEE Transactions on Knowledge and Data Engineering, TKDE,10,5, 1998. · Zbl 0984.68038
[8] Benedikt, M. and Libkin, L., ”Query Safety with Constraints (chapter),”Constraint Databases, pp. 109–129, Springer, 2000. · Zbl 0989.68045
[9] Buneman, P., Naqvi, S.A., Tannen, V. and Wong, L., ”Principles of Programming with Complex Objects and Collection Types,”Theoretical Computer Science, TCS, 149, 1, pp. 3–48, 1995. · Zbl 0874.68092 · doi:10.1016/0304-3975(95)00024-Q
[10] Chimenti, D., Gamboa, R., Krishnamurthy, R., Naqvi, S.A., Tsur, S. and Zaniolo, C., ”The LDL System Prototype,”IEEE Transactions on Knowledge and Data Engineering, TKDE, 2, 1, pp. 76–90, 1990. · Zbl 05108686 · doi:10.1109/69.50907
[11] Codd, E.F., ”A Relational Model of Data for Large Shared Data Banks,”Communications of the ACM, CACM, 13, 6, pp. 377–387, 1970. · Zbl 0207.18003 · doi:10.1145/362384.362685
[12] González-Moreno, J.C., Hortalá-González, M.T., López-Fraguas, F.J. and Rodríguez-Artalejo, M., ”An Aproach to Declarative Programming Based on a Rewriting Logic,”Journal of Logic Programming JLP, 40, 1, pp. 47–87, 1999. · Zbl 0942.68060 · doi:10.1016/S0743-1066(98)10029-8
[13] Hanus, M., ”The Integration of Functions into Logic Programming: From Theory to Practice,”Journal of Logic Programming, JLP, 19, 20, pp. 583–628, 1994. · Zbl 0942.68526 · doi:10.1016/0743-1066(94)90034-5
[14] Hanus, M., ”Curry: An Integrated Functional Logic Language, Version 0.8,”Technical report, University of Kiel, Germany, 2003.
[15] Hull, R. and Su, J., ”Deductive Query Language for Recursively Typed Complex Objects,”Journal of Logic Programming, JLP, 35, 3, pp. 231–261, 1998. · Zbl 0905.68058 · doi:10.1016/S0743-1066(97)10009-7
[16] Kanellakis, P. and Goldin, D., ”Constraint Query Algebras,”Constraints, 1, 1–2, pp. 45–83, 1996. · Zbl 05475102 · doi:10.1007/BF00143878
[17] Kanellakis, P., Kuper, G. and Revesz, P., ”Constraint Query Languages,”Journal of Computer and System Sciences, JCSS, 51, 1, pp. 26–52, 1995. · Zbl 05478519 · doi:10.1006/jcss.1995.1051
[18] Kuper, G.M., Libkin, L. and Paredaens, J.,Constraint Databases, Springer, 2000. · Zbl 0935.00022
[19] Libkin, L., ”A Semantics-based Approach to Design of Query Languages for Partial Information,”Proc. of Semantics in Databases, LNCS, 1358, pp. 170–208, Springer, 1995. · doi:10.1007/BFb0035009
[20] Liu, M., ”Deductive Database Languages: Problems and Solutions,”ACM Computing Surveys, 31, 1, pp. 27–62, 1999. · doi:10.1145/311531.311533
[21] López-Fraguas, F.J. and Sánchez-Hernández, J., ”TOY: A Multiparadigm Declarative System,”Procs. of Conference on Rewriting Techniques and Applications, RTA, LNCS 1631, pp. 244–247, Springer, 1999.
[22] López-Fraguas, F.J. and Sánchez-Hernández, J., ”Proving Failure in Functional Logic Programs,”Proc. of the International Conference on Computational Logic, CL, LNCS 1861, pp. 179–193, Springer, 2000. · Zbl 0983.68503
[23] López-Fraguas, F.J. and Sánchez-Hernández, J., ”A Proof Theoretic Approach to Failure in Functional, Logic Programming,”Theory and Practice of Logic Programming, TPLP, 4, 1–2, pp. 41–74, 2004. · Zbl 1085.68021 · doi:10.1017/S1471068403001728
[24] Milner, R., Tofte, M. and Harper, R.,The Definition of Standard ML, MIT Press, 1990.
[25] Moreno-Navarro, J.J. and Rodríguez-Artalejo, M., ”Logic Programming with Functions and Predicates: The Language BABEL,”Journal of Logic Programming, JLP, 12, 3, pp. 191–223, 1992. · Zbl 0754.68031 · doi:10.1016/0743-1066(92)90024-W
[26] Paton, N., Cooper, R., Williams, H. and Trinder, P.,Database Programming Languages, C.A.R. Hoare Series, Prentice Hall, 1996. · Zbl 0836.68024
[27] Poulovassilis, A., ”FDL: An Integration of the Functional Data Model and the Functional Computation Model,”Proc. of the British National Conference on Databases, BNCOD, pp. 215–236, Cambridge University Press, 1988.
[28] Poulovassilis, A., ”The Implementation of FDL, a Functional Database Language,”The Computer Journal 35, 2, pp. 119–128, 1992. · Zbl 0757.68024 · doi:10.1093/comjnl/35.2.119
[29] Poulovassilis, A. and King, P., ”Extending the Functional Data Model to Computational Completeness,”Proc. of International Conference on Extending Database Technology, EDBT, LNCS 416, pp. 75–91, 1990.
[30] Poulovassilis, A. and Small, C., ”A Functional Programming Approach to Deductive Databases,”Proc. of Very Large Data Bases Conference, VLDB, pp. 491–500, Morgan Kaufmann, 1991.
[31] Ramakrishnan, R., Srivastava, D., Sudarshan, S. and Seshadri, P., ”Implementation of the CORAL Deductive Database System,”Proc. of the ACM SIGMOD International Conference on Management of Data (Eds. Buneman, P. and Jajodia, S.), pp. 167–176, ACM Press, 1993.
[32] Revesz, P.Z., ”Safe Datalog, Queries with Linear Constraints,”Proc. of International Conferente on Principles and Practice of Constraint Programming, CP, LNCS 1520, pp. 355–369, Springer, 1998.
[33] Revesz, P.Z., ”Safe Query Languages for Constraint Databases,”ACM Transactions on Database Systems TODS, 23, 1, pp. 58–99, 1998. · doi:10.1145/288086.288088
[34] Rigaux, P., Scholl, M., Segoufin, L. and Grumbach, S., ”Building a Constraint-based Spatial Database System: Model, Languages, and Implementation,”Information Systems, 28, 6, pp. 563–595, 2003. · Zbl 1056.68072 · doi:10.1016/S0306-4379(02)00041-8
[35] Shipman, D.W., ”The Functional Data Model and the Data Language DAPLEX,”ACM Transactions on Database Systems, TODS, 6, 1, pp. 140–173, 1981. · doi:10.1145/319540.319561
[36] Shmueli, O., Tsur, S. and Zaniolo, C., ”Compilation of Set Terms in the Logic Data Language (LDL),”Journal of Logic Programming, JLP, 12, 1–2, pp. 89–110, 1992. · Zbl 0763.68026 · doi:10.1016/0743-1066(92)90040-A
[37] Small, C. and Poulovassilis, A., ”An Overview of PFL,”Proc. of International Workshop on Database Programming Languages, DBPL, pp. 96–110, Morgan Kaufmann, 1991.
[38] Trinder, P.W., ”Comprehensions, A Query Notation for DBPL,”Proc. of International Workshop on Database Programming Languages, DBPL, pp. 55–68, Morgan Kaufman, 1991.
[39] Vaghani, J., Ramamohanarao, K., Kemp, D.B., Somogyi, Z., Stuckey, P.J., Leask, T.S. and Harland, J., ”The Aditi Deductive Database System,”The VLDB Journal, 3, 2, pp. 245–288, 1994. · doi:10.1007/BF01228882
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.