BQL(ID:3536/bql001)Bag Query Language Libkin and Wong 1993 Database language for Bags Uni of Pennsylvania Structures: References: Collection types such as sets, bags (multisets), lists, complex objects, nested relations, arrays, and certain kinds of trees are widely used in non-traditional database applications and must therefore be properly supported by modern database systems. The study of languages for these structures has only recently received serious attention. Can we find languages that naturally support these structures in the same way that relational languages support relational databases? Practical database languages are based on first-order logic, and much research has been devoted to augmentations of first-order logic to produce languages of increased expressive power, but with the added demands of dealing with collection types, we must ask whether we are stretching this computational paradigm beyond its breaking point. This tutorial will suggest that we can cope with a rich variety of collection type semantics by looking at the operations that are "naturally'' (in the sense of category theory) associated with the data structures involved. Surprisingly, category theory concepts that one might dismiss as too esoteric lead to a succession of useful languages for collection types, that includes equivalents of familiar languages for relational databases, such as relational algebra, nested relational algebra and datalog. As an extra bonus, this approach provides a basis for language syntax that is closely related to that of practical database query languages such as SQL. Moreover, this approach provides equational logics which serve to study certain classes of query optimizations. Finally, there are some intriguing connections between these languages and query complexity classes, both sequential and parallel. in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details |