Principles of programming with complex objects and collection types.

*(English)*Zbl 0874.68092Summary: We present a new principle for the development of database query languages that the primitive operations should be organized around types. Viewing a relational database as consisting of sets of records, this principle dictates that we should investigate separately operations for records and sets. There are two immediate advantages of this approach, which is partly inspired by basic ideas from category theory. First, it provides a language for structures in which record and set types may be freely combined: nested relations or complex objects. Second, the fundamental operations for sets are closely related to those for other “collection types” such as bags or lists, and this suggests how database languages may be uniformly extended to these new types. The most general operation on sets, that of structural recursion, is one in which not all programs are well-defined. In looking for limited forms of this operation that always give rise to well-defined operations, we find a number of close connections with existing database languages, notably those developed for complex objects. Moreover, even though the general paradigm of structural recursion is shown to be no more expressive than one of the existing languages for complex objects, it possesses certain properties of uniformity that make it a better candidate for an efficient, practical language. Thus rather than developing query languages by extending, for example, relational calculus, we advocate a very powerful paradigm in which a number of well-known languages are to be found as natural sublanguages.

##### MSC:

68P15 | Database theory |

##### Keywords:

database query languages
PDF
BibTeX
XML
Cite

\textit{P. Buneman} et al., Theor. Comput. Sci. 149, No. 1, 3--48 (1995; Zbl 0874.68092)

Full Text:
DOI

##### References:

[1] | Abiteboul, S.; Beeri, C., On the power of languages for the manipulation of complex objects, () |

[2] | Abiteboul, S.; Hillebrand, G., Space usage in functional query languages, (), 439-454 |

[3] | Abiteboul, S.; Vianu, V., Fixpoint extensions of first-order logic and Datalog-like languages, (), 71-79 · Zbl 0716.68020 |

[4] | Aho, A.V.; Ullman, J.D., University of data retrieval languages, (), 110-120 |

[5] | Bancilhon, F.; Briggs, T.; Khoshafian, S.; Valduriez, P., A powerful and simple database language, (), 97-105 |

[6] | Barendregt, H., The lambda calculus: its syntax and semantics, (1984), Elsevier Amsterdam · Zbl 0551.03007 |

[7] | BreazuTannen, V.; Buneman, P.; Naqvi, S., Structureal recursion as a query language, (), 9-19 |

[8] | Breazu-Tannen, V.; Buneman, P.; Wong, L., Naturally embedded query languages, (), 140-154 |

[9] | Breazu-Tannen, V.; Subrahmanyam, R., Logical and computational aspects of programming with sets/bags/lists, (), 60-75 · Zbl 0769.68080 |

[10] | Buneman, P., The fast Fourier transform as a database query, () |

[11] | Buneman, P.; Frankel, R.E.; Nikhil, R., An implementation technique for database query languages, ACM trans. database system, 7, 164-187, (1982) |

[12] | Buneman, P.; Libkin, L.; Suciu, D.; Tannen, V.; Wong, L., Comprehension syntax, SIGMOD record, 23, 87-96, (1994) |

[13] | Chandra, A.; Harel, D., Computable queries for relational databases, J. comput. system sci, 21, 156-178, (1980) · Zbl 0456.68128 |

[14] | Chandra, A.; Harel, D., Structure and complexity of relational queries, J. comput. system sci, 25, 99-128, (1982) · Zbl 0511.68073 |

[15] | Codd, E.F., A relational model for large shared databanks, Commun. ACM, 13, 377-387, (1970) · Zbl 0207.18003 |

[16] | Colby, L.S., A recursive algebra for nested relations, Inform. systems, 15, 567-582, (1990) |

[17] | Fegaras, L., Efficient optimization of iterative queries, (), 200-225 |

[18] | Fegaras, L.; Maier, D., Towards an effective calculus for object query languages, () |

[19] | Goguen, J.; Meseguer, J., Completeness of many-sorted equational logic, Houston J. math, 11, 307-334, (1985) · Zbl 0602.08004 |

[20] | Goguen, J.A.; Thatcher, J.W.; Wagner, E.G., An initial algebra approach to the specification, correctness and implementation of abstract data types, (), 80-149 |

[21] | Gunter, E.; Libkin, L., OR-SML: a functional database programming language for disjunctive information, () |

[22] | Gyssens, M.; Van Gucht, D., A comparison between algebraic query languages for flat and nested databases, Theoret. comput. sci, 87, 263-286, (1991) · Zbl 0743.68053 |

[23] | Gyssens, M.; Van Gucht, D., The powerset algebra as a natural tool to handle nested database relations, J. comput. system sci, 45, 76-103, (1992) · Zbl 0752.68024 |

[24] | Hart, K.; Wong, L., A query interface for heterogeneous biological data sources, Manuscript, (February 1994), Available on WWW via ftp: |

[25] | Hart, K.; Wong, L.; Overton, C.; Buneman, P., Using a query language to integrate biological data, (), Available on WWW via |

[26] | Hillebrand, G.G.; Kanellakis, P.C.; Mairson, H.G., Database query languages embedded in the typed lambda calculus, (), 332-343 · Zbl 0856.68056 |

[27] | Imielinski, T.; Naqvi, S.; Vadaparty, K., Querying design and planning databases, (), 524-545 |

[28] | Immerman, N.; Patnaik, S.; Stemple, D., The expressiveness of a family of finite set language, (), 37-52 |

[29] | ISO, Standard 9075, Information processing systems, Database language SQL, (1987) |

[30] | Jaeschke, G.; Schek, H.J., Remarks on the algebra of non-first-normal-form relations, (), 124-138 |

[31] | Lambek, J.; Scott, P.J., Introduction to higher order categorical logic, (1986), Camridge Univ. Press London · Zbl 0596.03002 |

[32] | Libkin, L., Aspects of partial information in database, () · Zbl 0818.06004 |

[33] | Libkin, L., Approximation in database, (), 411-424 |

[34] | Libkin, L.; Wong, L., Semantic representations and query languages for or-sets, (), 37-48 |

[35] | Libkin, L.; Wong, L., Aggregate functions, conservative extension, and linear orders, (), 282-294 |

[36] | Libkin, L.; Wong, L., Some properties of query languag es for bags, (), 97-114 |

[37] | Libkin, L.; Wong, L., Conservativity of nested relational calculi with internal generic functions, Inform. process. lett, 49, 273-280, (1994) · Zbl 0803.68027 |

[38] | Libkin, L.; Wong, L., New techniques for studying set languages, bag languages, and aggregate functions, (), 155-166 |

[39] | MacLane, S., Categories for the working Mathematician, (1971), Springer Berlin |

[40] | Macleod, I.A., A database management system for document retrieval applications, Inform. systems, 6, (1981) |

[41] | Makinouchi, A., A consideration on normal form of not necessarily normalised relation in the relational data model, (), 447-453 |

[42] | Manes, E.G., Algebraic theories, (1976), Springer Berlin · Zbl 0489.18003 |

[43] | Meertens, L., Algorithmics — towards programming as a mathematical activity, (), 289-334 |

[44] | Meyer, A.R.; Mitchell, J.C.; Moggi, E.; Statman, R., Empty types in polymorphic λ-calculus, (), 253-262 |

[45] | Milner, R.; Tofte, M.; Harper, R., The definitin of standard ML, (1990), MIT Press Cambridge |

[46] | Moggi, E., Notions of computation and monads, Inform. comput, 93, 55-92, (1991) · Zbl 0723.68073 |

[47] | Naqvi, S.; Tsur, S., A logical language for data and knowledge bases, (1989), Computer Science Press New York |

[48] | Ohori, A.; Buneman, P.; Breazu-Tannen, V., Database programming in machiavelli, a polymorphic language with static type inference, (), 46-57 |

[49] | Paredaens, J.; Van Gucht, D., Converting nested relational algebra expression into flat algebra expressions, ACM trans. database systems, 17, 65-93, (1992) |

[50] | Saraiya, Y., Optimizing functional query languages, () |

[51] | Schek, H.-J.; Scholl, M.H., The relational model with relation-valued attributes, Inform. systems, 11, 137-147, (1989) · Zbl 0589.68067 |

[52] | Suciu, D., Fixpoints and bounded fixpoints for complex objects, (), 263-281 |

[53] | Suciu, D., Domain-independent queries on databases with external functions, (), 177-190 |

[54] | Suciu, D.; Paredaens, J., Any algorithm in the complex object algebra with powerset needs exponential space to compute transitive closure, (), 201-209 |

[55] | Suciu, D.; Tannen, V., A query language for NC, (), 167-178 |

[56] | Suciu, D.; Wong, L., On two forms of structural recursion, (), 111-124 |

[57] | Thomas, S.J.; Fischer, P.C., Nested relational structures, (), 269-307 |

[58] | Trinder, P.W., Comprehesions, a query notation for dbpls, (), 49-62 |

[59] | Trinder, P.W.; Wadler, P.L., List comprehensions and the relational calculus, (), 115-123 |

[60] | G. Venkatesh and M. Kohli, Shahrazade: a database query language for design and planning applications, Bellcore technical memorandum, Bellcore, Box 1910, Morristown, NJ 09760. |

[61] | Wadler, P.L., Comprehending monads, Math. struct. in comput. sci, 2, 461-493, (1992) · Zbl 0798.68040 |

[62] | Watt, D.A.; Trinder, P.W., Towards a theory of bulk types, () |

[63] | Wong, L., Normal forms and conservative properties for query languag e over collection types, (), 26-36 |

[64] | Wong, L., Querying nested collections, () |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.