This paper extends relational processing and optimization to the FISQL/FIRA languages for dynamic schema queries over multidatabases. Dynamic schema queries involve the creation and restructuring of metadata at runtime. We present a full implementation of a FISQL/FIRA engine, which includes subqueries and all transformational capabilities of FISQL/FIRA on distributed, multidatabase platforms. An important application of the system is to enhance traditional information architectures by enabling the creation and maintenance of dynamic wrappers and mapping queries at source databases within GAV, LAV, GLAV, peer-to-peer, or other integration frameworks. In addition to fully supporting FISQL/FIRA on multidatabases, our implementation introduces a bi-level optimization paradigm where purely relational sub-fragments of queries are pushed into source engines. This paradigm shares features of canonical distributed database processing, but has a new dimension through the extension of the relational model to dynamic schemas. We present empirical results showing the feasibility of optimization in this context, and discuss tradeoffs involved. Our system is the first to extend relational databases with these capabilities on this scale.

PIVOT is an important relational operation that allows data in rows to be exchanged for columns. Although most current relational database management systems support PIVOT-type operations, to date a purely formal, algebraic characterization of PIVOT has been lacking. In this paper, we present a characterization in terms of extended relational algebra operators τ (transpose), Π (drop projection), and μ (unique optimal tuple merge). This enables us to (1) draw parallels with PIVOT and existing operators employed in Dynamic Data Mapping Systems (DDMS), (2) formally characterize invertible PIVOT instances, and (3) provide complexity results for PIVOT-type operations. These contributions are an important part of ongoing work on formal models for relational OLAP.

We demonstrate a prototype of the relational data mapping module of MIQIS, a formal framework for investigating information flow in peer-to-peer database management systems. Data maps constitute effective mappings between structured data sources. These mappings are the `glue' for facilitating large scale ad-hoc information sharing between autonomous peers, and automating their discovery is one of the fundamental unsolved challenges for information interoperability and sharing. Our approach to automating data map discovery utilizes heuristic search within a space delineated by basic relational transformation operators. A novelty of our approach is that these operators include data to metadata transformations (and vice versa). This approach leverages new perspectives on the data mapping problem, and generalizes previous approaches such as token-based schema matching.

In this article, we develop a relational algebra for metadata integration, Federated Interoperable Relational Algebra (FIRA). FIRA has many desirable properties such as compositionality, closure, a deterministic semantics, a modest complexity, support for nested queries, a subalgebra equivalent to canonical Relational Algebra (RA), and robustness under certain classes of schema evolution. Beyond this, FIRA queries are capable of producing fully dynamic output schemas, where the number of relations and/or the number of columns in relations of the output varies dynamically with the input instance. Among existing query languages for relational metadata integration, only FIRA provides generalized dynamic output schemas, where the values in any (fixed) number of input columns can determine output schemas.Further contributions of this article include development of an extended relational model for metadata integration, the Federated Relational Data Model , which is strictly downward compatible with the relational model. Additionally, we define the notion of Transformational Completeness for relational query languages and postulate FIRA as a canonical transformationally complete language. We also give a declarative, SQL-like query language that is equivalent to FIRA, called Federated Interoperable Structured Query Language (FISQL).While our main contributions are conceptual, the federated model, FISQL/FIRA, and the notion of transformational completeness nevertheless have important applications to data integration and OLAP. In addition to summarizing these applications, we illustrate the use of FIRA to optimize FISQL queries using rule-based transformations that directly parallel their canonical relational counterparts. We conclude the article with an extended discussion of related work as well as an indication of current and future work on FISQL/FIRA.

The need for interoperability among databases has increased dramatically with the proliferation of readily available DBMS and application software. Even within a single organization, data from disparate relational databases must be integrated. A framework for interoperability in a federated system of relational databases should be inherently relational, so that it can use existing techniques for query evaluation and optimization where possible and retain the key features of SQL, such as a modest complexity and ease of query formulation. Our contribution is a logspace relational algebra, the Meta-Algebra (MA), for data/metadata integration among relational databases containing semantically similar information in schematically disparate formats. The MA is a simple yet powerful extension of the classical relational algebra (RA). The MA has a natural declarative counterpart, the Meta-Query Language (MQL), which we briefly describe. We state a result showing MQL and the MA are computationally equivalent, which enables us to algebratize MQL queries in fundamentally the same way as ordinary SQL queries. This algebratization in turn enables us to use MA equivalences to facilitate the application of known query optimization techniques to MQL query evaluation.