<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Artículo:
Learning a Subclass of Multivalued Dependencies Formulas from Entailments

Cargando...
Miniatura

Editor

Sistedes

Publicado en

Actas de las XV Jornadas de Programación y Lenguajes (PROLE 2015)

Licencia Creative Commons

Excepto donde se indique lo contrario, la licencia de este ítem se describe como CC BY 4.0

Resumen

Functional and multivalued dependencies play an important role in the design of relational databases. There is a strong connection between data dependencies and some fragments of the propositional logic. In particular, functional dependencies are closely related to Horn formulas. Also, multivalued dependencies are characterized in terms of multivalued formulas. It is known that both Horn formulas and sets of functional dependencies are efficiently learnable in the exact model of learning with queries. In this work, we study the learnability of a non-trivial subclass of multivalued formulas called CRMVDF. We use Angluin’s exact learning model with membership and equivalence queries and present a polynomial time algorithm which exactly learns CRMVDF from entailments.

Descripción

Acerca de Hermo, Montserrat

Palabras clave

Citación

Hermo, M., Ozaki, A.: Learning a Subclass of Multivalued Dependencies Formulas from Entailments. In: Navarro, M. (ed.) Actas de las XV Jornadas de Programación y Lenguajes (PROLE 2015). Sistedes (2015). https://hdl.handle.net/11705/PROLE/2015/019