کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429037 687010 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of tree pattern containment with arithmetic comparisons
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the complexity of tree pattern containment with arithmetic comparisons
چکیده انگلیسی

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
نویسندگان
, , ,