Exact Learning of Multivalued Dependencies

From International Center for Computational Logic

Toggle side column

Exact Learning of Multivalued Dependencies

Montserrat HermoMontserrat Hermo,  Ana OzakiAna Ozaki
Exact Learning of Multivalued Dependencies


Montserrat Hermo, Ana Ozaki
Exact Learning of Multivalued Dependencies
Algorithmic Learning Theory - 26th International Conference, October 2015. Springer
  • KurzfassungAbstract
    The transformation of a relational database schema into fourth normal form, which minimizes data redundancy, relies on the correct identification of multivalued dependencies. In this work, we study the learnability of multivalued dependency formulas (MVDF), which correspond to the logical theory behind multivalued dependencies. As we explain, MVDF lies between propositional Horn and 2-Quasi-Horn. We prove that MVDF is polynomially learnable in Angluin et al.’s exact learning model with membership and equivalence queries, provided that counterexamples and membership queries are formulated as 2-Quasi-Horn clauses. As a consequence, we obtain that the subclass of 2-Quasi-Horn theories which are equivalent to MVDF is polynomially learnable.
  • Bemerkung: Note: Our work received the E.M Gold Award in ALT 2015.
  • Forschungsgruppe:Research Group: Wissensbasierte Systeme
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-24486-0.
@inproceedings{HO2015,
  author    = {Montserrat Hermo and Ana Ozaki},
  title     = {Exact Learning of Multivalued Dependencies},
  booktitle = {Algorithmic Learning Theory - 26th International Conference},
  publisher = {Springer},
  year      = {2015},
  month     = {October},
  doi       = {10.1007/978-3-319-24486-0}
}