التبعية المولدة للصفوف

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

في نظرية قواعد البيانات العلائقية ، يُعدّ التبعية المولدة للصفوف (TGD) نوعًا معينًا من القيود المفروضة على قاعدة البيانات العلائقية . وهي فئة فرعية من فئة التبعيات المضمنة (EDs).

تأخذ خوارزمية تُعرف باسم المطاردة كمدخلات حالة قد تفي أو لا تفي بمجموعة من TGDs (أو بشكل عام EDs) وإذا انتهت (وهو أمر غير قابل للتقرير مسبقًا)، فإنها تُخرج حالة تفي بـ TGDs.

تعريف

التبعية المولدة للصفوف هي جملة في منطق الرتبة الأولى على الشكل التالي: [ 1 ]

∀x1،...،xن.ϕ(x1،...،xن)→∃y1،...،yم،ψ(x1،...،xن،y1،...،yم){\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \exists y_{1},\ldots ,y_{m},\psi (x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m})}

أينϕ{\displaystyle \phi }قد يكون فارغًا وψ{\displaystyle \psi }هو اقتران غير فارغ لذرات علائقية . الذرة العلائقية لها الشكل التالي:R(w1،...،wح){\displaystyle R(w_{1},\ldots ,w_{h})}، حيث كل مصطلحw،...،wح{\displaystyle w,\ldots ,w_{h}}هي متغيرات أو ثوابت.

شظايا

تم تعريف عدة أجزاء من TGDs. على سبيل المثال، TGDs الكاملة هي TGDs التي لا تستخدم المُكمِّم الوجودي. ويمكن اعتبار TGDs الكاملة بمثابة برامج مكتوبة بلغة استعلام Datalog .

هناك أيضًا بعض أجزاء من TGDs التي يمكن التعبير عنها في منطق محمي ، على وجه الخصوص: [ 2 ] [ 3 ] [ 4 ]

  • في قواعد البيانات ذات الحدود المحمية (FGTGD)، يجب أن تظهر جميع المتغيرات المشتركة بين جسم ورأس القاعدة (تسمى متغيرات الحدود ) معًا في ذرة ما؛
  • تُعتبر قواعد البيانات المحمية (GTGD) قواعد بيانات خاصة من نوع FGTGD حيث يجب أن تظهر جميع المتغيرات المستخدمة في جسم القاعدة معًا في ذرة ما؛
  • تُعتبر TGDs الخطية (LTGD) نوعًا خاصًا من GTGDs حيث يتكون جسمها من ذرة واحدة؛
  • تُعدّ تبعيات التضمين (IND) من أنواع LTGDs الخاصة التي تحتوي على ذرة علائقية واحدة فقط في كلا جانبي القاعدة. [ 5 ]

لقد دُرست القدرة التعبيرية لهذه الأجزاء ولغة TGDs دراسةً معمقة. فعلى سبيل المثال، طوّر كلٌ من هينغ تشانغ وآخرون [ 3 ] ، وماركو كونسول وفوكيون جي. كولايتيس [ 4 ] ، سلسلةً من توصيفات نظرية النماذج لهذه اللغات. إضافةً إلى ذلك، قدّم هينغ تشانغ وغويفي جيانغ توصيفاتٍ للقدرة التعبيرية البرمجية للغة TGDs، والعديد من امتداداتها، ولغة Linear TGDs، وتحديدًا في سياق الإجابة على الاستعلامات [ 6 ] .

في لغة SQL ، يتم التعبير عن تبعيات التضمين عادةً عن طريق قيد أقوى يسمى المفتاح الخارجي ، والذي يجبر متغيرات الحدود على أن تكون مفتاحًا مرشحًا في الجدول المقابل للذرة العلائقية لـψ{\displaystyle \psi }.

مراجع

  1. ↑ فاجين، رونالد (2009). "التبعيات المولدة للصفوف". في: ليو، لينغ ؛ أوزسو، م. تامر (محرران). موسوعة أنظمة قواعد البيانات . سبرينغر الولايات المتحدة. ص 3201-3202 . doi : 10.1007/978-0-387-39940-9_1274 . ISBN  9780387355443.
  2. ↑ بينيديكت، مايكل؛ بوريس، بيير؛ جاكيه، لويس؛ تومازو، مايكل (أغسطس 2019). التفكير المنطقي بشأن الإفصاح في تكامل البيانات في ظل قيود المصدر . المؤتمر الدولي المشترك الثامن والعشرون للذكاء الاصطناعي IJCAI 2019. ماكاو، الصين. الصفحات 1551-1557 . arXiv : 1906.00624 . doi : 10.24963 /ijcai.2019/215 . 
  3. 1 2 تشانغ، هينغ؛ تشانغ، يان؛ جيانغ، غويفي (2020-07-09). "الخصائص النظرية النموذجية للغات القواعد الوجودية" . وقائع المؤتمر الدولي المشترك التاسع والعشرين حول الذكاء الاصطناعي . 2 : 1940-1946 . arXiv : 2001.08688 . doi : 10.24963/ijcai.2020/269 .
  4. 1 2 كونسول، ماركو؛ كولايتيس، فوكيون ج.؛ بيريس، أندرياس (يونيو 2021). توصيفات نظرية النموذج للأنطولوجيات القائمة على القواعد . ندوة حول مبادئ أنظمة قواعد البيانات. PODS'21: وقائع الندوة الأربعين لجمعية ACM SIGMOD-SIGACT-SIGAI حول مبادئ أنظمة قواعد البيانات . حدث افتراضي، الصين. الصفحات 416-428 . doi : 10.1145/3452021.3458310 . hdl : 11573/1568516 . 
  5. ^ Kolaitis، Phokion G. “برنامج تعليمي حول تبعيات قاعدة البيانات” (PDF) . جامعة كاليفورنيا سانتا كروز وأبحاث IBM - المادن. مؤرشفة من الأصلي (PDF) في 20 فبراير 2015 . تم الاسترجاع 2021-12-10 .
  6. ↑ تشانغ، هينغ؛ جيانغ، غويفي (28-06-2022). "توصيف القدرة التعبيرية البرمجية للغات القواعد الوجودية" . وقائع مؤتمر AAAI حول الذكاء الاصطناعي . 36 (5): 5950-5957 . arXiv : 2112.08136 . doi : 10.1609/aaai.v36i5.20540 . ISSN 2374-3468 . 

للمزيد من القراءة