💻 computer science

Multiset semantics in SPARQL, Relational Algebra and Datalog

تُثبت هذه الورقة التكافؤ التعبيري بين دلالات المجموعات المتعددة لـ SPARQL، ولغة Datalog غير العودية الممتدة للمجموعات المتعددة مع النفي الآمن، وجبر العلاقات متعدد المجموعات، وذلك من خلال توصيف هياكلهم الجبرية والمنطقية المشتركة لمشغلات الاستعلام الأساسية.

المؤلفون الأصليون: Renzo Angles, Claudio Gutierrez, Daniel Hernández

نُشر 2026-05-04

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

CC BY 4.0

المؤلفون الأصليون: Renzo Angles, Claudio Gutierrez, Daniel Hernández

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

تخيل أنك تدير مكتبة ضخمة حيث ليست الكتب مجرد عناصر فريدة على الرف، بل هي أكوام من النسخ المتطابقة. أحياناً تريد معرفة كم عدد النسخ التي تملكها من كتاب معين، وليس فقط ما إذا كنت تملك نسخة واحدة منه. في عالم قواعد البيانات، يُسمى هذا المفهوم المجموعة متعددة العناصر (multiset) أو "الحقيبة" (bag). وعلى عكس المجموعة القياسية (set) حيث يتم التخلص من النسخ المكررة، فإن المجموعة متعددة العناصر تتبع كل نسخة بمفردها.

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

إليك تفصيل نتائجهم باستخدام تشبيهات بسيطة:

1. المشكلة: ارتباك "الحقيبة"

تخيل أنك طاهٍ.

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

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

2. اللغات الثلاث في الحلبة

أقام المؤلفون "سباق ثلاثي" لمعرفة ما إذا كانت ثلاث لغات مختلفة يمكنها القيام بنفس المهمة وبنفس الدقة:

SPARQL: نجم العرض، وتُستخدم لبيانات الويب.
NRMD¬ (Datalog متعدد العناصر غير المتكرر مع النفي الآمن): فكر في هذا كحل للألغاز المنطقية. إنه يبني الإجابات خطوة بخطوة باستخدام القواعد، لكنه لا يسمح بالحلقات اللانهائية (غير متكرر) ويتعامل مع جمل "النفي" بعناية (نفي آمن).
MRA (الجبر العلائقي متعدد العناصر): هذه هي مجموعة الأدوات الرياضية. إنها تشبه مجموعة من العمليات الميكانيكية (مثل الخلاط، أو المنخل، أو الميزان) التي يمكنك تطبيقها على حقائب البيانات لخلطها، وتصفيتها، وعدّها.

3. الاكتشاف الكبير: جميعها هي نفسها

الادعاء الجوهري للورقة هو أن هذه اللغات الثلاث متكافئة رياضياً.

فكر في الأمر كأن ثلاثة مترجمين مختلفين يتحدثون ثلاث لغات مختلفة (الإسبانية، والفرنسية، والألمانية). لقد أثبت المؤلفون أنه إذا أخذت تعليمات معقدة مكتوبة بـ SPARQL، يمكنك ترجمتها تماماً إلى قواعد Datalog، ثم ترجمتها بعد ذلك إلى الجبر العلائقي، وستحصل على النتيجة نفسها تماماً في كل مرة. لا تُفقد أي معلومات، ولا يتم إفراغ "حقيبة" من البيانات أو ملؤها بنسخ إضافية عن طريق الخطأ.

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

4. لماذا هذا مهم (وفقاً للورقة)

لا يدعي المؤلفون أن هذا سيصلح فوراً خطأً برمجياً معيناً أو ينشئ تطبيقاً طبياً جديداً. بدلاً من ذلك، هم يركزون على الأساس النظري:

التحقق من الصحة: يثبت هذا أن SPARQL ليست مجرد لغة "مرتجلة"؛ بل لها عمود فقري رياضي رصين ومنضبط يطابق النظريات الراسخة.
الاتساق: وجدوا أن تصميم SPARQL هو في الواقع أكثر تماسكاً من SQL. فبينما تمتلك SQL طرقاً عديدة مختلفة للتعامل مع التكرارات (مما قد يكون مربكاً)، فإن العمليات الأساسية في SPARQL تشكل نظاماً منطقياً ونظيفاً.
التصميم المستقبلي: من خلال فهم أن SPARQL مكافئة لهذه النماذج الرياضية الأبسط والأكثر دراسة، يمكن لمصممي المستقبل بناء أدوات وتحسينات أفضل لـ SPARQL. إنه يشبه إدراك أن آلة معقدة هي في الواقع مجرد مزيج من تروس بسيطة وموثوقة.

الملخص

باختصار، هذه الورقة هي إثبات رياضي بأن طريقة تعامل SPARQL مع البيانات المكررة تتماشى تماماً مع أفضل نظريات رياضيات قواعد البيانات. لقد بنى المؤلفون جسراً بين لغة الاستعلام الخاصة بالويب (SPARQL)، والبرمجة المنطقية (Datalog)، والجبر العلائقي (Relational Algebra)، موضحين أن جميعها مجرد طرق مختلفة لوصف نفس الواقع الكامن. هذا يمنحنا الثقة في أن SPARQL قوية، وقابلة للتنبؤ، وسليمة من الناحية النظرية.

إليك ملخص تقني مفصل لورقة البحث بعنوان "دلالات المجموعات المتعددة في SPARQL، والجبر العلاقاتي، وDatalog"* من إعداد أنجلز، وغوتيريز، وهيرنانديز.

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

تتناول الورقة الأسس النظرية لـ دلالات المجموعات المتعددة (multiset semantics) في سياق لغة الاستعلام SPARQL لقواعد بيانات RDF. وبينما تُعد المجموعات المتعددة (التي تسمح بالعناصر المكررة) ميزة قياسية في أنظمة قواعد البيانات الحديثة (مثل SQL) نظراً للاحتياجات العملية (مثل التجميع، وتجنب حذف التكرارات المكلف)، فإن معالجتها النظرية في لغات الاستعلام التصريحية تعد أمراً معقداً.

تشمل التحديات الرئيسية المحددة ما يلي:

التباين الدلالي: لا يوجد إجماع واحد حول كيفية تمديد العمليات القائمة على المجموعات (الاتحاد، التقاطع، الفرق) لتشمل المجموعات المتعددة. توجد عمليات مختلفة (على سبيل المثال: الاتحاد الحسابي مقابل الاتحاد الأقصى، والفرق الحسابي مقابل النفي الوجودي).
فجوة القدرة التعبيرية: من غير الواضح ما إذا كانت المجموعة المحددة من عمليات المجموعات المتعددة التي تدعمها SPARQL (وهي: AND، UNION، FILTER، EXCEPT، SELECT) تشكل مجموعة مثالية أو متماسكة.
الافتقار إلى التكافؤ الرسمي: هناك حاجة لتوصيف القدرة التعبيرية لدلالات المجموعات المتعددة في SPARQL بدقة من خلال مقارنتها بالصيغ الرسمية الراسخة: الجبر العلاقاتي (Relational Algebra) و Datalog.

2. المنهجية

يستخدم المؤلفون تحليلاً رسمياً مقارناً لإثبات التكافؤ التعبيري بين ثلاث صيغ متميزة تحت دلالات المجموعات المتعددة:

SPARQL: وتحديداً "اللب العلاقاتي" (relational core) الذي يتضمن AND و UNION و FILTER و EXCEPT و SELECT.
NRMD¬ (Datalog للمجموعات المتعددة غير العودية مع النفي الآمن): صيغة منطقية تمدد Datalog لدعم المجموعات المتعددة والنفي الآمن، بناءً على الدلالات القائمة على نظرية الإثبات (عدّ أشجار الاشتقاق).
MRA (الجبر العلاقاتي للمجموعات المتعددة): صيغة جبرية تمدد الجبر العلاقاتي القياسي بعمليات المجموعات المتعددة (الإسقاط، الاختيار، الضرب المباشر الطبيعي، الاتحاد الحسابي، فرق التصفية).

النهج الجوهري:
يعرف المؤلفون المحاكاة (simulations) (الترجمة) بين هذه اللغات لإثبات أنها تمتلك نفس القدرة التعبيرية. ويتضمن ذلك تعريف ثلاث دوال لكل زوج من اللغات $(L_1, L_2)$ :

$g$ : ترجمة قاعدة البيانات (تحويل هياكل البيانات).
$f$ : ترجمة الاستعلام (تحويل بناء الجملة للاستعلام).
$h$ : ترجمة الإجابة (تحويل مجموعات النتائج).

ويثبتون أن $L_1$ محتواة في $L_2$ والعكس صحيح، مما يثبت أن $L_1 \equiv L_2$ .

التحديات التقنية الرئيسية التي تمت معالجتها:

التعامل مع القيم الفارغة/غير المقيدة: تمتلك خرائط SPARQL نطاقات جزئية (متغيرات غير مقيدة)، بينما تكون صفوف العلاقات وDatalog كليّة. لذا، استحدث المؤلفون ثابتاً خاصاً ( $\bot$ أو NULL) لتمثيل القيم غير المقيدة في اللغات المستهدفة.
المنطق ثلاثي القيم في المرشحات (Filters): تستخدم SPARQL منطقاً ثلاثي القيم (صواب، خطأ، خطأ/Error) للمرشحات. وقد طور المؤلفون قواعد إعادة كتابة محددة للتعامل مع OR و NOT في المرشحات تحت دلالات المجموعات (bags)، لضمان انتشار حالات "الخطأ" (Error) بشكل صحيح وعدم تضخيم أعداد العناصر (cardinalities) بشكل خاطئ.
التطبيع (Normalization): عرّف المؤلفون أشكالاً طبيعية (normal forms) لأنماط SPARQL وقواعد Datalog لضمان تحديد نطاق المتغيرات في الأنماط الفرعية بشكل صحيح قبل الترجمة.

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

أ. تعريف الصيغ

NRMD¬: عرّف المؤلفون نسخة من Datalog تدعم المجموعات المتعددة والنفي الآمن، مع قصرها على البرامج غير العودية لتتوافق مع قدرات SPARQL. وهم يستخدمون "المجموعات الملونة" لتتبع عدد الحقائق (الإثباتات).
MRA: عرّفوا الجبر العلاقاتي للمجموعات المتعددة الذي يتكون من:
- $\pi$ (الإسقاط): جمع أعداد عناصر الصفوف المسقطة.
- $\sigma$ (الاختيار): التصفية مع الحفاظ على العدد.
- $\bowtie$ (الضرب المباشر الطبيعي): ضرب أعداد العناصر المتوافقة.
- $\cup$ (الاتحاد الحسابي): جمع الأعداد.
- $\setminus$ (فرق التصفية): طرح الأعداد (مع التوقف عند الصفر).

ب. آليات الترجمة

تقدم الورقة خوارزميات دقيقة للترجمة بين اللغات الثلاث:

SPARQL $\leftrightarrow$ NRMD¬:
- من SPARQL إلى Datalog: تصبح أنماط الثلاثيات (triple patterns) ذرات (atoms)؛ وAND يصبح ضرباً مباشماً؛ وUNION يصبح قواعد متعددة؛ وEXCEPT يصبح نفياً؛ ويتم إعادة كتابة شروط FILTER للتعامل مع المنطق ثلاثي القيم والأخطاء صراحةً.
- من Datalog إلى SPARQL: يتم ترميز الحقائق كـ "ثلاثيات RDF" مع معرفات فريدة للحفاظ على التكرارات؛ وتُترجم القواعد إلى أنماط رسومية باستخدام AND و UNION و EXCEPT.
MRA $\leftrightarrow$ NRMD¬:
- يتم ربط العمليات العلاقاتية القياسية بقواعد Datalog (مثلاً: الضرب المباشر $\to$ ترابط جسم القاعدة).
- تُترجم قواعد Datalog إلى تعبيرات جبرية (مثلاً: النفي $\to$ فرق المجموعات).
SPARQL $\leftrightarrow$ MRA:
- تُترجم أنماط SPARQL إلى تعبيرات جبرية باستخدام علاقة Comp خاصة لمحاكاة فحص التوافق (للتعامل مع النطاقات الجزئية).
- تُترجم التعبيرات الجبرية مرة أخرى إلى أنماط SPARQL، باستخدام ثلاثيات NULL لإعادة بناء مخططات المتغيرات (variable schemas) للنتائج الفارغة.

ج. إثبات التكافؤ التعبيري

النتيجة النظرية المركزية هي مثلث التكافؤ:
$\text{SPARQL} \equiv \text{NRMD}^\neg \equiv \text{MRA}$
يثبت المؤلفون أن الجزء الجوهري من SPARQL (مع المجموعات المتعددة) مكافئ تعبيرياً لكل من Datalog للمجموعات المتعددة غير العودية مع النفي الآمن، والجبر العلاقاتي للمجموعات المتعددة.

4. النتائج

توصيف SPARQL: تكشف الدراسة أن دلالات المجموعات المتعددة للجزء الجوهري من SPARQL ليست عشوائية، بل تتوافق بدقة مع بنية منطقية وجبرية محددة جيداً.
تماسك العمليات: على عكس SQL، التي تدعم مجموعة متنوعة من عمليات المجموعات المتعددة (مثل max-union و min-intersection و arithmetic difference)، أظهرت الدراسة أن تصميم SPARQL هو مجموعة فرعية متماسكة. فهي تدعم الاتحاد الحسابي وفرق التصفية، لكنها تفتقر إلى max-union و min-intersection.
التعامل مع حالات "الخطأ" (Error): نجحت الورقة في صياغة كيفية تفاعل منطق SPARQL ثلاثي القيم (تحديداً حالة Error في المرشحات) مع أعداد عناصر المجموعات (cardinality)، حيث أظهرت أن التكافؤات الجبرية القياسية (مثل قوانين دي مورغان للاتحاد) لا تتحقق مباشرة في دلالات المجموعات (bags) دون إعادة كتابة محددة.

5. الأهمية والآثار المترتبة

الأساس النظري: يوفر هذا العمل أول توصيف جبري ومنطقي دقيق لدلالات المجموعات المتعددة في SPARQL، مما يسد الفجوة بين الويب الدلالي (RDF/SPARQL) ونظرية قواعد البيانات الكلاسيكية (الجبر العلاقاتي/Datalog).
إمكانات التحسين (Optimization): من خلال إثبات التكافؤ مع MRA و NRMD¬، يقترح المؤلفون أن تقنيات التحسين المطورة لـ Datalog (مثل Magic Sets) وللجبر العلاقاتي (مثل إعادة ترتيب الضرب المباشر ودفع عمليات الاختيار - pushdown of selections) يمكن تكييفها لمحركات SPARCl لتحسين الأداء في استعلامات المجموعات (bag-based queries).
توجيه التصميم: تشير النتائج إلى أن التوسعات المستقبلية لـ SPARQL يجب أن تهدف إلى الحفاظ على تماسك مجموعة عملياته الحالية. إن إضافة عمليات تقع خارج هذه البنية الجبرية "المتماسكة" (مثل max-union) قد يؤدي إلى عدم اتساق نظري أو يتطلب معالجة مؤقتة (ad-hoc).
التقنين (Standardization): يوضح هذا العمل سلوك EXCEPT (SetMinus) و OPTIONAL في وجود التكرارات، مما يوفر أساساً متيناً لتحسين الاستعلام والتحقق من التكافؤ في SPARQL 1.1 وما بعده.

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