کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6853150 | 658310 | 2016 | 42 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Games for query inseparability of description logic knowledge bases
ترجمه فارسی عنوان
بازی برای پرس و جو جداسازی پایگاه های منطق توضیح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
منطق توصیف دانش محور، پرس و جو متقابل، تقسیمپذیری پرس و جو، بازی در گراف، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
چکیده انگلیسی
We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature-a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-ALCHI, including the description logics underpinning OWLâ2âQL and OWLâ2âEL. We also determine the data and combined complexity of deciding query inseparability. While query inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWLâ2âQL by showing that TBox query inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 234, May 2016, Pages 78-119
Journal: Artificial Intelligence - Volume 234, May 2016, Pages 78-119
نویسندگان
Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev,