کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427222 | 686473 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A dichotomy in the complexity of consistent query answering for queries with two atoms
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We establish a dichotomy in the complexity of computing the consistent answers of a Boolean conjunctive query with exactly two atoms and without self-joins. Specifically, we show that the problem of computing the consistent answers of such a query either is in P or it is coNP-complete. Moreover, we give an efficiently checkable criterion for determining which of these two possibilities holds for a given query.
► Complexity of consistent answers of self-join free conjunctive queries with two atoms.
► Dichotomy theorem for the complexity established.
► Computing the certain answers either is in P or it is coNP-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 3, 31 January 2012, Pages 77–85
Journal: Information Processing Letters - Volume 112, Issue 3, 31 January 2012, Pages 77–85
نویسندگان
Phokion G. Kolaitis, Enela Pema,