dc.contributor.author | Hermo Huguet, Montserrat | |
dc.contributor.author | Ozaki, Ana | |
dc.date.accessioned | 2024-02-02T17:15:29Z | |
dc.date.available | 2024-02-02T17:15:29Z | |
dc.date.issued | 2017-12-01 | |
dc.identifier.citation | Theoretical Computer Science 716 : 4-14 (2018) | es_ES |
dc.identifier.issn | 0304-3975 | |
dc.identifier.uri | http://hdl.handle.net/10810/64602 | |
dc.description.abstract | The transformation of a relational database schema into the 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. | es_ES |
dc.description.sponsorship | Hermo was supported by the Spanish Project TIN2013-46181-C2-2-R, the Basque Project GIU12/26 and grant UFI11/45. Ozaki was supported by the Science with-out Borders scholarship programme 245288/2012-0 | es_ES |
dc.language.iso | eng | es_ES |
dc.publisher | Elsevier | es_ES |
dc.rights | info:eu-repo/semantics/openAccess | es_ES |
dc.subject | exact learning | es_ES |
dc.subject | multivalued dependencies | es_ES |
dc.subject | 2-quasi-horn | es_ES |
dc.title | Exact learning of multivalued dependency formulas | es_ES |
dc.type | info:eu-repo/semantics/preprint | es_ES |
dc.rights.holder | © 2017 Elsevier B.V. | es_ES |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0304397517308484 | es_ES |
dc.identifier.doi | 10.1016/j.tcs.2017.11.018 | |
dc.departamentoes | Lenguajes y sistemas informáticos | es_ES |
dc.departamentoeu | Hizkuntza eta sistema informatikoak | es_ES |