{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:28:07Z","timestamp":1765484887299},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>\n            In this article, we develop a relational algebra for metadata integration,\n            <jats:italic>Federated Interoperable Relational Algebra<\/jats:italic>\n            (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\n            <jats:italic>Federated Relational Data Model<\/jats:italic>\n            , which is strictly downward compatible with the relational model. Additionally, we define the notion of\n            <jats:italic>Transformational Completeness<\/jats:italic>\n            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\n            <jats:italic>Federated Interoperable Structured Query Language<\/jats:italic>\n            (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.\n          <\/jats:p>","DOI":"10.1145\/1071610.1071618","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"624-660","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Relational languages for metadata integration"],"prefix":"10.1145","volume":"30","author":[{"given":"Catharine M.","family":"Wyss","sequence":"first","affiliation":[{"name":"Indiana University, Bloomington, IN"}]},{"given":"Edward L.","family":"Robertson","sequence":"additional","affiliation":[{"name":"Indiana University, Bloomington, IN"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/101620.101641"},{"key":"e_1_2_1_2_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley New York.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley New York."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/238355.238565"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304590"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 16th Meeting of the Information Processing Society of Japan. IPSJ","author":"Chawathe S.","unstructured":"Chawathe , S. , Garcia-Molina , H. , Hammer , J. , Ireland , K. , Papakonstantinou , Y. , Ullman , J. D. , and Widom , J . 1994. The TSIMMIS project: Integration of heterogeneous information sources . In Proceedings of the 16th Meeting of the Information Processing Society of Japan. IPSJ , Tokyo, Japan, 7--18. Chawathe, S., Garcia-Molina, H., Hammer, J., Ireland, K., Papakonstantinou, Y., Ullman, J. D., and Widom, J. 1994. The TSIMMIS project: Integration of heterogeneous information sources. In Proceedings of the 16th Meeting of the Information Processing Society of Japan. IPSJ, Tokyo, Japan, 7--18."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the North American Conference","author":"Chen W.","year":"1989","unstructured":"Chen , W. , Kifer , M. , and Warren , D. S . 1989. HiLog: A first-order semantics for higher-order logic programming constructs. In Logic Programming , Proceedings of the North American Conference 1989 , E. L. Lusk and R. A. Overbeek, Eds. (Cleveland, Ohio). MIT Press, Cambridge, Mass., 1090--1114. Chen, W., Kifer, M., and Warren, D. S. 1989. HiLog: A first-order semantics for higher-order logic programming constructs. In Logic Programming, Proceedings of the North American Conference 1989, E. L. Lusk and R. A. Overbeek, Eds. (Cleveland, Ohio). MIT Press, Cambridge, Mass., 1090--1114."},{"key":"e_1_2_1_7_1","unstructured":"Chen W. Kifer M. and Warren D. S. 1990a. HiLog: A foundation for higher-order logic programming. Tech. Rep. State University of New York at Stony Brook Stony Brook N.Y.  Chen W. Kifer M. and Warren D. S. 1990a. HiLog: A foundation for higher-order logic programming. Tech. Rep. State University of New York at Stony Brook Stony Brook N.Y."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 2nd International Workshop on Database Programming Languages, R. Hull, R. Morrison, and D. W. Stemple, Eds. (Gleneden Beach, Ore.). Morgan-Kaufmann","author":"Chen W.","unstructured":"Chen , W. , Kifer , M. , and Warren , D. S . 1990b. HiLog as a platform for database languages . In Proceedings of the 2nd International Workshop on Database Programming Languages, R. Hull, R. Morrison, and D. W. Stemple, Eds. (Gleneden Beach, Ore.). Morgan-Kaufmann , San Francisco, Calif., 315--329. Chen, W., Kifer, M., and Warren, D. S. 1990b. HiLog as a platform for database languages. In Proceedings of the 2nd International Workshop on Database Programming Languages, R. Hull, R. Morrison, and D. W. Stemple, Eds. (Gleneden Beach, Ore.). Morgan-Kaufmann, San Francisco, Calif., 315--329."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/288627.288672"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 30th International Conference on Very Large DataBases (VLDB 2004)","author":"Cunningham C.","unstructured":"Cunningham , C. , Galindo-Legaria , C. A. , and Graefe , G . 2004. PIVOT and UNPIVOT: Optimization and execution strategies in an RDBMS . In Proceedings of the 30th International Conference on Very Large DataBases (VLDB 2004) (Toronto, Ont., Canada). Morgan-Kaufmann, San Francisco, Calif., 998--1009. Cunningham, C., Galindo-Legaria, C. A., and Graefe, G. 2004. PIVOT and UNPIVOT: Optimization and execution strategies in an RDBMS. In Proceedings of the 30th International Conference on Very Large DataBases (VLDB 2004) (Toronto, Ont., Canada). Morgan-Kaufmann, San Francisco, Calif., 998--1009."},{"key":"e_1_2_1_12_1","unstructured":"Dalkilic M. Jain M. Van Gucht D. and Mendhekar A. 1996. Design and implementation of reflective SQL. Tech. Rep. TR 451 Indiana University.  Dalkilic M. Jain M. Van Gucht D. and Mendhekar A. 1996. Design and implementation of reflective SQL. Tech. Rep. TR 451 Indiana University."},{"key":"e_1_2_1_13_1","unstructured":"Garcia-Molina H. Ullman J. D. and Widom J. 2000. Database System Implementation. Prentice-Hall Upper Saddle River New Jersey.   Garcia-Molina H. Ullman J. D. and Widom J. 2000. Database System Implementation. Prentice-Hall Upper Saddle River New Jersey."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of 24th International Conference on Very Large Data Bases, A. Gupta, O. Shmueli, and J. Widom, Eds. (New York City, N.Y.). Morgan-Kaufmann","author":"Gingras F.","unstructured":"Gingras , F. and Lakshmanan , L. V . 1998. nD-SQL: A multi-dimensional language for interoperability and OLAP . In Proceedings of 24th International Conference on Very Large Data Bases, A. Gupta, O. Shmueli, and J. Widom, Eds. (New York City, N.Y.). Morgan-Kaufmann , San Francisco, Calif., 134--145. Gingras, F. and Lakshmanan, L. V. 1998. nD-SQL: A multi-dimensional language for interoperability and OLAP. In Proceedings of 24th International Conference on Very Large Data Bases, A. Gupta, O. Shmueli, and J. Widom, Eds. (New York City, N.Y.). Morgan-Kaufmann, San Francisco, Calif., 134--145."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055560"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/615164.615167"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237688"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316691"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66939"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115795"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 14th International Conference on Very Large Data Bases, F. Bancilhon and D. J. DeWitt, Eds.","author":"Krishnamurthy R.","unstructured":"Krishnamurthy , R. and Naqvi , S. A . 1988. Towards a real horn clause language . In Proceedings of the 14th International Conference on Very Large Data Bases, F. Bancilhon and D. J. DeWitt, Eds. ( Los Angeles, Calif., Aug. 29--Sept. 1). Morgan-Kaufmann, San Francisco, Calif., 252--263. Krishnamurthy, R. and Naqvi, S. A. 1988. Towards a real horn clause language. In Proceedings of the 14th International Conference on Very Large Data Bases, F. Bancilhon and D. J. DeWitt, Eds. (Los Angeles, Calif., Aug. 29--Sept. 1). Morgan-Kaufmann, San Francisco, Calif., 252--263."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 3rd International Conference on Deductive and Object-Oriented Databases, S. Ceri, K. Tanaka, and S. Tsur, Eds. (Phoenix, Az.). Springer-Verlag","author":"Lakshmanan L. V.","unstructured":"Lakshmanan , L. V. , Sadri , F. , and Subramanian , I. N . 1993. On the logical foundations of schema integration and evolution in heterogeneous database systems . In Proceedings of the 3rd International Conference on Deductive and Object-Oriented Databases, S. Ceri, K. Tanaka, and S. Tsur, Eds. (Phoenix, Az.). Springer-Verlag , New York, 81--100. Lakshmanan, L. V., Sadri, F., and Subramanian, I. N. 1993. On the logical foundations of schema integration and evolution in heterogeneous database systems. In Proceedings of the 3rd International Conference on Deductive and Object-Oriented Databases, S. Ceri, K. Tanaka, and S. Tsur, Eds. (Phoenix, Az.). Springer-Verlag, New York, 81--100."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Workshop on Research Issues in Data Engineering (New Orleans, La.). IEEE Computer Society Press, Los Alamitos, Calif., 12--19","author":"Lakshmanan L. V. S.","unstructured":"Lakshmanan , L. V. S. , Sadri , F. , and Subramanian , I. N . 1996a. A declarative language for querying and restructuring the web . In Proceedings of the International Workshop on Research Issues in Data Engineering (New Orleans, La.). IEEE Computer Society Press, Los Alamitos, Calif., 12--19 . Lakshmanan, L. V. S., Sadri, F., and Subramanian, I. N. 1996a. A declarative language for querying and restructuring the web. In Proceedings of the International Workshop on Research Issues in Data Engineering (New Orleans, La.). IEEE Computer Society Press, Los Alamitos, Calif., 12--19."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of 22th International Conference on Very Large Data Bases, T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, Eds.","author":"Lakshmanan L. V. S.","unstructured":"Lakshmanan , L. V. S. , Sadri , F. , and Subramanian , I. N . 1996b. SchemaSQL---A language for interoperability in relational multi-database systems . In Proceedings of 22th International Conference on Very Large Data Bases, T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, Eds. ( Mumbai, India). Morgan-Kaufmann, San Francisco, Calif., 239--250. Lakshmanan, L. V. S., Sadri, F., and Subramanian, I. N. 1996b. SchemaSQL---A language for interoperability in relational multi-database systems. In Proceedings of 22th International Conference on Very Large Data Bases, T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, Eds. (Mumbai, India). Morgan-Kaufmann, San Francisco, Calif., 239--250."},{"key":"e_1_2_1_26_1","first-page":"2","article-title":"Logic and algebraic languages for interoperability in multidatabase systems","volume":"32","author":"Lakshmanan L. V. S.","year":"1997","unstructured":"Lakshmanan , L. V. S. , Sadri , F. , and Subramanian , I. N. 1997 . Logic and algebraic languages for interoperability in multidatabase systems . J. Logic Prog. 32 , 2 (Nov.), 101--149. Lakshmanan, L. V. S., Sadri, F., and Subramanian, I. N. 1997. Logic and algebraic languages for interoperability in multidatabase systems. J. Logic Prog. 32, 2 (Nov.), 101--149.","journal-title":"J. Logic Prog."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of 25th International Conference on Very Large Data Bases, M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, Eds.","author":"Lakshmanan L. V. S.","unstructured":"Lakshmanan , L. V. S. , Sadri , F. , and Subramanian , S. N . 1999. On efficiently implementing SchemaSQL on a SQL database system . In Proceedings of 25th International Conference on Very Large Data Bases, M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, Eds. ( Edinburgh, Scotland). Morgan-Kaufmann, San Francisco, Calif., 471--482. Lakshmanan, L. V. S., Sadri, F., and Subramanian, S. N. 1999. On efficiently implementing SchemaSQL on a SQL database system. In Proceedings of 25th International Conference on Very Large Data Bases, M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, Eds. (Edinburgh, Scotland). Morgan-Kaufmann, San Francisco, Calif., 471--482."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/503099.503102"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(89)90024-8"},{"key":"e_1_2_1_31_1","volume-title":"SISQL: Schema-independent database querying (on and off the web). In Proceedings of the International Database Engineering and Applications Symposium (IDEAS'00) (Yokohama, Japan)","author":"Masermann U.","year":"2000","unstructured":"Masermann , U. and Vossen , G . 2000 . SISQL: Schema-independent database querying (on and off the web). In Proceedings of the International Database Engineering and Applications Symposium (IDEAS'00) (Yokohama, Japan) . IEEE Computer Society Press , Los Alamitos , Calif., 55--65. Masermann, U. and Vossen, G. 2000. SISQL: Schema-independent database querying (on and off the web). In Proceedings of the International Database Engineering and Applications Symposium (IDEAS'00) (Yokohama, Japan). IEEE Computer Society Press, Los Alamitos, Calif., 55--65."},{"key":"e_1_2_1_32_1","unstructured":"Naqvi S. A. and Tsur S. 1989. A Logical Language for Data and Knowledge Bases. Computer Science Press Inc. New York N.Y.   Naqvi S. A. and Tsur S. 1989. A Logical Language for Data and Knowledge Bases. Computer Science Press Inc. New York N.Y."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 12th International Conference on Data Engineering (New Orleans, La.). IEEE Computer Society Press, Los Alamitos, Calif.","author":"Papakonstantinou Y.","unstructured":"Papakonstantinou , Y. , Garc\u00eda-Molina , H. , and Ullman , J . 1996. MedMaker: A mediation system based on declarative specifications . In Proceedings of the 12th International Conference on Data Engineering (New Orleans, La.). IEEE Computer Society Press, Los Alamitos, Calif. Papakonstantinou, Y., Garc\u00eda-Molina, H., and Ullman, J. 1996. MedMaker: A mediation system based on declarative specifications. In Proceedings of the 12th International Conference on Data Engineering (New Orleans, La.). IEEE Computer Society Press, Los Alamitos, Calif."},{"key":"e_1_2_1_34_1","unstructured":"Ramakrishnan R. and Gehrke J. 2003. Database Management Systems Third ed. McGraw-Hill New York.   Ramakrishnan R. and Gehrke J. 2003. Database Management Systems Third ed. McGraw-Hill New York."},{"key":"e_1_2_1_35_1","volume-title":"Tech. Rep. TR599","author":"Robertson E. L.","year":"2004","unstructured":"Robertson , E. L. and Wyss , C. M . 2004 . Optimal tuple merge is NP-Complete . Tech. Rep. TR599 , Indiana University Computer Science . July. Robertson, E. L. and Wyss, C. M. 2004. Optimal tuple merge is NP-Complete. Tech. Rep. TR599, Indiana University Computer Science. July."},{"key":"e_1_2_1_36_1","volume-title":"Tech. Rep. TR-528","author":"Rood C. M.","year":"1999","unstructured":"Rood , C. M. , Van Gucht , D. , and Wyss , F. I . 1999 . MD-SQL: A language for meta-data queries over relational databases. Tech. Rep. TR-528 , Indiana University at Bloomington . July. Rood, C. M., Van Gucht, D., and Wyss, F. I. 1999. MD-SQL: A language for meta-data queries over relational databases. Tech. Rep. TR-528, Indiana University at Bloomington. July."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137905"},{"key":"e_1_2_1_38_1","volume-title":"DS-5","author":"Saltor F.","unstructured":"Saltor , F. , Castellanos , M. , and Garcia-Solaco , M. 1993. Overcoming schematic discrepancies in interoperable databases . In DS-5 , D. K. Hsiao, E. J. Neuhold, and R. Sacks-Davis, Eds. IFIP Transactions, vol. A-25 . North-Holland, Amsterdam, The Netherland , 191--205. Saltor, F., Castellanos, M., and Garcia-Solaco, M. 1993. Overcoming schematic discrepancies in interoperable databases. In DS-5, D. K. Hsiao, E. J. Neuhold, and R. Sacks-Davis, Eds. IFIP Transactions, vol. A-25. North-Holland, Amsterdam, The Netherland, 191--205."},{"key":"e_1_2_1_39_1","volume-title":"Tech. Rep. WPI-CS-TR-00-19","author":"Su H.","year":"2000","unstructured":"Su , H. , Claypool , K. , and Rundensteiner , E. A . 2000 . Extending the object query language for transparent metadata access. Tech. Rep. WPI-CS-TR-00-19 , Worcester Polytechnic Institute . Su, H., Claypool, K., and Rundensteiner, E. A. 2000. Extending the object query language for transparent metadata access. Tech. Rep. WPI-CS-TR-00-19, Worcester Polytechnic Institute."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153852"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Van den Bussche J. Vansummeren S. and Vossen G. 2004. Meta-SQL: Towards practical meta-querying. In Advances in Database Technology (EDBT 2004): 9th International Conference on Extending Database Technology (Heraklion Crete Greece). Springer-Verlag New York 823--825.  Van den Bussche J. Vansummeren S. and Vossen G. 2004. Meta-SQL: Towards practical meta-querying. In Advances in Database Technology (EDBT 2004): 9th International Conference on Extending Database Technology (Heraklion Crete Greece). Springer-Verlag New York 823--825.","DOI":"10.1007\/978-3-540-24741-8_48"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1812"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/502585.502597"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 4th Workshop (EFIS","author":"Wyss C.","year":"2001","unstructured":"Wyss , C. , Wyss , F. , and Van Gucht , D. 2001 . Augmenting SQL with dynamic restructuring to support interoperability in a relational federation. In Engineering Federated Information Systems , Proceedings of the 4th Workshop (EFIS 2001), R.-D. Kutsche, S. Conrad, and W. Hasselbring, Eds. (Berlin, Germany Oct. 9--10). IOS Press, 5--18. Wyss, C., Wyss, F., and Van Gucht, D. 2001. Augmenting SQL with dynamic restructuring to support interoperability in a relational federation. In Engineering Federated Information Systems, Proceedings of the 4th Workshop (EFIS 2001), R.-D. Kutsche, S. Conrad, and W. Hasselbring, Eds. (Berlin, Germany Oct. 9--10). IOS Press, 5--18."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071610.1071618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:26:19Z","timestamp":1672244779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071610.1071618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071610.1071618"],"URL":"https:\/\/doi.org\/10.1145\/1071610.1071618","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}