💻 computer science

Common Foundations for Recursive Shape Languages

تتناول هذه الورقة التباعد الدلالي بين لغتي المخططات الشاملة (ShEx) و(SHACL) العودية من خلال تقديم إطار رسمي موحد يوضح العلاقات بين دلالات النقطة الثابتة الدنيا والنقطة الثابتة العليا، ويثبت وجود أجزاء متكافئة تعبيرياً بين المعيارين، ويحلل التعقيدات الحسابية الخاصة بكل منهما.

المؤلفون الأصليون: Shqiponja Ahmetaj, Iovka Boneva, Jan Hidders, Maxime Jakubowski, Jose-Emilio Labra-Gayo, Wim Martens, Fabio Mogavero, Filip Murlak, Cem Okulmus, Ognjen Savković, Mantas Šimkus, Dominik Tomaszuk

نُشر 2026-04-24

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Shqiponja Ahmetaj, Iovka Boneva, Jan Hidders, Maxime Jakubowski, Jose-Emilio Labra-Gayo, Wim Martens, Fabio Mogavero, Filip Murlak, Cem Okulmus, Ognjen Savković, Mantas Šimkus, Dominik Tomaszuk

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تقوم ببناء مدينة ضخمة ومترابطة من المعلومات تسمى رسم البياني RDF. في هذه المدينة، كل مبنى (نقطة بيانات) متصل بغيره عبر طرق (علاقات). وللحفاظ على تنظيم هذه المدينة، تحتاج إلى كتيب قواعد لمخطط المدينة (لغة مخطط) يخبرك بما يجعل المبنى صالحاً.

لقد وضع مجموعتان رئيستان من المهندسين المعماريين كتيبات القواعد الخاصة بهما لهذه المدينة: ShEx و SHACL.

لفترة طويلة، عملت هذه الكتيبات بشكل جيد للطرق البسيطة والمستقيمة. ولكن مؤخراً، بدأت المدينة تصبح معقدة مع ظهور الحلقات (طرق تدور حول نفسها) و القواعد التكرارية (قواعد تشير إلى نفسها، مثل "المبنى يكون صالحاً إذا كان متصلاً بمبنى آخر صالح").

هنا بدأت الأمور تصبح فوضوية. هذه الورقة البحثية التي طلبتها هي عبارة عن فريق من الخبراء من جميع أنحاء العالم اجتمعوا لحل سوء فهم هائل بين هاتين المجموعتين. إليك القصة عما وجدوه، مشروحة ببساطة.

المشكلة الجوهرية: حيرة "من على الخط الأول؟"

تخيل أنك تحاول تحديد قاعدة لـ "مبنى آمن".

فريق ShEx يقول: "المبنى يكون آمناً إذا يمكن أن يكون جزءاً من حلقة آمنة. نحن نبحث عن أكبر مجموعة ممكنة من المباني الآمنة". (يسمون هذا النقطة الثابتة الكبرى أو GFP).
فريق SHACL يجادل حول الأمر. البعض يقول: "المبنى يكون آمناً فقط إذا استطعنا إثبات أنه آمن خطوة بخط الخطوة انطلاقاً من لا شيء". (إنهم يميلون نحو النقطة الثابتة الصغرى أو LFP).
آخرون يقولون: "دعونا نختار أي مجموعة من المباني تبدو منطقية، حتى لو كانت هناك طرق متعددة للقيام بذلك". (هذا هو دلالات النموذج المدعوم أو SMS).

النتيجة: نظرًا لأنهم يستخدمون تعريفات مختلفة لـ "الصلاحية"، فقد يتم الموافقة على نفس المبنى من قبل مدقق ShEx ورفضه من قبل مدقق SHACL. إنه يشبه شرطيي مرور يعطيان اتجاهات متضادة لنفس السائق. هذا يكسر قدرة المدينة على التواصل مع نفسها (التوافق التشغيلي).

التحقيق: "اختبار التذوق"

لم يكتفِ المؤلفون بالحديث عن النظرية فحسب؛ بل بنوا اختبار تذوق (مجموعة من 13 حالة اختبار محددة). قاموا بتغذية هذه الاختبارات في أدوات التحقق (المدققات) الفعلية التي يستخدمها الناس اليوم.

ما وجدوه:

أدوات ShEx: جميعها متسقة. جميعها تتبع قاعدة "أكبر مجموعة" (GFP). إنهم مثل جوقة غنائية تغني في تناغم تام.
أدوات SHACL: هي فرقة جاز فوضوية.
- بعض الأدوات تتبع قاعدة "خطوة بخوة" (LFP).
- بعضها يتبع قاعدة "اختر أي منطق" (Brave SMS).
- أداة واحدة (Topbraid) يبدو أن لديها كتيب قواعد سري خاص بها لا يتطابق مع أي شخص آخر.
- بعض الأدوات تنهار ببساد بمجرد رؤية حلقة.

الخلاصة: إذا كتبت قاعدة لـ SHACL اليوم، فأنت لا تعرف ما إذا كانت ستعمل غداً لأنك لا تعرف أي "نكهة" من المنطق يستخدمها المدقق الخاص بك.

الاكتشاف الكبير: "خدعة المرآة"

إليك الجزء الأكثر إثارة في الورقة البحثية. أدرك المؤلفون أنه بينما يبدو أن ShEx و SHACL يسيران في اتجاهين متعاكسين، إلا أنهما في الواقع صورتان مرآتيتان لبعضهما البعض.

التشبيه: تخيل أن ShEx ينظر إلى انعكاس في المرآة، و SHACL ينظر إلى الجسم الحقيقي.
إذا أخذت قاعدة ShEx (البحث عن "أكبر مجموعة") وقلبتها رأسا على عقب (نفيها)، فإنها تصبح مطابقة رياضياً لقاعدة SHACL التي تبحث عن "أصغر مجموعة".
لماذا يهم هذا: هذا يعني أنه رغم استخدام كلمات ومنطق مختلفين، فإن ShEx و SHACL في الواقع متساويان في القوة. يمكنهما وصف نفس الأشكال المعقدة في البيانات تماماً. إنهما فقط يتحدثان لهجات مختلفة.

تكلفة الارتباك: "القائمة الباهظة"

نظرت الورقة أيضاً في مدى صعوبة فحص هذه القواعد من قبل الحواسيب.

LFP و GFP (القواعد القياسية): هذه تشبه طلب برجر. يستغيث الأمر وقتاً وجهداً (قدرة حوسبية) يمكن التنبؤ به ومعقولاً للتحقق مما إذا كان المبنى صالحاً.
SMS (قاعدة "اختر أي منطق"): هذه تشبه طلب وجبة يتعين على الطاهي فيها تخمين كل التركيبات الممكنة للمكونات التي قد تنجح، وفحصها جميعاً، ثم اختيار واحدة. هذا باهظ التكلفة بشكل أسّي. يمكن أن يجعل الكمبيوتر ينهار أو يستغرق وقتاً طويلاً جداً للانتهاء، حتى بالنسبة للقواعد البسيطة.

الخلاوصة: "معاهدة سلام"

لقد توصل المؤلفون، الذين يضمون أشخاصاً ساعدوا في تصميم كل من ShEx و SHACL، إلى إجماع:

توقفوا عن الشجار: لا بأس أن يستمر ShEx في استخدام قاعدة "أكبر مجموعة" (GFP) وأن يتبنى SHACL قاعدة "أصغر مجموعة" (LFP).
المرآة حقيقية: لأن "خدعة المرآة" موجودة، يمكن لهذين النهجين المختلفين التعامل مع نفس البيانات المعقدة والتواصل مع بعضهما البعض.
تجنب الخيار المكلف: هم ينصحون بشدة بعدم استخدام نهج "اختر أي منطق" (SMS) لأنه بطيء وغير قابل للتنبؤ للاستخدام في العالم الحقيقي.

باختاًصر: تقول الورقة البحثية: "لا تقلقوا. كتيبات القواعد الرئيسية متوافقة في الواقع إذا فهمنا أنها مرايا لبعضها البعض. دعونا نتوحد على القواعد السريعة والقابلة للتنبؤ ونتوقف عن ترك أدوات البرمجيات تخمن ما يجب أن تفعله".

إليك ملخص تقني مفصل لورقة البحث بعنوان "الأسس المشتركة للغات الأشكال العودية" (Common Foundations for Recursive Shape Languages).

1. بيان المشكلة

مع نضوج لغات المخططات (Schema Languages) لبيانات RDF (تحديداً ShEx و SHACL)، تبرز حاجة ماسة للتعامل مع العودية (Recursion) لتعريف التبعيات الدورية. ومع ذلك، فقد تباعدت اللغتان في نهجهما الدلالي تجاه العودية، مما خلق مشكلات في التوافق التشغيلي وعدم القدرة على التنبؤ:

ShEx: تتبنى رسمياً دلالات النقطة الثابتة الكبرى (Greatest Fixpoint - GFP).
SHACL: لا تزال دلالاتها غير محددة في توصية W3C، بينما تميل المقترحات الأكاديمية نحو النقطة الثابتة الصغرى (Least Fixpoint - LFP) أو دلالات النموذج المدعوم (Supported Model Semantics - SMS).
الصراع: يكشف دراسة عملية أن أدوات التحقق الحالية تنفذ هذه الدلالات بشكل غير متسق. تتبع أدوات التحقق من ShEx عموماً دلالات GFP، بينما تتسم أدوات التحقق من SHACL بعدم التجانس (بعضها يتبع SMS "الجريء" Brave SMS، والبعض الآخر يفشل أو يتصرف بشكل غير متوقع). هذا التباعد يقوض موثوقية أدوات التحقق ويعيق الانتقال بين أطر العمل.

2. المنهجية

يستخدم المؤلفون نهجاً متعدد الأوجه يجمع بين المنطق الصوري، ونظرية التعقيد، والتجريب العملي:

إطار عمل توحيدي صوري (SSL): قدموا لغة "الشكل البسيط" (Simple Shape Language - SSL)، وهي لغة أساسية دنيا تلتقط جوهر كل من ShEx و SHACL. تتضمن SSL أسماء الأشكال، والنفي، والاقتران، والترابط، والوجودية/الكلية على المحمولات (Predicates).
التعريف الدلالي: حددوا رسمياً ثلاث دلالات عودية على SSL:
1. دلالات النموذج المدعوم (SMS): تسمح بأي تعيين صحيح (غير حتمي).
2. النقطة الثابتة الصغرى (LFP): تختار الحد الأدنى من التعيينات الصحيحة.
3. النقطة الثابتة الكبرى (GFP): تختار الحد الأقصى من التعيينات الصحيحة.
- استخدموا الطبقية (Stratification) للتعامل مع النفي بطريقة منضبطة، مما يضمن دلالات محددة جيداً لجميع المناهج الثلاثة.
مبدأ الثنائية: أثبتوا وجود ثنائية صورية بين LFP و GFP في الأجزاء الطبقية، مبرهنين أنهما متساويان في القدرة التعبيرية عبر ترجمة مباشرة (تبديل $\top/\bot$ ، و $\land/\lor$ ، و $\exists/\forall$ ).
التحقق التجريبي: صمموا 13 حالة اختبار (اختبارات الفصل واختبارات الميزات) لاستقصاء سلوك أدوات التحقق الواقعية. تميز هذه الاختبارات بين LFP و GFP و Brave SMS و Cautious SMS.
تحليل التعقيد: أجروا تحليلاً صارماً لـ تعقيد البيانات (Data Complexity) (مخطط ثابت، بيانات متغيرة) و التعقيد المشترك (Combined Complexity) (تغير كل من المخطط والبيانات) لجميع الدلالات عبر SSL و ShEx و SHACL.

3. المساهمات الرئيسية

أ. التوحيد الصوري والثنائية

توفر الورقة إطاراً توحيدياً يوضح أن SSL مع LFP تمتلك نفس القدرة التعبيرية لـ SSL مع GFP بسبب مبدأ الثنائية.
يعني هذا أنه رغم استخدام ShEx لـ GFP وربما توجه SHACL نحو LFP، فإنهما يمكنهما التعبير عن نفس مجموعة القيود (تحديداً الجزء الخالي من التناوب من حساب $\mu$ -calculus مع الـ nominals).

ب. التحليل التجريبي لأدوات التحقق

اختبر المؤلفون أدوات التحقق الرئيسية:

أدوات التحقق من ShEx (مثل rudof، و Jena ShEx، و ShEx-S): تتبع باستمرار GFP، بما يتماشى مع دلالات ShEx الرسمية.
أدوات التحقق من SHACL (مثل pySHACL، و SHACL-S، و Jena SHACL، و rudof): تتماشى في الغالب مع Brave SMS (تقبل الرسم البياني إذا وجد بعض التعيينات الصحيحة)، رغم أن السلوك غير متسق.
Topbraid: تتبع دلالات فريدة وغير محددة لا تطابق LFP أو GFP أو متغيرات SMS القياسية.
اختبارات الميزات: تسلط الدراسة الضوء على أن العديد من أدوات التحقق تفشل في التعامل مع النفي غير الطبقي أو فحوصات الاتساق المحددة، مما يكشف عن فجوات في التنفيذ.

ج. تكافؤ القدرة التعبيرية

عرف المؤلفون Restricted ShEx (مع GFP) و Restricted SHACL (مع LFP).
أثبتوا المبرهنة 1: هذه الأجزاء المقيدة لها قدرة تعبيرية متطابقة وتسمح بترجمات ذهاب وإياب فعالة. يشير هذا إلى أن الاختيار بين LFP و GFP لا يحد من أنواع القيود التي يمكن التعبير عنها، بل يغير فقط تفسير التعريفات الدورية.

د. نتائج التعقيد

وضعت الورقة حدوداً دقيقة للتعقيد (ملخصة في الجدول 3 من الورقة):

LFP و GFP: كلاهما يسمح بـ وقت متعدد الحدود (Polynomial Time - P) لتعقيد البيانات لـ SSL و SHACL و ShEx.
SMS: يؤدي إلى تعقيد بيانات من فئة NP-complete حتى بالنسبة للغة SSL البسيطة.
التعقيد المشترك: LFP/GFP هي من فئة $P^{NP}$ -complete لـ ShEx، بينما SMS هي من فئة $NP^{NP}$ -complete.
الاستنتاج: تعتبر SMS غير قابلة للتتبع حسابياً مقارنة بدلالات النقطة الثابتة، مما يجعل LFP و GFP متفوقة من الناحية العملية.

4. النتائج

عدم تجانس أدوات التحقق: لا يوجد سلوك موحد في أدوات التحقق من SHACL فيما يتعلق بالعودية. بعضها يرفض المخططات العودية تماماً؛ والبعض الآخر ينفذ Brave SMS؛ ولا يوجد أي منها ينفذ LFP بصرامة بشكل افتراضي.
التوافق التشغيلي: يسبب التباعد في الدلالات (GFP مقابل LFP مقابل SMS) التحقق من نفس المخطط بشكل مختلف على محركات مختلفة، مما يكسر التوافق التشغيلي.
الجدوى: تعتبر LFP و GFP قابلة للتنفيذ خوارزمياً (وقت متعدد الحدود لتعقيد البيانات)، بينما تعتبر SMS غير قابلة للتتبع حسابياً.
التوافق: رغم التباعد الدلالي، فإن القدرة التعبيرية لـ ShEx (GFP) و SHACL (LFP) تتداخل بشكل كبير للأجزاء الطبقية.

5. الأهمية والتوصيات

التقنين (Standardization): يخلص المؤلفون، الذين يمثلون مساهمين في كل من ShEx و SHACL، إلى أنه من المقبول أن تعتمد SHACL نظام LFP بينما تحتفظ ShEx بنظام GFP. يضمن مبدأ الثنائية بقاء اللغتين متكافئتين تعبيرياً لجزء كبير ومفيد من المخططات.
التوصية: يجب على المجتمع الابتعاد عن دلالات النموذج المدعوم (SMS) بسبب تكلفتها الحسابية العالية وعدم حتميتها. ويُنصح باستخدام LFP و GFP كمعيار للعودية في كلتا اللغتين.
العمل المستقبلي: توفر هذه النتائج أساساً لمجموعة عمل W3C لإنهاء دلالات العودية في SHACL، مما يضمن أدوات تحقق متوقعة، متوافقة تشغيلياً، وفعالة حسابياً.

باخت-صار، تحل الورقة غموضاً نظرياً وعملياً حرجاً في لغات مخططات الرسوم البيانية من خلال إثبات أن LFP و GFP هما ثنائيان بقدة تعبيرية متساوية، وتوضيح أن تطبيقات SHACL الحالية غير متسقة وغالباً ما تكون غير فعالة (بسبب SMS)، والدعوة إلى اعتماد معيار دلالات النقطة الثابتة لضمان توافق تشغيلي قوي.