Article3034: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 7: | Zeile 7: | ||
|Referiert=0 | |Referiert=0 | ||
|Title=Exact Learning of Multivalued Dependency Formulas | |Title=Exact Learning of Multivalued Dependency Formulas | ||
|To appear= | |To appear=0 | ||
|Year=2017 | |Year=2017 | ||
|Month=Dezember | |||
|Journal=Theoretical Computer Science | |Journal=Theoretical Computer Science | ||
}} | }} | ||
| Zeile 14: | Zeile 15: | ||
|Abstract=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 | |Abstract=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. | 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. | ||
|DOI Name=https://doi.org/10.1016/j.tcs.2017.11.018 | |||
|Projekt=Cfaed | |||
|Forschungsgruppe=Wissensbasierte Systeme | |Forschungsgruppe=Wissensbasierte Systeme | ||
}} | }} | ||
Version vom 2. Dezember 2017, 13:26 Uhr
Exact Learning of Multivalued Dependency Formulas
Montserrat HermoMontserrat Hermo, Ana OzakiAna Ozaki
Montserrat Hermo, Ana Ozaki
Exact Learning of Multivalued Dependency Formulas
Theoretical Computer Science, December 2017
Exact Learning of Multivalued Dependency Formulas
Theoretical Computer Science, December 2017
- 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. - Projekt:Project: Cfaed
- Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@article{HO2017,
author = {Montserrat Hermo and Ana Ozaki},
title = {Exact Learning of Multivalued Dependency Formulas},
journal = {Theoretical Computer Science},
year = {2017},
month = {December},
doi = {https://doi.org/10.1016/j.tcs.2017.11.018}
}
