مرجع
آخر الزيارات

الجبر العلائقي

2٬304 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: في نظرية قاعدة البيانات، الجبر العلائقي هو نظرية تستعمل الهياكل الجبرية لنمذجة البيانات وتحديد الاستعلامات عليها باستخدام دلالات جيدة التأسيس. في هذه المقالة 21 قسماً: «لغة الاستعلامات المهيكلة»، «Relation» و«في الخطوة التالية نطرح R من T» وغيرها.
المحتويات
  1. لغة الاستعلامات المهيكلة
  2. Relation
  3. في الخطوة التالية نطرح R من T
  4. القسمة
  5. }
  6. الامتدادات الشائعة
  7. الارتباط المضاد
  8. الإسقاط
  9. مثال
  10. قراءة إضافية
  11. إعادة التسمية
  12. θ -join و equijoin
  13. الاختيار
  14. Codd's theorem
  15. شبه الارتباط
  16. T := πa1,...,an(R) × S
  17. مؤشرات المجموعة
  18. Object-role modeling
  19. U := T − R
  20. الارتباط الطبيعي
  21. مقدمة

بدايةً، في نظرية قاعدة البيانات، الجبر العلائقي هو نظرية تستعمل الهياكل الجبرية لنمذجة البيانات وتحديد الاستعلامات عليها باستخدام دلالات جيدة التأسيس. قدَّم إدغار ف كوود هذه النظرية. وفيما يلي تفاصيل أوسع عن ذلك.

ومن جهة أخرى، التطبيق الرئيسي للجبر العلائقي هو توفير أساس نظري لقواعد البيانات العلائقية، وخاصة لغات الاستعلام لمثل قواعد البيانات هذه، وأهمها لغة الاستعلامات المهيكلة SQL. تخزن قواعد البيانات العلائقية البيانات الجدولية الممثلة في صورة علاقات relations. غالبًا ما تُرجع الاستعلامات عبر قواعد البيانات العلائقية كذلك بيانات جدولية ممثلة في صورة علاقات.

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

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

لغة الاستعلامات المهيكلة

  • علاقة (منطق)
  • Triadic relation
  • Tuple relational calculus
  • ملحوظات
  • المراجع

Relation

  • Relation (database)
  • Relation algebra
  • Relation composition
  • Relation construction
  • قاعدة بيانات علائقية

في الخطوة التالية نطرح R من T

العلاقة :

القسمة

ومن ناحية أخرى، القسمة (÷) هي عملية ثنائية تُكتب على هيئة R ÷ S. ولا يجري تنفيذ القسمة بشكل مباشر في SQL. تتكون النتيجة من قيود العناصر الثنائية في R على أسماء السمات الفريدة لـ R، أي في رأس R ولكن ليس في رأس S، حيث تنص على أن جميع مجموعاتها مع العناصر الثنائية في S موجودة في R.

}

حيث كما هو الحال في تعريف الارتباط الطبيعي.

من جانب آخر، يمكن كذلك تعريف الارتباط المضاد باعتباره المكمل لشبيه الارتباط، على النحو التالي:ونظراً لهذا، يُطلق على مضاد الارتباط antijoin أحيانًا اسم anti-semijoin أي مضاد شبيه الارتباط، ويُكتب عامل مضاد الارتباط antijoin أحيانًا على هيئة رمز شبيه الارتباط semijoin مع شريط فوقه، بدلاً من ▷.

ومن جهة أخرى، في الحالة التي يكون فيها للعلاقات نفس السمات (متوافقة مع الاتحاد)، فإن مضاد الارتباط antijoin هو نفسه الطرح.

الامتدادات الشائعة

  • الارتباطات الخارجية
  • الارتباط الخارجي الأسر
  • الارتباط الخارجي الأيمن
  • الارتباط الخارجي الكامل
  • عمليات حساب المجال
  • انظر كذلك
  • جداء ديكارتي

ومن ناحية أخرى، في الممارسة العملية، يجري توسيع الجبر العلائقي التقليدي الموصوف أعلاه من خلال عمليات مختلفة مثل الارتباطات الخارجية والوظائف التجميعية وحتى الإغلاق المتعدي.

الارتباط المضاد

وفي هذا السياق، مثلًا، ضع في اعتبارك جداول الموظفين Employee والقسم Dept والارتباط المضاد antijoin الخاصة بهما:

  • يمكن تعريف مضاد الارتباط antijoin رسميًا على النحو التالي:
  • }
  • أو

ومن جهة أخرى، الارتباط المضاد (▷) (بالإنجليزية antijoin)، يُكتب على هيئة R ▷ S حيث R و S علاقات، يشبه شبه الارتباط، ولكن نتيجة الارتباط المضاد هي فقط تلك الثنائيات في R التي لا يوجد لها ثنائي في S متساوٍ في أسماء السمات المشتركة بينهما.

الإسقاط

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

إضافةً إلى ذلك، ملاحظة: عند التنفيذ في معيار لغة الاستعلامات المهيكلة SQL، يقوم "الإسقاط الافتراضي" بإرجاع مجموعة متعددة multiset بدلاً من مجموعة، ويمكن الحصول على إسقاط لإزالة البيانات المكررة عن طريق إضافة الكلمة الأساسية DISTINCT (أي DISTINCT keyword).

مثال

في هذا الإطار، يجري محاكاة عملية القسمة مع العمليات الأساسية على النحو التالي. نفترض أن a1 ،...، an هي أسماء السمات الفريدة لـ R وأن b1،...، bm هي أسماء السمات الخاصة بـ S. في الخطوة الأولى، نقوم بإسقاط R على أسماء السمات الفريدة الخاصة بها وإنشاء جميع التركيبات التي تحتوي على مجموعات في S :

وفي هذا الصدد، إذا كان جدول DBProject يحتوي على جميع مهام مشروع قاعدة البيانات، فإن نتيجة القسمة أعلاه تحتوي بالضبط على الطلاب الذين أكملوا كلتا المهمتين في مشروع قاعدة البيانات. بصورة أكثر رسمية، يمكن تعريف دلالات القسمة على النحو التالي:حيث { a1 ,..., an } هي مجموعة أسماء السمات الفريدة لـ R و t [ a1 ,..., an ] هو تقييد t لهذه المجموعة. من المعتاد أن يكون مطلوبًا أن تكون أسماء السمات في رأس S هي مجموعة فرعية من أسماء R لأنه بخلاف ذلك ستكون نتيجة العملية فارغة دائمًا.

قراءة إضافية

(For relationship with cylindric algebras).

إعادة التسمية

من جهة ثانية، هناك كذلك تدوين ، حيث يمكن إعادة تسمية R إلى x والسمات يجري إعادة تسميتها إلى .

في هذا الإطار، إعادة التسمية ( ρ ) أو rename هي عملية أحادية مكتوبة على النحو التالي حيث تكون النتيجة متطابقة مع R باستثناء أن السمة b في جميع الثنائيات يجري إعادة تسميتها إلى سمة a. يُستعمل هذا عادةً لإعادة تسمية سمة العلاقة لغرض الانضمام.

ومن ناحية أخرى، لإعادة تسمية السمة "isFriend" إلى "isBusinessContact" في علاقة، قد ييجري استخدامها.

مؤشرات الارتباط والشبيهة بالارتباط

θ -join و equijoin

كذلك، من أجل دمج العناصر من علاقتين حيث لا يكون شرط الدمج ببساطة هو مساواة السمات المشتركة، فمن المناسب أن يكون لدينا شكل أكثر عمومية لمؤشر الارتباط join operator، وهو θ-join (أو theta-join). حيث θ-join هو عامل ثنائي مكتوب على النحو التالي أو حيث أن a و b هما اسما سمة، وθ هو عامل علاقات ثنائية في المجموعة }، و υ هو ثابت القيمة، و R و S هما علاقات. تتكون نتيجة هذه العملية من جميع مجموعات الثنائيات في R و S التي تلبي θ. يمكن تعريف نتيجة θ-join فقط إذا كانت رؤوس S و R منفصلة، أي لا تحتوي على سمة مشتركة.

كذلك، بالنظر إلى جداول السيارة و القارب التي تسرد قائمة نماذج من السيارات والقوارب وأسعار كل منها. لنفترض أن أحد العملاء يريد شراء سيارة وقارب، لكنه لا يريد إنفاق أموال على القارب أكثر من الإنفاق على السيارة. وبالتالي يكون θ-join (⋈θ) على المسند سعر السيارة ≥ سعر القارب تُنتج أزواج مُسطحة من الصفوف التي تُحقق ذلك المسند. عند استخدام شرط تكون فيه السمات متساوية، مثلًا السعر، يمكن تحديد الشرط على النحو التالي السعر=السعر

من جانب آخر، وبالتالي فإن محاكاة هذه العملية في العمليات الأساسية تكون على النحو التالي :

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

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

أو بدلا من ذلك (السعر) نفسها.

R ⋈ θ S = σ θ ( R × S )

من جهة ثانية، في حالة أن العامل θ هو عامل المساواة (=)، فإن هذا الارتباط يسمى كذلك ارتباطًا متساويًا equijoin.

الاختيار

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

من جانب آخر، الاختيار المعمم generalized selection ( σ ) هو عملية أحادية مكتوبة على النحو التالي حيث φ هي صيغة اقتراحية propositional formula تتكون من ذرات atomsكما هو مسموح به في الاختيار الطبيعي normal selection والمؤشرات المنطقية ∧

إضافةً إلى ذلك، (and), (or) and (negation). يقوم هذا الاختيار بتحديد كل تلك المجموعات في R التي تحتوي على φ.

Codd's theorem

  • D4 (programming language) (an implementation of D)
  • نمذجة البيانات
  • قاعدة بيانات
  • Datalog
  • تشارلز ساندرز برس

شبه الارتباط

ومن جهة أخرى، في ورقة كوود عام 1970، يسمى الارتباط الجزئي التقييد restriction.

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

وفي هذا الصدد، بشكل أكثر رسمية، يمكن تعريف دلالات شبه الارتباط على النحو التالي:

من جانب آخر، إن شبه الارتباط الأيسر left semijoin (⋉ و⋊) هو ارتباط مشابه للارتباط الطبيعي ومكتوب على النحو التالي حيث و هي علاقات. النتيجة هي مجموعة كل الثنائيات في حيث يوجد مجموعة في حيث يتساويان في أسماء صفاتهما المشتركة. الفرق عن الارتباط الطبيعي هو أن الأعمدة الأخرى من لا تظهر. مثلًا، ضع في اعتبارك جداول الموظف والقِسم Employee و Dept وشبه الارتباط الخاص بهما:

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

حيث كما هو الحال في تعريف الانضمام الطبيعي.

T := πa1,...,an(R) × S

من جانب آخر، في المثال السابق، سيمثل T جدولاً بحيث يجري دمج كل طالب (لأن الطالب هو المفتاح/السمة الفريدة للجدول المكتمل) مع كل مهمة معينة. مثلًا، سيكون لدى Eugene صفين، Eugene → Database1 و Eugene → Database2 في T.

كذلك، T := πStudent(R) × S // هذا يعطينا كل تركيبة مرغوبة ممكنة، بما في ذلك تلك التي لا توجد بالفعل في R، واستبعاد التركيبات الأخرى (مثلًا Fred | compiler1، وهي ليست تركيبة مرغوبة)

علاوةً على ذلك، مثلًا: أولاً، لنفترض أن "مكتمل Completed" لديه سمة ثالثة تسمى "الدرجة grade". فهي غير مرغوب فيها هنا، لذلك يجب علينا إسقاطها دائمًا. في الواقع، في هذه الخطوة يمكننا إسقاط "Task" من R كذلك؛ حيث تقوم عملية الضرب بإعادتها مرة أخرى.

مؤشرات المجموعة

إضافةً إلى ذلك، فضلًا عن ذلك، يمكن تعريف الناتج الديكارتي بشكل مختلف عن الناتج الموجود في نظرية المجموعات بمعنى أن المجموعات تعتبر "سطحية shallow" لأغراض العملية. وهذا يعني أن حاصل الجداء الديكارتي لمجموعة من n-أزواج مع مجموعة من m-أزواج يعطي مجموعة من "المسطحات" -أزواج (بينما كانت نظرية المجموعات الأساسية قد وصفت مجموعة من 2 من الأزواج، كل منها يحتوي على n-أزواج و m-أزواج). وبشكل أكثر رسمية، يمكن تعريف R × S على النحو التالي:

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

كذلك، لكي يمكن تعريف حاصل الجداء الديكارتي، يجب أن يكون للعلاقتين المعنيتين رؤوس منفصلة - أي أنه لا يجب أن يكون لهما اسم سمة مشترك.

من جانب آخر، بالنسبة لاتحاد المجموعات وفرق المجموعات، يجب أن تكون العلاقتان المعنيتان متوافقتين مع الاتحاد - أي يجب أن يكون للعلاقتين نفس مجموعة السمات. نظرًا لأن تقاطع المجموعات يمكن تعريفه بدلالة اتحاد المجموعات وفرق المجموعات، فيجب أن تكون العلاقتان المتضمنتان في تقاطع المجموعات متوافقتين مع الاتحاد كذلك.

Object-role modeling

  • Projection (mathematics)
  • Projection (relational algebra)
  • Projection (set theory)

U := T − R

ومن ناحية أخرى، في U لدينا التركيبات الممكنة التي "كان من الممكن" أن تكون في R، ولكنها لم تكن كذلك.

الارتباط الطبيعي

وفي هذا الصدد، بصورة أكثر رسمية، يمكن تعريف دلالات الارتباط الطبيعي على النحو التالي:حيث Fun(t) هو مسند predicate صحيح لعلاقة t (بالمعنى الرياضي) إذا كانت t دالة (أي أن t لا تقوم بتعيين أي سمة لقيم متعددة). من المعتاد أن يكون مطلوبًا أن يكون لدى R و S سمة مشتركة واحدة على الأقل، ولكن إذا جرى حذف هذا القيد، ولم يكن لدى R و S أي سمات مشتركة، فإن الارتباط الطبيعي يصبح هو حاصل الضرب الديكارتي تمامًا.

في هذا الإطار، يمكن محاكاة الارتباط الطبيعي باستخدام بدائيات كوود Codd's primitives على النحو التالي. افترض أن c1،...، cm هي أسماء السمات المشتركة بين R و S، وأن r1،...، rn هي أسماء السمات الفريدة لـ R وأن s1،...، sk هي أسماء السمات الفريدة لـ S. علاوة على ذلك، افترض أن أسماء السمات x1،...، xm لا توجد في R ولا في S. في الخطوة الأولى، يمكن إعادة تسمية أسماء السمات المشتركة في S كالتالي:ثم نأخذ حاصل الضرب الديكارتي ونختار المجموعات التي سيتم ضمها (ارتباطها):وأخيرًا، نتخذ إسقاطًا للتخلص من السمات التي جرى إعادة تسميتها:

إضافةً إلى ذلك، يمكن كذلك استخدام هذا لتحديد تكوين العلاقات composition of relations. مثلًا، تكوين علاقة الموظف والقسم هو ارتباطهما كما هو موضح أعلاه، ويمكن إسقاطه على جميع السمات باستثناء السمة المشتركة DeptName. في نظرية الفئة، فإن الارتباط join هو على وجه التحديد منتج الألياف fiber product.

كذلك، الارتباط الطبيعي (⨝) (بالإنجليزية Natural join) هو علاقة ثنائية تُكتب على هيئة ( R ⨝ S ) حيث R و S هما علاقات. نتيجة الارتباط الطبيعي هي مجموعة كل مجموعات العناصر في R و S المتساوية في أسماء السمات المشتركة. مثلًا، ضع في اعتبارك الجداول الموظفين Employee والقِسم Dept وارتباطهما الطبيعي:

كذلك، لاحظ أنه لا الموظفة المسماة ماري Mary ولا قسم الإنتاج Production يظهران في النتيجة.

وفي هذا السياق، يمكن القول أن الارتباط الطبيعي هو أحد أهم المؤشرات لأنه النظير العلائقي لمؤشر AND المنطقي. لاحظ أنه إذا ظهر نفس المتغير في كل من المسندين المرتبطين بواسطة AND، فإن هذا المتغير يمثل نفس الشيء ويجب دائمًا استبدال كلا الظهورين بنفس القيمة (وهذا نتيجة لتساوي قوى AND المنطقية). على وجه الخصوص، يسمح الانضمام الطبيعي بدمج العلاقات المرتبطة بمفتاح خارجي. مثلًا، في المثال أعلاه، من المحتمل أن يكون المفتاح الخارجي صالحًا من Employee.DeptName إلى Dept.DeptName ثم الانضمام الطبيعي للموظف والقسم يجمع بين جميع الموظفين وأقسامهم. يعمل هذا لأن المفتاح الخارجي يربط بين السمات التي تحمل نفس الاسم. إذا لم يكن هذا هو الحال كما هو الحال في المفتاح الخارجي من مدير القسم Dept.Manager إلى اسم الموظف Employee.Name. ثم يجب إعادة تسمية هذه الأعمدة قبل اتخاذ الانضمام الطبيعي. يُشار إلى مثل هذا الانضمام أحيانًا باسم الانضمام المتساوي equijoin.

مقدمة

ومن جهة أخرى، تحتوي العلاقة كذلك على عنصر فريد يسمى الرأس header والذي يمنح كل عمود اسمًا أو سمة فريدة attribute داخل العلاقة. تُستعمل السمات في الإسقاطات والتحديدات.

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

ومن ناحية أخرى، يعمل الجبر العلائقي على مجموعات متجانسة من الثنائيات حيث نفسر عادةً m على أنه عدد صفوف العناصر في الجدول و n على أنه عدد الأعمدة. جميع الإدخالات في كل عمود لها نفس النوع type.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.