کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429037 | 687010 | 2011 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of tree pattern containment with arithmetic comparisons
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is Π2P-complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (<, ⩽, =) or right semi-interval (>, ⩾, =) attribute constraints.
► Query containment for tree patterns with arithmetic comparisons is studied.
► Query containment is Π2P-complete in the general case.
► For left (or right) semi-interval constraints, query containment is NP-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 15, 15 August 2011, Pages 754–760
Journal: Information Processing Letters - Volume 111, Issue 15, 15 August 2011, Pages 754–760
نویسندگان
Foto N. Afrati, Sara Cohen, Gabriel Kuper,