Computing Dependencies Using FCA | SpringerLink
Skip to main content
Springer Nature Link
Log in

Computing Dependencies Using FCA

  • Chapter
  • First Online:
Complex Data Analytics with Formal Concept Analysis

Abstract

Constraints, in a broad sense, are restrictions that exist (or should exist) in a dataset. There are many different kinds of constraints, that differ not only in their semantics, but also, in the domains in which they are present: database design, knowledge discovery, data analysis, to name a few. Formal Concept Analysis and Pattern Structures has been used to characterize and compute different kinds of constraints. The fact that this unified framework can embrace all this diversity has been an appealing line of research during the last years. In this paper we revisit some of our relevant results in this field. Moreover, we also discuss limitations and drawbacks and suggest possible directions within this field.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 18303
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 22879
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 22879
Price includes VAT (Japan)
  • Durable hardcover 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

Similar content being viewed by others

References

  1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, Reading (MA), USA, 1995.

    MATH  Google Scholar 

  2. J. Baixeries. A formal concept analysis framework to model functional dependencies. In Mathematical Methods for Learning, 2004.

    Google Scholar 

  3. J. Baixeries. Lattice Characterization of Armstrong and Symmetric Dependencies (PhD Thesis). Universitat Politècnica de Catalunya, 2007.

    Google Scholar 

  4. J. Baixeries. A Formal Context for Symmetric Dependencies, pages 90–105. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.

    MATH  Google Scholar 

  5. J. Baixeries. A formal context for acyclic join dependencies. In M. Kryszkiewicz, A. Appice, D. Ślezak, H. Rybinski, A. Skowron, and Z. W. Raś, editors, Foundations of Intelligent Systems, pages 563–572, Cham, 2017. Springer International Publishing.

    Google Scholar 

  6. J. Baixeries and J. L. Balcázar. Characterization and armstrong relations for degenerate multivalued dependencies using formal concept analysis. In B. Ganter and R. Godin, editors, ICFCA, volume 3403 of Lecture Notes in Computer Science, pages 162–175. Springer, 2005.

    Google Scholar 

  7. J. Baixeries and J. L. Balcázar. A lattice representation of relations, multivalued dependencies and armstrong relations. In ICCS, pages 13–26, 2005.

    Google Scholar 

  8. J. Baixeries, V. Codocedo, M. Kaytoue, and A. Napoli. Characterizing approximate-matching dependencies in formal concept analysis with pattern structures. Discrete Applied Mathematics, 249:18 – 27, 2018. Concept Lattices and Applications: Recent Advances and New Opportunities.

    Google Scholar 

  9. J. Baixeries, M. Kaytoue, and A. Napoli. Computing functional dependencies with pattern structures. In L. Szathmary and U. Priss, editors, CLA, volume 972 of CEUR Workshop Proceedings, pages 175–186. CEUR-WS.org, 2012.

    Google Scholar 

  10. J. Baixeries, M. Kaytoue, and A. Napoli. Computing similarity dependencies with pattern structures. In M. Ojeda-Aciego and J. Outrata, editors, CLA, volume 1062 of CEUR Workshop Proceedings, pages 33–44. CEUR-WS.org, 2013.

    Google Scholar 

  11. J. Baixeries, M. Kaytoue, and A. Napoli. Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures. Annals of Mathematics and Artificial Intelligence, 72(1–2):129–149, Oct. 2014.

    Article  MathSciNet  Google Scholar 

  12. R. Belohlávek and V. Vychodil. Data tables with similarity relations: Functional dependencies, complete rules and non-redundant bases. In M.-L. Lee, K.-L. Tan, and V. Wuwongse, editors, DASFAA, volume 3882 of Lecture Notes in Computer Science, pages 644–658. Springer, 2006.

    Google Scholar 

  13. M. Baudinet, J. Chomicki, and P. Wolper. Constraint-generating dependencies. J. Comput. Syst. Sci., 59(1):94–115, 1999.

    Article  MathSciNet  Google Scholar 

  14. L. Bertossi, S. Kolahi, and L. V. S. Lakshmanan. Data cleaning and query answering with matching dependencies and matching functions. In Proceedings of the 14th International Conference on Database Theory, ICDT ’11, pages 268–279, New York, NY, USA, 2011. ACM.

    Google Scholar 

  15. P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Conditional functional dependencies for data cleaning. In ICDE, pages 746–755, 2007.

    Google Scholar 

  16. L. Caruccio, V. Deufemia, and G. Polese. Relaxed functional dependencies - A survey of approaches. IEEE Trans. Knowl. Data Eng., 28(1):147–165, 2016.

    Article  Google Scholar 

  17. N. Caspard and B. Monjardet. The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey. Discrete Applied Mathematics, 127(2):241–269, 2003.

    Article  MathSciNet  Google Scholar 

  18. V. Codocedo, J. Baixeries, M. Kaytoue, and A. Napoli. Characterization of Order-like Dependencies with Formal Concept Analysis. In M. Huchard and S. Kuznetsov, editors, Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications, Moscow, Russia, July 18–22, 2016., volume 1624 of CEUR Workshop Proceedings, pages 123–134. CEUR-WS.org, 2016.

    Google Scholar 

  19. V. Codocedo, J. Baixeries, M. Kaytoue, and A. Napoli. Contributions to the Formalization of Order-like Dependencies using FCA. In What can FCA do for Artificial Intelligence?, The Hague, Netherlands, Aug. 2016.

    Google Scholar 

  20. J. Demetrovics, G. Hencsey, L. Libkin, and I. B. Muchnik. Normal form relation schemes: A new characterization. Acta Cybern., 10(3):141–153, 1992.

    MathSciNet  MATH  Google Scholar 

  21. W. Fan, H. Gao, X. Jia, J. Li, and S. Ma. Dynamic constraints for record matching. The VLDB Journal, 20(4):495–520, Aug. 2011.

    Article  Google Scholar 

  22. A. Floratou, N. Teletia, D. J. DeWitt, J. M. Patel, and D. Zhang. Can the elephants handle the nosql onslaught? Proc. VLDB Endow., 5(12):1712–1723, Aug. 2012.

    Article  Google Scholar 

  23. B. Ganter and S. O. Kuznetsov. Pattern Structures and Their Projections. In Proceedings of ICCS 2001, Lecture Notes in Computer Science 2120, pages 129–142. Springer, 2001.

    Google Scholar 

  24. B. Ganter and R. Wille. Formal Concept Analysis. Springer, Berlin, 1999.

    Book  Google Scholar 

  25. J.-L. Guigues and V. Duquenne. Familles minimales d’implications informatives résultant d’un tableau de données binaires. Mathématiques et Sciences Humaines, 95:5–18, 1986.

    Google Scholar 

  26. M. Kaytoue, S. O. Kuznetsov, A. Napoli, and S. Duplessis. Mining gene expression data with pattern structures in Formal Concept Analysis. Information Sciences, 181(10):1989–2001, 2011.

    Article  MathSciNet  Google Scholar 

  27. S. O. Kuznetsov. Machine learning on the basis of formal concept analysis. Autom. Remote Control, 62(10):1543–1564, Oct. 2001.

    Article  MathSciNet  Google Scholar 

  28. S. O. Kuznetsov. Pattern Structures for Analyzing Complex Data. In H. Sakai, M. K. Chakraborty, A. E. Hassanien, D. Slezak, and W. Zhu, editors, RSFDGrC, volume 5908 of Lecture Notes in Computer Science, pages 33–44. Springer, 2009.

    Google Scholar 

  29. S. Lopes, J.-M. Petit, and L. Lakhal. Functional and approximate dependency mining: database and fca points of view. Journal of Experimental and Theoretical Artificial Intelligence, 14(2–3):93–114, 2002.

    Article  Google Scholar 

  30. D. Maier. The Theory of Relational Databases. Computer Science Press, 1983.

    MATH  Google Scholar 

  31. H. Mannila and K.-J. Räihä. The Design of Relational Databases. Addison-Wesley, Reading (MA), USA, 1992.

    MATH  Google Scholar 

  32. R. Medina and L. Nourine. Conditional functional dependencies: An fca point of view. In L. Kwuida and B. Sertkaya, editors, ICFCA, volume 5986 of Lecture Notes in Computer Science, pages 161–176. Springer, 2010.

    Google Scholar 

  33. S. Song and L. Chen. Efficient discovery of similarity constraints for matching dependencies. Data & Knowledge Engineering, 87(0):146 – 166, 2013.

    Google Scholar 

  34. S. Song, L. Chen, and P. S. Yu. Comparable dependencies over heterogeneous data. The VLDB Journal, 22(2):253–274, Apr. 2013.

    Article  Google Scholar 

  35. J. Ullman. Principles of Database Systems and Knowledge-Based Systems, volumes 1–2. Computer Science Press, Rockville (MD), USA, 1989.

    Google Scholar 

  36. R. Wille. Why can concept lattices support knowledge discovery in databases? Journal of Experimental and Theoretical Artificial Intelligence, 14(2–3):81–92, 2002.

    Article  Google Scholar 

Download references

Acknowledgements

This research was supported by the recognition of 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya), and the grant TIN2017-89244-R from MINECO (Ministerio de Economía y Competitividad).

Author information

Authors and Affiliations

  1. Computer Science Department, Universitat Politècnica de Catalunya, Barcelona, Spain

    Jaume Baixeries

  2. Departamento de Informática, Universidad Técnica Federico Santa María, Campus San Joaquín, Santiago de Chile, Chile

    Victor Codocedo

  3. Infologic R&D, Bourg-Lès-Valence, France

    Mehdi Kaytoue

  4. Université de Lorraine, CNRS, Nancy, France

    Amedeo Napoli

Authors
  1. Jaume Baixeries
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Victor Codocedo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mehdi Kaytoue
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Amedeo Napoli
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jaume Baixeries .

Editor information

Editors and Affiliations

  1. University of Quebec in Outaouais, Gatineau, QC, Canada

    Rokia Missaoui

  2. Bern University of Applied Sciences, Bern, Switzerland

    Léonard Kwuida

  3. Place Marguerite Perey, Télécom-Paris, Institut Polytechnique, Palaiseau, France

    Talel Abdessalem

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Baixeries, J., Codocedo, V., Kaytoue, M., Napoli, A. (2022). Computing Dependencies Using FCA. In: Missaoui, R., Kwuida, L., Abdessalem, T. (eds) Complex Data Analytics with Formal Concept Analysis. Springer, Cham. https://doi.org/10.1007/978-3-030-93278-7_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-93278-7_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-93277-0

  • Online ISBN: 978-3-030-93278-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics