Querying Nested Relations

Participants: Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, Limsoon Wong


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. Firstly, 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 and lists, and this suggests how database languages may be uniformly extended to these new types.

We also look into various questions on the expressive power of query languages resulting from this paradigm. We prove a number of very fundamental results---the conservative extension property, the finite-cofiniteness property, and the bounded degree property---on nested relational query languages and on SQL.


Selected Publications


Selected Presentations


This project is supported in part by ONR grant NOOO-14-88-K-0634 (Buneman, Tannen), NSF grant CCR-90-57570 (Suciu, Tannen: 90 - 95), ARO grant DAALO3-89-C-0031-PRIME (Tannen, Wong: 91 - 94), NSF grant IRI-86-10617 (Buneman), NSF grant IRI-90-04137 (Libkin, Suciu: 91 - 94; Wong: 90), and EDB grant to establish the NUS Bioinformatics Center (Wong: 96 - 98).

Last updated: 26/3/14, Limsoon Wong.