کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428604 686835 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Negative results on learning multivalued dependencies with queries
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Negative results on learning multivalued dependencies with queries
چکیده انگلیسی

Data dependencies are useful to design relational databases. There is a strong connection between 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 learnable in the exact model of learning with queries. Here we proof that neither multivalued formulas nor multivalued dependencies can be learned using only membership queries or only equivalence queries.


► We study multivalued formulas and multivalued dependencies in the model of learning with queries.
► We prove that none of these classes are learnable with only membership queries.
► We also prove that they cannot be learned with equivalence queries alone.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 19, 15 October 2011, Pages 968–972
نویسندگان
, ,