skip to main content
10.1145/1031171.1031177acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
Article

Extending and inferring functional dependencies in schema transformation

Published: 13 November 2004 Publication History

Abstract

We study the representation, derivation and utilization of a special kind of constraints in multidatabase systems. A major challenge is when component database schemas are <i>schematic discrepant</i> from each other, i.e., data values of one database correspond to schema labels of another. We propose "qualified functional dependencies" (or qualified FDs), an extension to conventional FDs to formalize integrity constraints in multidatabase systems. We first give inference rules to derive qualified FDs in fixed schemas, then study the derivation of qualified FDs during the transformations between schematic discrepant schemas. Propagation rules are given to derive qualified FDs of transformed schemas from qualified FDs of original schemas. Our work can be used in different stages of building and accessing a multidatabase system, e.g., to detect and resolve value inconsistency in schema integration, to verify lossless schema transformations, to normalize integrated schemas, to verify the integrity of data, and to optimize queries at an integration level. In particular, as an application of our theory, we will use FDs to check the validity of SchemaSQL views (SchemaSQL is a powerful multidatabase language).

References

[1]
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995, 173--187, 216--235.
[2]
R. Agrawal, A. Somani, and Y. R. Xu. Storing and querying of e-commerce data. VLDB, 2001, 149--158.
[3]
J. Albert. Theoretical Foundations of Schema Restructuring in Heterogeneous Multidatabase Systems. CIKM, 2000.
[4]
C. Batini, M. Lenzerini, and S. B. Navathe. A comparative analysis of methodologies for schema integration. CN computing surveys 18(4), 1986, 323--364.
[5]
F. Berzal, J. C. Cubero, F. Cuenca, J. M. Medina. Relational decomposition through partial functional dependencies. Data & Knowledge Engineering 43(2), 2002, 207--234.
[6]
P. De Bra and J. Paredaens. Conditional dependencies for horizontal decompositions. ICALP, 1983.
[7]
G. Gottlob. Computing covers for embedded functional dependencies. SIGMOD, 1987.
[8]
M. Gyssens, L. Lakshmanan, and S. N. Subramanian. Tables as a paradigm for querying and restructuring. PODS, 1996.
[9]
Qi He, Tok Wang Ling. Extending and inferring functional dependencies in schema transformation: extended version. Technical report, TRA3/04. School of Computing, National University of Singapore, 2004. http://wwwappn.comp.nus.edu.sg esubmit/diglib/public/techrep/2004/TRA304/report.pdf
[10]
C. N. Hsu and C. A. Knoblock. Semantic query optimization for query plans of heterogeneous multidatabase systems. TKDE 12(6), 2000, 959--978.
[11]
R. Krishnamurthy, W Litwen, and W. Kent. Language features for interoperability of databases with schematic discrepancies. SIGMOD, 1991, 40--49.
[12]
L. V. S. Lakshmanan, F. Sadri, and S. N. Subramanian. On efficiently implementing schemaSQL on SQL database system. VLDB, 1999, 471--482.
[13]
L. V. S. Lakshmanan, F. Sadri, and S. N. Subramanian. SchemaSQL-an extension to SQL for multidatabase interoperability. TODS, 2001, 476--519.
[14]
Mong Li Lee, Tok Wang Ling. A methodology for structural conflicts resolution in the integration of entity-relationship schemas. Knowledge and Information Sys., 5, 2003, 225--247.
[15]
Mong Li Lee and Tok Wang Ling. Resolving constraint conflicts in the integration of ER schemas. ER, 1997, 394--407.
[16]
Chen Li. Describing and Utilizing Constraints to Answer Queries in Data-Integration Systems. IIWeb, 2003, 163--168.
[17]
Tok Wang Ling. Extending classical functional dependencies for physical database design (lecture notes), 2001. http://www.comp.nus.edu.sg/ lingtw/cs4221/extended.fds.pdf
[18]
Tok Wang Ling, Mong Li Lee. Issues in an entityrelationship based federated database system. CODAS, 1996, 60--69.
[19]
R. J. Miller. Using schematically heterogeneous structures. SIGMOD, 1998, 189--200.
[20]
R. Ramakrishnan and J. Gehrke. Database Management Systems, 2nd Ed. McGraw-Hill, 1999, 427, 438--444.
[21]
M. P. Reddy, B. E. Prasad, and A. Gupta. Formulating global integrity constraints during derivation of global schema. Data & Knowledge Engineering, 1995, 241--268.
[22]
A. P. Sheth and S. K. Gala. Federated database systems for managing distributed, heterogenous, and autonomous databases. ACM Computing Surveys, 1990.
[23]
M. W. W. Vermeer and P. M. G. Apers. The role of integrity constraints in database interoperation. VLDB, 1996, 425--435.

Cited By

View all
  • (2024)Common equivalence and size of forgetting from Horn formulaeAnnals of Mathematics and Artificial Intelligence10.1007/s10472-024-09955-5Online publication date: 29-Oct-2024
  • (2016)Implication and axiomatization of functional and constant constraintsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-015-9473-776:3-4(251-279)Online publication date: 1-Apr-2016
  • (2016)Improving the Correctness of Some Database Research Using ORA-SemanticsConceptual Modeling10.1007/978-3-319-46397-1_1(3-17)Online publication date: 7-Oct-2016
  • Show More Cited By

Index Terms

  1. Extending and inferring functional dependencies in schema transformation

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    CIKM '04: Proceedings of the thirteenth ACM international conference on Information and knowledge management
    November 2004
    678 pages
    ISBN:1581138741
    DOI:10.1145/1031171
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 November 2004

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. functional dependency
    2. multidatabase
    3. schema integration
    4. schematic discrepancy

    Qualifiers

    • Article

    Conference

    CIKM04
    Sponsor:
    CIKM04: Conference on Information and Knowledge Management
    November 8 - 13, 2004
    D.C., Washington, USA

    Acceptance Rates

    Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

    Upcoming Conference

    CIKM '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 09 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Common equivalence and size of forgetting from Horn formulaeAnnals of Mathematics and Artificial Intelligence10.1007/s10472-024-09955-5Online publication date: 29-Oct-2024
    • (2016)Implication and axiomatization of functional and constant constraintsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-015-9473-776:3-4(251-279)Online publication date: 1-Apr-2016
    • (2016)Improving the Correctness of Some Database Research Using ORA-SemanticsConceptual Modeling10.1007/978-3-319-46397-1_1(3-17)Online publication date: 7-Oct-2016
    • (2015)A Method to Induce Indicative Functional Dependencies for Relational Data ModelAdvances in Intelligent Informatics10.1007/978-3-319-11218-3_40(445-456)Online publication date: 2015
    • (2014)Implication and Axiomatization of Functional Constraints on Patterns with an Application to the RDF Data ModelProceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems - Volume 836710.1007/978-3-319-04939-7_12(250-269)Online publication date: 3-Mar-2014
    • (2013)Inferring and Propagating Pivot Dependencies in Schema Transformation between Data and MetadataProceedings of the 2013 10th Web Information System and Application Conference10.1109/WISA.2013.69(333-338)Online publication date: 10-Nov-2013
    • (2008)Propagating functional dependencies with conditionsProceedings of the VLDB Endowment10.14778/1453856.14539011:1(391-407)Online publication date: 1-Aug-2008
    • (2007)Extending relational query optimization to dynamic schemas for information integration in multidatabasesProceedings of the 2007 ACM SIGMOD international conference on Management of data10.1145/1247480.1247533(473-484)Online publication date: 11-Jun-2007
    • (2006)Putting context into schema matchingProceedings of the 32nd international conference on Very large data bases10.5555/1182635.1164155(307-318)Online publication date: 1-Sep-2006
    • (2006)Global Schema as an Inversed View of Local Schemas for IntegrationProceedings of the Fourth International Conference on Software Engineering Research, Management and Applications10.1109/SERA.2006.39(206-212)Online publication date: 9-Aug-2006
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media