Indiana University Bloomington

Luddy School of Informatics, Computing, and Engineering

Technical Report TR528:
MD-SQL: A Language for Meta-Data Queries over Relational Databases

C. M. Rood, D. Van Gucht and F. I. Wyss
(Jul 1999), 20 pages pages
Future users of large, interconnected databases and data warehouses will increasingly require schematic transparency of data manipulation systems, in that (i) data from heterogeneous sources must be compared and interrelated and (ii) data must be queried and extracted by distant users having minimal knowledge of its logical structure. A query language that abstracts over meta-data as well as ordinary data is needed. Previous work in this area has resulted in HILOG, SchemaLog and SchemaSQL. Although SchemaSQL improves on its predecessors, it remains somewhat informal and relies on a specialized transformation into a fragment of the tabular algebra to give it a viable operational semantics. In contrast, we provide a complete EBNF for Meta-Data SQL (MD-SQL) as a straightforward extension of a relationally complete subset of standard SQL. Like SchemaSQL, MD-SQL allows queries involving meta-data and ordinary data in a multi-database context over potentially disparate platforms. Schematic elements and data are freely interchangeable, and queries are allowed whose output type cannot be known at compile time. Unlike SchemaSQL however, each MD-SQL query translates into a series of simple, atomic operations, each of which is inherently relational. We formalize this translation by presenting a complete meta-algebra which is shown to be equivalent to MD-SQL. Furthermore, we provide some complexity results, in particular that MD-SQL and the meta-algebra yield characterizations of PSPACE. We also give results concerning when the output type of an MD-SQL query can be deduced at compile time. Finally we briefly discuss an implementation of MD-SQL over an ordinary, relational system that uses the DynamicSQL/CLI standard. Since MD-SQL is relational in nature, our implementation can benefit directly from existing query optimization techniques.

Available as: