Skip to main content
SpringerLink
Log in

Simplification of Integrity Constraints for Data Integration

  • Conference paper
Foundations of Information and Knowledge Systems (FoIKS 2004)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2942))

Abstract

When two or more databases are combined into a global one, integrity may be violated even when each database is consistent with its own local integrity constraints. Efficient methods for checking global integrity in data integration systems are called for: answers to queries can then be trusted, because either the global database is known to be consistent or suitable actions have been taken to provide consistent views. The present work generalizes simplification techniques for integrity checking in traditional databases to the combined case. Knowledge of local consistency is employed, perhaps together with given a priori constraints on the combination, so that only a minimal number of tuples needs to be considered. Combination from scratch, integration of a new source, and absorption of local updates are dealt with for both the local-as-view and global-as-view approaches to data integration.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abiteboul, S.: Querying semi-structured data. In: Afrati, F.N., Kolaitis, P.G. (eds.) ICDT 1997. LNCS, vol. 1186, pp. 1–18. Springer, Heidelberg (1996)

    Google Scholar 

  2. Arenas, M., Bertossi, L., Chomicki, J.: Specifying and Querying Database Repairs using Logic Programs with Exceptions. In: Larsen, H., Kacprzyk, J., Zadrozny, S., Andreasen, T., Christiansen, H. (eds.) Proceedings of FQAS 2000, pp. 27–41. Physica-Verlag, A Springer-Verlag Company, Heidelberg (2000)

    Google Scholar 

  3. De Amo, S., Carnielli, W., Marcos, J.: A Logical Framework for Integrating Inconsistent Information in Multiple Databases. In: Eiter, T., Schewe, K.-D. (eds.) FoIKS 2002. LNCS, vol. 2284, pp. 67–84. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  4. Arieli, O., Denecker, M., Van Nuffelen, B., Bruynooghe, M.: Repairing Inconsistent Databases: A Model-Theoretic Approach and Abductive Reasoning. In: Decker, H., Villadsen, J., Waragaipp, T. (eds.) PCL 2002, Datalogiske Skrifter, vol. 95, pp. 51–65. Roskilde University, Roskilde (2002)

    Google Scholar 

  5. Buneman, P.: Semistructured data. In: Proc. of the ACM SIGACT-SIGMODSIGART Smposium on Principles of Database Systems (PODS), pp. 117–121. ACM Press, New York (1997)

    Google Scholar 

  6. Baral, C., Kraus, S., Minker, J.: Combining multiple knowledge bases. IEEE Transactions on Knowledge and Data Engineering 3(2), 208–220 (1991)

    Article  Google Scholar 

  7. Baral, C., Kraus, S., Minker, J., Subrahmanian, S.: Combining knowledge bases consisting of first-order theories. Computational Intelligence 8, 45–71 (1992)

    Article  Google Scholar 

  8. Bertossi, L., Schwind, C.: Analytic Tableaux and Database Repairs: Foundations. In: Eiter, T., Schewe, K.-D. (eds.) FoIKS 2002. LNCS, vol. 2284, pp. 32–48. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  9. Calì, A., Calvanese, D., De Giacomo, G., Lenzerini, M.: On the Role of Integrity Constraints in Data Integration. Bull. of the IEEE Computer Society Technical Committee on Data Engineering 25(3), 39–45 (2002)

    Google Scholar 

  10. Calì, A., Calvanese, D., De Giacomo, G., Lenzerini, M.: Data Integration under Integrity Constraints. In: Pidduck, A.B., Mylopoulos, J., Woo, C.C., Ozsu, M.T. (eds.) CAiSE 2002. LNCS, vol. 2348, pp. 262–279. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  11. Calì, A., Calvanese, D., De Giacomo, G., Lenzerini, M.: On the Expressive Power of Data Integration Systems. In: Spaccapietra, S., March, S.T., Kambayashi, Y. (eds.) ER 2002. LNCS, vol. 2503, pp. 338–350. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  12. Chakravarthy, U.S., Grant, J., Minker, J.: Foundations of semantic query optimization for deductive databases. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann, San Francisco (1987)

    Google Scholar 

  13. Christiansen, H., Martinenghi, D.: Simplification of database integrity constraints revisited: A transformational approach. Presented at LOPSTR, Uppsala, Sweden, August 25-27 (2003), Preliminary version available at http://www.dat.ruc.dk/~henning/LOPSTR03.pdf

  14. Dijkstra, E.W.: A Discipline of Programming. Prentice-Hall, Englewood Cliffs (1976)

    MATH  Google Scholar 

  15. Flach, P., Kakas, A. (eds.): Abductive and Inductive Reasoning: Essays on their Relation and Integration, pp. 195–211. Kluwer Academic Publishers, Dordrecht (2000)

    Google Scholar 

  16. Godfrey, P., Grant, J., Gryz, J., Minker, J.: Integrity Constraints: Semantics and Applications. In: Chomicki, J., Saake, G. (eds.) Logics for Databases and Information System, pp. 265–306. Kluwer, Dordrecht (1988)

    Google Scholar 

  17. Grant, J., Minker, J.: A logic-based approach to data integration. Theory and Practice of Logic Programming (TPLP) 2, 323–368 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  18. Hoare, C.A.R.: An axiomatic basis for computer programming. Communications of the ACM 12(10), 576–580 (1969)

    Article  MATH  Google Scholar 

  19. Kakas, A.A., Kowalski, R.A., Toni, F.: The role of abduction in logic programming. In: Gabbay, D.M., Hogger, C.J., Robinson, J.A. (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 5, pp. 235–324. Oxford University Press, Oxford (1998)

    Google Scholar 

  20. Levy, A.Y.: Combining Artificial Intelligence and Databases for Data Integration. In: Veloso, M.M., Wooldridge, M.J. (eds.) Artificial Intelligence Today. LNCS (LNAI), vol. 1600, pp. 249–268. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  21. Li, C.: Describing and Utilizing Constraints to Answer Queries in Data-Integration Systems. In: IJCAI 2003 workshop on Information Integration on the Web (2003), On-line proceedings available at http://www.isi.edu/info-agents/workshops/ijcai03/proceedings.htm

  22. Lin, J., Mendelzon, A.: Merging Databases Under Constraints. International Journal of Cooperative Information Systems 7(1), 55–76 (1998)

    Article  Google Scholar 

  23. Martinenghi, D.: A Simplification Procedure for Integrity Constraints. In: World Wide Web (2003), http://www.dat.ruc.dk/~dm/spic/index.html

  24. Nicolas, J.-M.: Logic for Improving Integrity Checking in Relational Data Bases. Acta Informatica 18, 227–253 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  25. Nilsson, U., Małuzyński, J.: Logic, Programming and Prolog, 2nd edn. John Wiley & Sons Ltd., Chichester (1995)

    Google Scholar 

  26. Revesz, P.: On the Semantics of Arbitration. Journal of Algebra and Computation 7(2), 133–160 (1997)

    Article  MathSciNet  Google Scholar 

  27. Rahm, E., Bernstein, P.: A survey of approaches to automatic schema matching. VLDB Journal 10(4), 334–350 (2001)

    Article  MATH  Google Scholar 

  28. Ullman, J.: Information integration using logical views. In: International Conference on Database Theory, pp. 19–40 (1997)

    Google Scholar 

  29. Xu, L., Embley, D.: Discovering Direct and Indirect Matches for Schema Elements. In: Eighth International Conference on Database Systems for Advanced Applications (DASFAA 2003), Kyoto, Japan, pp. 39–46. IEEE Computer Society, Los Alamitos (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Dept., Roskilde University, P.O. Box 260, DK-4000, Roskilde, Denmark

    Henning Christiansen & Davide Martinenghi

Authors
  1. Henning Christiansen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Davide Martinenghi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universität Würzburg, Am Hubland, 97074, Würzburg, Germany

    Dietmar Seipel

  2. Department of Information Systems, Massey University, Information Science Research Centre, PO Box 756, Wellington, New Zealand

    José María Turull-Torres

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Christiansen, H., Martinenghi, D. (2004). Simplification of Integrity Constraints for Data Integration. In: Seipel, D., Turull-Torres, J.M. (eds) Foundations of Information and Knowledge Systems. FoIKS 2004. Lecture Notes in Computer Science, vol 2942. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24627-5_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-24627-5_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20965-2

  • Online ISBN: 978-3-540-24627-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation