Relational Algebra ونظرية قواعد البيانات

#Bonus: ليه مهندس .NET يحتاج Relational Algebra؟BonusBonus: why relational algebra matters to a .NET engineer

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

Query بترجع أرقام غلط حتى لو SQL صحيحة نحويًا؟ غالبًا المشكلة في معنى join أو التكرار أو مكان filter. Relational algebra بتديك لغة صغيرة تفك بيها الاستعلام لعمليات، وتراجع SQL مولّدة من EF أو AI. المحور كله اختياري؛ الهدف تفهم النتيجة قبل ما تناقش سرعة التنفيذ.

Relation مجموعة tuples بنفس schema. الـ tuple صف، والـ attribute عمود مسمّى، والـ domain مجموعة القيم المسموحة للعمود. الـ relation النظرية ملهاش ترتيب أو duplicates؛ SQL table ممكن يبقى فيها تكرار وNULL. الأمثلة الجبرية هنا set semantics، والـ SQL بيستخدم DISTINCT لما الفرق مهم.

SELECT Id, Name FROM Products ORDER BY Id; -- (1)

#σ و π و ρ: اختار الصفوف والأعمدة والأساميBonusσ, π and ρ: rows, columns and names

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

لما شاشة المنتجات محتاجة أسماء الكتب بس، ماتحمّلش كل الصفوف والأعمدة. Selection σ بتفلتر صفوف. Projection π بتختار attributes وبتشيل تكرار في الجبر. Rename ρ بتسمي relation أو attributes عشان تمنع الالتباس، خصوصًا self joins.

SELECT * FROM Products WHERE Category = 'Books';       -- (1) σ
SELECT DISTINCT Category FROM Products;               -- (2) π
SELECT P.Id AS ProductId, P.Name FROM Products AS P;   -- (3) ρ

ماتشيلش join key بدري لو محتاجه بعدين. DISTINCT ممكن تخبي bug في join؛ افهم سبب التكرار الأول.

#∪ و − و ∩: عمليات المجموعاتBonus∪, − and ∩: set operations

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

عايز مستخدمين اشتروا الشهر ده أو الشهر اللي فات؟ دي union. عايز اللي في الاتنين؟ intersection. عايز اللي اشتروا قبل كده ومارجعوش؟ difference. لازم المدخلات union-compatible: نفس عدد الأعمدة وdomains متوافقة، ونوحد الأسامي عند الحاجة.

SELECT UserId FROM A UNION SELECT UserId FROM B;       -- (1)
SELECT UserId FROM A EXCEPT SELECT UserId FROM B;      -- (2)
SELECT UserId FROM A INTERSECT SELECT UserId FROM B;   -- (3)

لو التكرار مقصود، UNION ALL أوفر من إزالة تكرار مش مطلوبة. الجمع هنا بين نتائج، مش join بيزوّد أعمدة. تفاصيل SQL: Combining queries.

#× و ⋈: من كل الأزواج للـ joinsBonus× and ⋈: from all pairs to joins

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

Cartesian product × بيكوّن كل زوج ممكن. لو P فيها صفين وO فيها تلاتة، النتيجة ستة. Theta join هي selection على product بشرط θ؛ equi-join حالتها لما الشرط مساواة. Natural join بتساوي تلقائيًا كل attributes المشتركة في الاسم وبتحتفظ بنسخة واحدة منها؛ زيادة عمود بنفس الاسم ممكن تغيّر النتيجة فجأة.

SELECT P.Id, O.OrderId FROM P CROSS JOIN O;                 -- (1)
SELECT P.Id, O.OrderId FROM P
JOIN O ON P.Id = O.ProductId;                              -- (2)
SELECT P.Id, O.OrderId FROM P
JOIN O ON P.Price < O.MaxPrice;                            -- (3)
-- Natural join equivalent with explicit matching names after rename:
SELECT P.Id, P.Price, O.OrderId, O.MaxPrice
FROM P JOIN O ON P.Id = O.ProductId;                       -- (4)

راجع cardinality قبل SUM؛ join واحد لمتعدد ممكن يكرر مبلغ order على كل سطر. ماتكتبش CROSS JOIN لو المطلوب relationship بشرط.

#Outer joins و ⋉ و ▷: موجود ولا مش موجود؟BonusOuter joins, ⋉ and ▷: matching and absence

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

تخيّل Users على الشمال وOrders على اليمين: الـ join بيربط صفوف لما قيمة المفتاح في الجدولين تتطابق. Inner join بيرجع المطابق بس. Left outer join بيحافظ على كل مستخدم حتى لو ماعندوش order، ويحط NULL مكان بيانات order الغايبة؛ NULL هنا علامة «مفيش قيمة مطابقة»، مش صفر. Right بيعكس الجهة، وfull بيحافظ على الصفوف غير المطابقة من الناحيتين. دي امتدادات للجبر الكلاسيكي اللي مافيهوش NULL. Semi-join ⋉ يرجّع المستخدمين اللي عندهم order من غير أعمدة order أو تكرار لو للمستخدم كذا order. Anti-join ▷ هنا يرجّع المستخدمين اللي مالهمش order؛ الرمز بيختلف بين المراجع.

Left join تطلع (1,10) و(1,11) و(2,NULL). Right تطلع كمان (NULL,12) بدل (2,NULL). Full تطلع الأربعة.

SELECT U.Id, O.Id AS OrderId FROM Users U
LEFT JOIN Orders O ON O.UserId = U.Id;                     -- (1)
SELECT U.Id, O.Id AS OrderId FROM Users U
RIGHT JOIN Orders O ON O.UserId = U.Id;
SELECT U.Id, O.Id AS OrderId FROM Users U
FULL OUTER JOIN Orders O ON O.UserId = U.Id;
SELECT U.Id FROM Users U WHERE EXISTS
    (SELECT 1 FROM Orders O WHERE O.UserId = U.Id);         -- (2)
SELECT U.Id FROM Users U WHERE NOT EXISTS
    (SELECT 1 FROM Orders O WHERE O.UserId = U.Id);         -- (3)

حط فلتر اليمين في ON لو عايز تحافظ على الصفوف غير المطابقة؛ شرط WHERE O.Status = 'Paid' بعد left join بيستبعد NULL وغالبًا يغيّر المعنى لـ inner join.

#÷ و γ: كل المطلوب والمجاميعBonus÷ and γ: all required items and aggregation

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

Division ÷ تجاوب على «مين اشترى كل المنتجات المطلوبة؟». لو Bought(UserId, ProductId) وRequired(ProductId)، النتيجة Users اللي عندهم زوج مع كل Required. Aggregation γ من extended algebra: تعمل grouping وتحسب count أو sum.

-- Candidate users are the users occurring in Bought, as in division.
SELECT DISTINCT B.UserId FROM Bought B
WHERE NOT EXISTS (
    SELECT 1 FROM Required R
    WHERE NOT EXISTS (
        SELECT 1 FROM Bought B2
        WHERE B2.UserId = B.UserId AND B2.ProductId = R.ProductId)); -- (1)

-- γ UserId; COUNT(*)→ItemCount (Bought)
SELECT UserId, COUNT(*) AS ItemCount
FROM Bought GROUP BY UserId;                                   -- (2)

بديل GROUP BY مع HAVING محتاج يتعامل صح مع duplicates والـ required set الفاضية. Division مش قسمة أرقام، ومش ضرورية لو المطلوب «أي منتج»؛ EXISTS واحدة تكفي.

#Equivalences و Query trees: الـ optimizer بيفكر إزايBonusEquivalences and query trees: optimizer reasoning

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

لو الاستعلام بيعمل join لمليون order وبعدها يفلتر paid، ممكن يدفع selection لتحت قبل join ويقلل الصفوف الوسيطة. دي equivalence منطقية، مش وعد بخطة physical معينة. الـ optimizer بيوازن statistics وindexes وتكلفة join algorithms.

Before:                             After:
π U.Name, O.Id                      π U.Name, O.Id
       |                                   |
σ O.Status='Paid'                         ⋈ U.Id=O.UserId
       |                                /               \
⋈ U.Id=O.UserId                       Users       σ Status='Paid'   (1)
 /           \                                          |
Users       Orders                                    Orders

SELECT U.Name, O.Id FROM Users U
JOIN Orders O ON U.Id = O.UserId
WHERE O.Status = 'Paid';                         -- (2)

ماتطبقش القواعد عمياني على outer joins، أو LIMIT، أو aggregates، أو expressions غير حتمية. Projection pushdown لازم تسيب keys وattributes المستخدمة في filters والـ joins. راجع actual plan بدل الحكم من شكل SQL.

#SQL bags و NULL: الفرق اللي بيكسر الترجمةBonusSQL bags and NULL: where direct translation breaks

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

SQL افتراضيًا bag، يعني التكرار جزء من المعنى. لو الأسعار 20 و20 و100، SELECT Price ترجع تلاتة، وprojection النظرية ترجع 20 و100 بس. الـ join بيضاعف multiplicities، فـ DISTINCT في آخر query ممكن يخبي الخطأ من غير ما يصلح SUM اتحسبت قبلها.

NULL مش قيمة مجهولة تساوي نفسها. المقارنة بيها عادة ترجع UNKNOWN، وWHERE وHAVING بيحتفظوا بـ TRUE بس. NOT UNKNOWN تفضل UNKNOWN. FALSE AND UNKNOWN تساوي FALSE، وTRUE OR UNKNOWN تساوي TRUE.

SELECT Price FROM Products;                         -- (1) preserves duplicates
SELECT DISTINCT Price FROM Products;
SELECT UserId FROM A UNION ALL SELECT UserId FROM B; -- (2) preserves duplicates
SELECT Id FROM Products WHERE Price IS NULL;        -- (3)
SELECT U.Id FROM Users U WHERE NOT EXISTS (
    SELECT 1 FROM Orders O WHERE O.UserId = U.Id);    -- (4)

إزالة التكرار بتعامل NULLs كـ not distinct عن بعضها، رغم إن NULL = NULL مش TRUE. ماتستنتجش سلوك set operators من مقارنة WHERE بس.

#Functional dependencies و Closure و KeysBonusFunctional dependencies, closure and keys

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

افترض جدول فيه سطر لكل منتج داخل order. ممكن OrderId واحد يظهر في كذا سطر، لكن كل السطور دي تخص نفس المستخدم. لو كل OrderId له UserId واحد مسموح به، نكتب OrderId → UserId. دي functional dependency، يعني قاعدة ثابتة في شكل الداتا: أي صفين متفقين على الشمال لازم يتفقوا على اليمين في كل حالة مسموحة، مش بس في العينة اللي قدامنا. السهم مش معناه العكس ولا علاقة سبب ونتيجة. هنستخدم القواعد دي نعرف إيه الأعمدة اللي تميّز order line واحدة.

قبل الحساب: closure لمجموعة أعمدة هي كل الأعمدة اللي نقدر نستنتجها منها بتطبيق القواعد مراراً. لو الـ closure وصلت لكل أعمدة الجدول، فالمجموعة دي superkey وبتعرّف الصف؛ ولو مافيش جزء أصغر منها يحقق ده تبقى candidate key. المفتاح الأساسي هو candidate key اختاره تصميم الجدول.

R(OrderId, UserId, UserEmail, ProductId, Qty)
Assumed rules: one line per product per order.
FDs:
  OrderId → UserId
  UserId → UserEmail
  OrderId, ProductId → Qty

{OrderId}+ = {OrderId, UserId, UserEmail}                    (1)
{OrderId, ProductId}+ = all attributes of R                 (2)

Superkey يحدد الصف؛ candidate key superkey minimal من غير attributes زيادة؛ primary key واحد اخترناه من المرشحين. Minimal مش معناه أقصر key بين كل المرشحين. ماافترضناش إن email فريد؛ لو القاعدة دي موجودة، أضفها وحلل من جديد.

CREATE TABLE OrderLines (
    OrderId int NOT NULL,
    ProductId int NOT NULL,
    Qty int NOT NULL,
    PRIMARY KEY (OrderId, ProductId)
);

الـ primary key بتنّفذ قاعدة الزوج الفريد، مش بتثبت باقي الـ FDs تلقائيًا.

#Normalization من الـ FDs وفرق Calculus عن AlgebraBonusNormalization from FDs, and calculus versus algebra

اختياري بس بيفرق: مش هيتسأل فيه في كل انترفيو، بس معرفته بتعمّق فهمك وبتميّزك عن غيرك.

تكرار UserEmail على كل سطر طلب بيعمل update anomalies: تعدل سطر وتنسى سطر. نفك الـ relation بناءً على dependencies، مش لمجرد إن الجدول كبير.

Prime يعني attribute داخلة في أي candidate key. لو فيه key واحدة بسيطة، وصف «مفيش transitive dependency لغير الـ key» مفيد، لكن مش بديل لتعريف 3NF العام.

Users(UserId PK, UserEmail)                              (1)
Orders(OrderId PK, UserId FK)
OrderLines(OrderId FK, ProductId, Qty, PK(OrderId, ProductId))

Lossless reconstruction:
Users ⋈ Orders ⋈ OrderLines                              (2)

SELECT O.OrderId, U.UserId, U.UserEmail, L.ProductId, L.Qty
FROM Orders O JOIN Users U ON U.UserId = O.UserId
JOIN OrderLines L ON L.OrderId = O.OrderId;               -- (3)

Relational calculus بتحدد الصفوف المطلوبة بمنطق predicates وquantifiers؛ algebra بتعبّر عن تركيب operators. Safe، domain-independent calculus والـ classical algebra متكافئين في القدرة التعبيرية. SQL declarative وقريبة من المنطق ده، لكن bags وNULL وaggregation إضافات لازم تتحسب. ده مش معناه إن algebra خطة physical بتفرض ترتيب التنفيذ.

ماتعملش denormalization قبل قياس bottleneck وتحديد مين يحدث النسخ. مرجع إضافي: Relational algebra and normalization.