في عالم الذكاء الاصطناعي، تتزايد الحاجة إلى أدوات فعّالة للإجابة على استعلامات المعرفة. تركز هذه الدراسة على استعلامات مسارات ثنائية-Regualar Path Queries ((C)RPQs) التي تُستخدم للإجابة عن استعلامات معرفية تتضمن قاعدة بيانات وأنتولوجيا. تعتبر هذه الاستعلامات مهمة للغاية، خاصة عندما يتعلق الأمر بالاستعلامات التنقلية.

بدأ الباحثون بدراسة التعقيد المرتبط بالإجابة عن استعلامات (C)RPQs في سياق قواعد المعرفة التي يجري تحديدها بواسطة مجموعة من القواعد الوجودية الحارسة. وقد أظهروا أن الإجابة عن الاستعلامات من هذا النوع تتمتع بتعقيد NL-complete في سياق البيانات، مما يعني أن التعقيد يظل مماثلاً لما هو موجود في قواعد البيانات العادية.

ومع ذلك، في حالة التعقيد المشترك، نجد أن مهام الإجابة تتطور لتصبح ExpTime-complete في الحالة العامة. لكن، عند وجود حد معين على عدد علاقات البدايات، تنخفض الصعوبة لتصبح PTime-complete و PSpace-complete على التوالي.

من المثير للاهتمام أنه عند تناول القواعد الحارسة، قام الباحثون بتوفير تخفيض غير تافه إلى الحالة الخطية، مما سمح بتحديد أن تعقيد الإجابة عن (C)RPQs يتساوى مع تعقيد الإجابة عن استعلامات تفصيلية (CQs)، ويبلغ مستوى تعقيدها 2ExpTime-complete في التعقيد المشترك (ExpTime-complete في الحالات ذات الحد).

هذا التطور يشير إلى أهمية القواعد الوجودية الحارسة في تحسين كفاءة استعلامات المعرفة وفتح آفاق جديدة في تحليل البيانات.