Реляциялық алгебра - Relational algebra

Жылы мәліметтер қорының теориясы, реляциялық алгебра қолданатын теория болып табылады алгебралық құрылымдар а негізделген семантика деректерді модельдеуге және олар бойынша сұраныстарды анықтауға арналған. Теория енгізген Эдгар Ф. Кодд.

Реляциялық алгебраның негізгі қолданылуы теориялық негіз қалау болып табылады реляциялық мәліметтер базасы, атап айтқанда сұрау тілдері осындай мәліметтер базасы үшін, олардың ішінде бастысы SQL. Реляциялық мәліметтер қоры кесте түрінде көрсетілген деректерді сақтайды қарым-қатынастар. Реляциялық мәліметтер қорына қатысты сұраулар көбінесе кесте түрінде көрсетілген деректерді қайтарады қарым-қатынастар. Реляциялық алгебраның негізгі алғышарты - бір немесе бірнеше кіріс қатынастарын шығыс қатынасқа түрлендіретін операторларды анықтау. Бұл операторлар қатынастарды кіріс ретінде қабылдап, қатынастарды нәтиже ретінде шығаратындығын ескере отырып, оларды біріктіруге болады және көптеген кіріс қатынастарын (олардың дерекқорында сақталатын) бір қатынасқа айналдыратын әлеуетті күрделі сұраныстарды қолдануға болады (сұрау нәтижелері) . Бірыңғай операторлар кіріс ретінде бір қатынасты қабылдайды; мысалдарға белгілі бір атрибуттарды (бағандарды) немесе кортеждерді (жолдарды) енгізу қатынасынан сүзуге арналған операторлар жатады. Екілік операторлар кіріс ретінде екі қатынасты қабылдайды; мұндай операторлар екі кірістегі қатынастарды бір шығыс қатынасқа біріктіреді, мысалы, екі қатынаста кездесетін барлық кортеждерді алып, екінші қатынастан табылған бірінші қатынастан кортеждерді алып тастап, бірінші қатынастың кортеждерін екінші қатынасқа шығарады. белгілі бір шарттарға сәйкес келу және т.б. Сондай-ақ басқа операторларды қосуға болады, мұнда белгілі бір операторларды қосу немесе алып тастау алгебралар отбасын тудырады.

Кіріспе

Реляциялық алгебра таза математикадан тыс жарық көргенге дейін аз көңіл бөлді Э.Ф.Кодд Келіңіздер мәліметтердің реляциялық моделі 1970 ж. Кодд осындай алгебраны мәліметтер базасының сұраныстар тілдеріне негіз ретінде ұсынды. (Бөлімді қараңыз) Іске асыру.)

Кодд алгебрасының бес қарабайыр операторы болып табылады таңдау, болжам, Декарттық өнім (деп те аталады кросс өнім немесе айқасу), одақ құрды, және айырмашылықты орнатыңыз.

Операторларды орнатыңыз

Реляциялық алгебра қолданады одақ құрды, айырмашылықты орнатыңыз, және Декарттық өнім бастап жиынтық теориясы, бірақ осы операторларға қосымша шектеулер қосады.

Орнатылған одақ пен жиынтық айырмашылығы үшін екеуі қарым-қатынастар қатысуы керек кәсіптік үйлесімді- яғни екі қатынастың атрибуттарының жиынтығы болуы керек. Себебі қиылысты орнатыңыз белгіленген одақ және жиынтық айырмашылық тұрғысынан анықталады, жиынтық қиылысқа қатысатын екі қатынас сонымен қатар одаққа үйлесімді болуы керек.

Декарттық өнімнің анықталуы үшін екі қатынастың біріккен тақырыптары болуы керек, яғни олардың жалпы атрибут атауы болмауы керек.

Сонымен қатар, декарттық өнім in-мен салыстырғанда басқаша анықталады орнатылды кортеждер операция мақсаттары үшін «таяз» болып саналады деген мағынадағы теория. Яғни, жиынтықтың декарттық көбейтіндісі n- жиынтығы бар буындар м-жұптар «тегістелген» жиынтығын береді (n + м)-tuples (алайда негізгі жиынтық теориясы әрқайсысында an бар 2 кортеж жиынтығын тағайындаған болар еді n-tuple және an м-тупле). Ресми түрде, R × S келесідей анықталады:

${ displaystyle R times S: = {(r_ {1}, r_ {2}, dots, r_ {n}, s_ {1}, s_ {2}, dots, s_ {m}) | ( r_ {1}, r_ {2}, нүктелер, r_ {n}) R-де, (s_ {1}, s_ {2}, нүктелер, s_ {m}) in S }}$

Декарттық өнімнің кардиналдылығы деп оның факторларының кардиналының көбейтіндісін айтады, яғни |R × S| = |R| × |S|.

Болжам (Π)

A болжам Бұл бірыңғай операция ретінде жазылған ${ displaystyle Pi _ {a_ {1}, ldots, a_ {n}} (R)}$ қайда ${ displaystyle a_ {1}, ldots, a_ {n}}$ атрибут атауларының жиынтығы болып табылады. Мұндай проекцияның нәтижесі ретінде анықталады орнатылды бұл барлық кезде алынған кортеждер жылы R жиынтығымен шектелген ${ displaystyle {a_ {1}, ldots, a_ {n} }}$.

Ескерту: іске асырылған кезде SQL стандартты «әдепкі проекция» а қайтарады мультисет жиынтықтың орнына және Π қайталанатын деректерді жоюға арналған проекцияны. қосу арқылы алады БІЛУ кілт сөз.

Таңдау (σ)

A жалпыланған таңдау Бұл бірыңғай операция ретінде жазылған ${ displaystyle sigma _ { varphi} (R)}$ қайда φ Бұл ұсыныстық формула тұрады атомдар рұқсат етілгендей қалыпты таңдау және логикалық операторлар ${ displaystyle wedge}$ (және ), ${ displaystyle lor}$ (немесе ) және ${ displaystyle neg}$ (жоққа шығару ). Бұл таңдау олардың барлығын таңдайды кортеждер жылы R ол үшін φ ұстайды.

Мекен-жай кітабындағы барлық достардың немесе серіктестердің тізімін алу үшін таңдау келесі түрде жазылуы мүмкін ${ displaystyle sigma _ {{ text {isFriend = true}} , lor , { text {isBusinessContact = true}}} ({ text {addressBook}})}$. Нәтижесінде барлық бірегей жазбалардың барлық атрибуттарын қамтитын қатынас болады isF Friend шын немесе қайда isBusinessContact шындық

Атауын өзгерту (ρ)

A атауын өзгерту Бұл бірыңғай операция ретінде жазылған ${ displaystyle rho _ {a / b} (R)}$ мұндағы нәтиже бірдей R қоспағанда б барлық кортеждердегі атрибут an деп өзгертілді а атрибут. Бұл жай атрибутының атауын өзгерту үшін қолданылады қатынас немесе қатынастың өзі.

«IsFriend» атрибутының атын «isBusinessContact» қатынасқа өзгерту үшін, ${ displaystyle rho _ { text {isBusinessContact / isFriend}} ({ text {addressBook}})}$ қолданылуы мүмкін.

Қосылу және біріктіру сияқты операторлар

Табиғи қосылу (⋈)

Табиғи қосылыс (⋈) - бұл екілік оператор деп жазылған (R ⋈ S) қайда R және S болып табылады қарым-қатынастар.^[1] Табиғи қосылудың нәтижесі - бұл кортеждердің барлық тіркесімдерінің жиынтығы R және S жалпы атрибуттық атауларына тең. Мысал үшін кестелерді қарастырайық Қызметкер және Бөлім және олардың табиғи қосылыстары:

Нәтижесінде Мэри есімді қызметкер де, өндірістік бөлім де көрінбейтінін ескеріңіз.

Мұны анықтау үшін де қолдануға болады қатынастардың құрамы. Мысалы, Қызметкер және Бөлім бұл жоғарыда көрсетілгендей, жалпы атрибуттан басқаларының бәрінде болжанған олардың қосылысы DeptName. Жылы категория теориясы, қосылу дәл болып табылады талшық өнімі.

Табиғи қосылыс маңызды операторлардың бірі болып табылады, өйткені ол логикалық AND операторының реляциялық аналогы болып табылады. ЖӘНЕ-мен байланысқан екі предикаттың әрқайсысында бірдей айнымалы пайда болса, онда бұл айнымалы бірдей затты білдіреді және екі көрініс әрқашан бірдей мәнмен алмастырылуы керек (бұл икемсіздік логикалық ЖӘНЕ). Атап айтқанда, табиғи қосылу а байланыстыратын қатынастардың үйлесуіне мүмкіндік береді шетелдік кілт. Мысалы, жоғарыдағы мысалда шетелдік кілт болуы мүмкін Қызметкер.DeptName дейін Бөлім.DeptName содан кейін табиғи қосылу Қызметкер және Бөлім барлық қызметкерлерді өздерінің бөлімшелерімен біріктіреді. Бұл жұмыс істейді, өйткені шетелдік кілт аттас атрибуттар арасында болады. Егер бұл шетелдік кілт сияқты болмаса Бөлім.Менеджер дейін Қызметкер.Аты-жөні онда біз табиғи қосылысты бастамас бұрын осы бағандардың атын өзгертуіміз керек. Мұндай қосылысты кейде ан деп те атайды equijoin (қараңыз θ-қосылыңыз).

Табиғи қосылыстың семантикасы ресми түрде келесідей анықталады:

${ displaystyle R bowtie S = left {r cup s vert r in R land s in S land { mathit {Fun}} (r cup s) оң жақта }}$

(1)

қайда Көңілді (t) Бұл предикат бұл а қатынас т (математикалық мағынада) iff т функция болып табылады. Әдетте бұл талап етіледі R және S кем дегенде бір жалпы төлсипатқа ие болуы керек, бірақ егер бұл шектеу алынып тасталса және R және S жалпы атрибуттары жоқ болса, онда табиғи қосылыс декарттық өнімге айналады.

Табиғи қосылысты Кодд примитивтерімен келесідей модельдеуге болады. Мұны ойлаңыз c₁,...,c_м жалпы атрибут атаулары болып табылады R және S, р₁,...,р_n ерекше атрибуттар R және с₁,...,с_к ерекше атрибуттар S. Сонымен, атрибут атаулары деп ойлаңыз х₁,...,х_м жоқ R не S. Бірінші қадамда біз енді жалпы атрибут атауларын қайта атауымызға болады S:

${ displaystyle T = rho _ {x_ {1} / c_ {1}, ldots, x_ {m} / c_ {m}} (S) = rho _ {x_ {1} / c_ {1}} ( rho _ {x_ {2} / c_ {2}} ( ldots rho _ {x_ {m} / c_ {m}} (S) ldots))}$

(2)

Содан кейін декарттық өнімді аламыз және біріктірілетін кортеждерді таңдаймыз:

${ displaystyle P = sigma _ {c_ {1} = x_ {1}, ldots, c_ {m} = x_ {m}} (R times T) = sigma _ {c_ {1} = x_ { 1}} ( sigma _ {c_ {2} = x_ {2}} ( ldots sigma _ {c_ {m} = x_ {m}} (R times T) ldots))}$

(3)

Соңында біз қайта атрибуттардан құтылу үшін проекция аламыз:

${ displaystyle U = Pi _ {r_ {1}, ldots, r_ {n}, c_ {1}, ldots, c_ {m}, s_ {1}, ldots, s_ {k}} (P )}$

(4)

θ-қосылу және қосылу

Кестелерді қарастырыңыз Автокөлік және Қайық онда автомобильдер мен қайықтардың модельдері және олардың бағалары келтірілген. Клиент автокөлік пен қайық алғысы келеді делік, бірақ ол қайыққа машинадан гөрі көп ақша жұмсағысы келмейді. The θ-қосылу (⋈_θ) предикат бойынша CarPrice ≥ BoatPrice предикатты қанағаттандыратын тегістелген жұп қатарлар шығарады. Атрибуттар тең болатын шартты қолданған кезде, мысалы, баға, онда шарт ретінде көрсетілуі мүмкін Бағасы=Бағасынемесе балама (Бағасы) өзі.

Автокөлік CarModel CarPrice CarA 20,000 CarB 30,000 CarC 50,000

Қайық BoatModel BoatPrice Қайық1 10,000 2. Қайық 40,000 Қайық3 60,000

${ displaystyle {Car bowtie Boat atop scriptstyle CarPrice geq BoatPrice}}$ CarModel CarPrice BoatModel BoatPrice CarA 20,000 Қайық1 10,000 CarB 30,000 Қайық1 10,000 CarC 50,000 Қайық1 10,000 CarC 50,000 2. Қайық 40,000

Егер біз үйлесімділік шарты тек ортақ атрибуттардың теңдігі емес екі қатынастың кортеждерін біріктіргіміз келсе, онда біріктіру операторының неғұрлым жалпы формасы болған ыңғайлы, бұл θ-қосылу (немесе тета-қосылу). The θ-қосу ретінде жазылатын екілік оператор ${ displaystyle {R bowtie S a theta b}}$ немесе ${ displaystyle {R bowtie S a theta v}}$ қайда а және б атрибут атаулары, θ екілік болып табылады реляциялық оператор жиынтықта {<, ≤, =, ≠, >, ≥}, υ мәні тұрақты болып табылады және R және S қатынастар болып табылады. Бұл операцияның нәтижесі in-дегі барлық тіркесімдерден тұрады R және S бұл қанағаттандырады θ. Нәтижесі θ-қосу тек егер тақырыптары болса ғана анықталады S және R бөлінеді, яғни жалпы атрибутты қамтымайды.

Бұл операцияның негізгі операциялардағы модельдеуі келесідей:

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

Егер оператор болса θ теңдік операторы (=) болса, онда бұл қосылыс ан деп аталады equijoin.

Алайда, табиғи қосылу және таңдау операторларын қолдайтын компьютер тілі қажет еместігін ескеріңіз θ- сонымен қатар қосылыңыз, өйткені бұны табиғи қосылыстың нәтижесінен таңдау арқылы алуға болады (ол ортақ атрибуттар болмаған кезде декарттық өнімге азаяды).

SQL ендірулерінде предикатқа қосылуды әдетте an деп атайды ішкі қосылыс, және қосулы кілт сөз жолдарды сүзуге қолданылатын предикатты көрсетуге мүмкіндік береді. Айта кету керек: тегістелген декарттық өнімді қалыптастыру, содан кейін жолдарды сүзу тұжырымдамалық тұрғыдан дұрыс, бірақ іске қосылу сұранысын жеделдету үшін неғұрлым жетілдірілген деректер құрылымдарын қолданады.

Semijoin (⋉)(⋊)

Сол жақ семижоин - бұл табиғи қосылысқа ұқсас және осылай жазылған қосылыс R⋉ S қайда R және S болып табылады қарым-қатынастар.^[2] Нәтижесінде барлық кортеждердің жиынтығы болады R ол үшін кортеж бар S бұл олардың жалпы төлсипат атауларына тең. Табиғи қосылыстың айырмашылығы мынада: S пайда болмайды. Мысалы, кестелерді қарастырайық Қызметкер және Бөлім және олардың қосылуы:

Жартылай қосылудың семантикасын ресми түрде келесідей анықтауға болады:

R ⋉ S = { т : т ∈ R ∧ ∃с ∈ S(Көңілді (т ∪ с)) }

қайда Көңілді(р) табиғи қосылыстың анықтамасындағы сияқты.

Жартылай қосылысты табиғи қосылыстың көмегімен орындауға болады. Егер а₁, ..., а_n деген атрибуттар болып табылады R, содан кейін

R ⋉ S = π_а1,..,аn(R ⋈ S).

Табиғи қосылуды негізгі операторлармен имитациялау мүмкін болғандықтан, бұл semijoin үшін де қажет.

Коддтың 1970 жылғы еңбегінде семижоин шектеу деп аталады.^[3]

Антигоин (▷)

Ретінде жазылған антижоин R ▷ S қайда R және S болып табылады қарым-қатынастар, semijoin-ге ұқсас, бірақ антижоиннің нәтижесі тек сол кортеждер R ол үшін бар жоқ кортеж S бұл олардың жалпы төлсипат атауларына тең.^[4]

Мысал үшін кестелерді қарастырайық Қызметкер және Бөлім және оларға қосылу:

Антигоин ресми түрде келесі түрде анықталады:

R ▷ S = { т : т ∈ R ∧ ¬∃с ∈ S(Көңілді (т ∪ с)) }

немесе

R ▷ S = { т : т ∈ R, кортеж жоқ с туралы S бұл қанағаттандырады Көңілді (т ∪ с) }

қайда Көңілді (т ∪ с) табиғи қосылыстың анықтамасындағы сияқты.

Антигоинді ретінде анықтауға болады толықтыру жартылай қосылыстың тізімі:

R ▷ S = R − R ⋉ S

(5)

Осыны ескере отырып, антижоин кейде антисемиджоин деп аталады, ал антиджоин операторы кейде of орнына, үстінде жолағы бар семижоин символы түрінде жазылады.

Бөлім (÷)

Бөлу деп жазылатын екілік амал болып табылады R ÷ S. Бөлу тікелей SQL-де жүзеге асырылмайды. Нәтиже ішіндегі кортеждердің шектеулерінен тұрады R тек төлсипат атауларына R, яғни, тақырыбында R бірақ тақырыпта жоқ S, бұл үшін олардың барлық тіркесімдері кортеждермен біріктірілген S қатысады R. Мысал үшін кестелерді қараңыз Аяқталды, DBProject және оларды бөлу:

Егер DBProject Деректер қоры жобасының барлық тапсырмаларын қамтиды, содан кейін жоғарыдағы бөлудің нәтижелері Деректер қоры жобасындағы екі тапсырманы да орындаған студенттерден тұрады, формальды түрде бөлудің семантикасы келесідей анықталады:

R ÷ S = { т[а1,...,аn] : т ∈ R ∧ ∀с ∈ S ( (т[а1,...,аn] ∪ с) ∈ R) }

(6)

қайда {а₁,...,а_n} - тек өзіне ғана тән атрибут атауларының жиынтығы R және т[а₁,...,а_n] дегеніміз - шектеу т осы жиынтыққа. Әдетте атрибут аттарының тақырыбында болуы қажет S солардың жиынтығы R өйткені әйтпесе операцияның нәтижесі әрқашан бос болады.

Негізгі операциялармен бөлуді модельдеу келесідей. Біз мұны болжаймыз а₁,...,а_n тек төлсипат атаулары болып табылады R және б₁,...,б_м атрибуттары болып табылады S. Бірінші қадамда біз жобалаймыз R оның бірегей төлсипат атауларында және барлық тіркесімдерді курорттармен салыңыз S:

Т : = π_а1,...,аn(R) × S

Алдыңғы мысалда, T кестені ұсынады, өйткені әр студент (ол Толтырылған кестенің ерекше кілт / атрибуты болғандықтан) әрбір берілген тапсырмамен біріктіріледі. Мысалы, Евгенийде екі қатар болады: Евгений → Деректер базасы1 және Евгений → Деректер базасы2.

Э.Г .: Алдымен, «Аяқталды» дегеннің «баға» деп аталатын үшінші атрибутына ие болып көрінейік. Бұл жерде қажет емес жүк, сондықтан біз оны әрдайым алып тастауымыз керек. Іс жүзінде бұл қадамда біз R-ден 'Task' тастай аламыз; көбейту оны қайтадан қояды.

Т : = π_{Студент}(R) × S // Бұл бізге кез-келген ықтимал комбинацияны, соның ішінде R-де жоқтығын және басқаларын қоспағанда береді (мысалы, Fred | компилятор1, бұл қажет тіркесім емес)

Келесі қадамда біз шегереміз R бастап Т

қатынас:

U := Т − R

Жылы U бізде болуы мүмкін «мүмкін» комбинациялар бар R, бірақ болған жоқ.

ЭГ: Тағы да проекциялармен - Т және R бірдей атрибуттардың аттары / тақырыптары болуы керек.

U := Т - π_{Студент, тапсырма}(R) // Бұл бізге «не жетіспейтін» тізімді береді.

Сонымен, егер атрибут атауларына проекцияны тек ерекше деп алсақ R

онда бізде кортеждердің шектеулері бар R ол үшін кортеждермен біріктірілген комбинациялар жоқ S қатысқан R:

V : = π_а1,...,аn(U)

EG: жоба U тек атрибутқа (қасиеттерге) дейін (Студент)

V : = π_{Студент}(U)

Сонымен, проекциясын қабылдау керек R оның ерекше атрибуттары бойынша және оларды алып тастаңыз V:

W : = π_а1,...,аn(R) − V

ЭГ: W : = π_{Студент}(R) − V.

Жалпы кеңейтулер

Іс жүзінде жоғарыда сипатталған классикалық реляциялық алгебра сыртқы қосылыстар, агрегаттық функциялар және транзиттік жабылу сияқты әр түрлі операциялармен кеңейтіледі.^[5]

Сыртқы қосылады

Қосылудың (немесе ішкі қосылыстың) нәтижесі екі операндтағы сәйкес кортеждерді біріктіру нәтижесінде пайда болған кортеждерден құралған болса, сыртқы біріктіруге сол кортеждер және қосымша операндалардың біріне теңестірілмеген кортежді «толтыру» мәндерімен кеңейту арқылы құрылған кейбір кортеждер кіреді. басқа операнд атрибуттарының әрқайсысы үшін. Сыртқы қосылыстар осы уақытқа дейін талқыланған классикалық реляциялық алгебраның бөлігі болып саналмайды.^[6]

Осы бөлімде анықталған операторлар а-ның болуын болжайды нөл мәні, ω, біз анықтамаймыз, толтыру мәндері үшін қолдану керек; іс жүзінде бұл сәйкес келеді ЖОҚ SQL-де. Алынған кестедегі келесі таңдау операцияларын мағыналы ету үшін нөлдерге мағыналық мағына беру керек; Кодд тәсілінде таңдау қолданатын пропорционалды логика болып табылады үш мәнді логикаға дейін кеңейтілген дегенмен, біз осы мақалада осы егжей-тегжейлерді қарастырамыз.

Үш сыртқы біріктіру операторы анықталды: сол жақ сыртқы қосылыс, оң жақ сыртқы қосылыс және толық сыртқы біріктіру. («Сыртқы» сөзі кейде алынып тасталады).

Сол жақтағы қосылыс (⟕)

Сол жақтағы қосылыс келесі түрінде жазылады R ⟕ S қайда R және S болып табылады қарым-қатынастар.^[7] Сол жақтағы қосылудың нәтижесі - бұл кортеждердің барлық тіркесімдерінің жиынтығы R және S жалпы атрибуттық атауларына тең, сонымен қатар (еркін түрде) R сәйкес келетін кортеждері жоқ S.

Мысал үшін кестелерді қарастырайық Қызметкер және Бөлім және олардың сол жақ сыртқы қосылыстары:

Алынған қатынаста кортеждер S кортеждері бар жалпы төлсипат атауларында ортақ мәндері жоқ R а нөл мәні, ω.

Кірістер жоқ болғандықтан Бөлім а DeptName туралы Қаржы немесе Атқарушы, ωs кортеждер пайда болатын қатынастарда пайда болады Қызметкер бар DeptName туралы Қаржы немесе Атқарушы.

Келіңіздер р₁, р₂, ..., р_n қатынастың атрибуттары болу R және {(ω, ..., ω) атрибуттар бойынша жалғыз байланыс болуы керек бірегей қатынасқа S (атрибуттары болып табылмайтындар) R). Содан кейін сол жақтағы қосылысты табиғи қосылысқа қатысты сипаттауға болады (демек, негізгі операторларды қолдана отырып):

${ displaystyle (R bowtie S) cup ((R- pi _ {r_ {1}, r_ {2}, dots, r_ {n}} (R bowtie S)) times {( омега, нүктелер омега) })}$

Оң жақ сыртқы қосылыс (⟖)

Оң жақ сыртқы қосылыс сол жақ сыртқы қосылумен бірдей дерлік әрекет етеді, бірақ кестелердің рөлдері ауысады.

Оң жақ сыртқы қосылысы қарым-қатынастар R және S ретінде жазылады R ⟖ S.^[8] Оң жақ сыртқы қосылыстың нәтижесі - бұл кортеждердің барлық тіркесімдерінің жиынтығы R және S ішіндегі кортеждерден басқа, олардың жалпы төлсипат атауларына тең S сәйкес келетін кортеждері жоқ R.

Мысалы, кестелерді қарастырайық Қызметкер және Бөлім және олардың сыртқы қосылыстары:

Алынған қатынаста кортеждер R кортеждері бар жалпы төлсипат атауларында ортақ мәндері жоқ S а нөл мәні, ω.

Кірістер жоқ болғандықтан Қызметкер а DeptName туралы Өндіріс, ωлар пайда болған қатынастың Name және EmpId атрибуттарында кездеседі, мұндағы кортеждер Бөлім болған DeptName туралы Өндіріс.

Келіңіздер с₁, с₂, ..., с_n қатынастың атрибуттары болу S және {(ω, ..., ω) атрибуттар бойынша жалғыз байланыс болуы керек бірегей қатынасқа R (атрибуттары болып табылмайтындар) S). Содан кейін, сол жақ қосылыстағы сияқты, оң жақ сыртқы қосылысты табиғи қосылысты келесідей етіп модельдеуге болады:

${ displaystyle (R bowtie S) cup ( {( omega, dots, omega) } times (S- pi _ {s_ {1}, s_ {2}, dots, s_ { n}} (R bowtie S))}}$

Толық сыртқы қосылыс (⟗)

The сыртқы біріктіру немесе толық сыртқы қосылыс іс жүзінде сол және оң жақ сыртқы қосылыстардың нәтижелерін біріктіреді.

Толық сыртқы қосылыс ретінде жазылады R ⟗ S қайда R және S болып табылады қарым-қатынастар.^[9] Толық сыртқы қосылудың нәтижесі - бұл кортеждердің барлық тіркесімдерінің жиынтығы R және S ішіндегі кортеждерден басқа, олардың жалпы төлсипат атауларына тең S сәйкес келетін кортеждері жоқ R және кортеждер R сәйкес келетін кортеждері жоқ S олардың жалпы атрибуттық атауларында.

Мысал үшін кестелерді қарастырайық Қызметкер және Бөлім және олардың сыртқы қосылыстары:

Алынған қатынаста кортеждер R кортеждері бар жалпы төлсипат атауларында ортақ мәндері жоқ S а нөл мәні, ω. Кіреберістер S кортеждері бар жалпы төлсипат атауларында ортақ мәндері жоқ R сонымен қатар а нөл мәні, ω.

Толық сыртқы біріктіруді сол және оң жақ сыртқы қосылыстардың көмегімен модельдеуге болады (демек, табиғи қосылу және жиынтық біріктіру):

R ⟗ S = (R ⟕ S) ∪ (R ⟖ S)

Домендік есептеулерге арналған операциялар

Реляциялық алгебрада деректер домендерінде есептеулер жүргізуге мүмкіндік беретін ештеңе жоқ (теңдікке қатысты пропозициялық өрнектерді бағалаудан басқа). Мысалы, екі бағандағы сандарды көбейтетін өрнек жазу үшін осы уақытқа дейін енгізілген алгебраны ғана қолдану мүмкін емес, мысалы. жалпы бағаны алу үшін саны бар бірлік бағасы. Сұраныстың практикалық тілдері осындай мүмкіндіктерге ие, мысалы. SQL SELECT арифметикалық операцияларға нәтижеде жаңа бағандарды анықтауға мүмкіндік береді ТАҢДАУ тауар өлшемінің бағасы * саны AS жалпы_баға КІМДЕН т, және ұқсас нысанды неғұрлым айқын қамтамасыз етілген Оқу құралы D Келіңіздер ҰЗАРТУ кілт сөз.^[10] Деректер қоры теориясында бұл деп аталады кеңейтілген проекция.^[11]:213

Жиынтық

Сонымен қатар, бағанға әртүрлі функцияларды есептеу, оның элементтерін қорытындылау сияқты, осы уақытқа дейін енгізілген реляциялық алгебраның көмегімен де мүмкін емес. Бесеуі бар жиынтық функциялар көптеген реляциялық мәліметтер қоры жүйелеріне енгізілген. Бұл операциялар - қосынды, санақ, орташа, максимум және минимум. Реляциялық алгебрада схема бойынша біріктіру әрекеті (A₁, A₂, ... A_n) келесідей жазылады:

${ displaystyle G_ {1}, G_ {2}, ldots, G_ {m} g_ {f_ {1} ({A_ {1}} '), f_ {2} ({A_ {2}}') , ldots, f_ {k} ({A_ {k}} ')} (r)}$

қайда A_j', 1 ≤ j ≤ к, бастапқы атрибуттардың бірі болып табылады A_мен, 1 ≤ мен ≤ n.

Алдыңғы атрибуттар ж SQL ішіндегі «топтастыру» сөйлемі сияқты жұмыс жасайтын атрибуттар. Содан кейін жеке атрибуттарға қолданылатын біріктіру функцияларының ерікті саны бар. Операция ерікті қатынасқа қолданылады р. Топтастырудың атрибуттары міндетті емес, егер олар жеткізілмеген болса, біріктіру функциялары операция қолданылатын барлық қатынасқа қолданылады.

Бізде кесте бар деп есептейік Тіркелгі үш бағанмен, атап айтқанда Есептік жазбаның нөмірі, филиалдың аты және Баланс. Әр филиалдың максималды балансын табуды қалаймыз. Мұны жүзеге асырады _{Тармақ_аты}G_{Максимум (Баланс)}(Тіркелгі). Барлық шоттардың ең жоғары сальдосын филиалына қарамай табу үшін жай ғана жаза алдық G_{Максимум (Баланс)}(Тіркелгі).

Өтпелі жабу

Реляциялық алгебра практикалық мақсаттар үшін жеткілікті қуатты болып көрінгенімен, қарапайым және табиғи операторлар бар қарым-қатынастар оны реляциялық алгебра арқылы өрнектеуге болмайды. Солардың бірі өтпелі жабылу екілік қатынастың Домен берілген Д., екілік қатынасқа жол берейік R ішкі бөлігі болуы керек Д.×Д.. Өтпелі жабылу R⁺ туралы R ең кіші ішкі жиыны болып табылады Д.×Д. бар R және келесі шартты қанағаттандырады:

${ displaystyle forall x forall y forall z left ((x, y) in R ^ {+} wedge (y, z) in R ^ {+} rightarrow (x, z) in R ^ {+} оң)}$

Реляциялық алгебра өрнегі жоқ E(R) қабылдау R шығаратын айнымалы аргумент ретінде R⁺. Мұны реляциялық өрнек келтіре отырып дәлелдеуге болады E ол үшін бұл талап етіледі E(R) = R⁺, қайда R айнымалы болып табылады, біз әрқашан дананы таба аламыз р туралы R (және тиісті домен г.) солай E(р) ≠ р⁺.^[12]

SQL дегенмен бұларды ресми түрде қолдайды fixpoint сұраулары 1999 жылдан бастап және оның осы бағытта сатушыларға арналған кеңейтімдері болған.

Сұраныстарды оңтайландыру үшін алгебралық қасиеттерді қолдану

Сұрақтар ретінде ұсынылуы мүмкін ағаш, қайда

• ішкі түйіндер - операторлар,
• жапырақтары қарым-қатынастар,
• кіші ағаштар қосалқы өрнектер болып табылады.

Біздің басты мақсатымыз - экспрессиялық ағаштарды эквивалентке айналдыру ағаштар, мұнда ағаштағы субэкспрессиялар арқылы туындайтын қатынастардың орташа мөлшері бұрынғыдан кішірек оңтайландыру. Біздің екінші мақсатымыз - бір сұрау шеңберінде жалпы субэкспрессия құруға тырысу, немесе егер бір уақытта бірнеше сұраныс бағаланса, сол сұраулардың барлығында. Екінші мақсаттың негізі мынада: жалпы субэкспрессияларды бір рет есептеу жеткілікті, ал нәтижелер осы субэкпрессияны қамтитын барлық сұрауларда қолданыла алады.

Мұнда біз осындай түрлендірулерде қолдануға болатын ережелер жиынтығын ұсынамыз.

Таңдау

Іріктеу операторлары туралы ережелер сұранысты оңтайландыруда маңызды рөл атқарады. Таңдау - бұл өз операндындағы жолдар санын өте тиімді түрде азайтатын оператор, сондықтан егер өрнек ағашындағы таңдауды жапыраққа қарай жылжытсақ, ішкі қарым-қатынастар (субэкспрессия арқылы алынған) ықшамдалуы мүмкін.

Негізгі таңдау қасиеттері

Таңдау идемпотентті (бірдей таңдаудың бірнеше қосымшасы біріншісінен тыс қосымша әсер етпейді), және ауыстырмалы (тапсырыс таңдауының қолданылуы түпкілікті нәтижеге әсер етпейді).

1. ${ displaystyle sigma _ {A} (R) = sigma _ {A} sigma _ {A} (R) , !}$
2. ${ displaystyle sigma _ {A} sigma _ {B} (R) = sigma _ {B} sigma _ {A} (R) , !}$

Күрделі шарттары бар таңдауды бұзу

Шарты a болатын таңдау конъюнкция қарапайым шарттар бірдей жеке шарттары бар таңдау тізбегіне және шарты а болатын таңдауға сәйкес келеді дизъюнкция таңдаулар одағына тең. Бұл сәйкестікті таңдауларды азырақ бағалау қажет болатындай етіп таңдауды біріктіру үшін немесе компоненттерді бөлек жылжыту немесе оңтайландыру үшін оларды бөлу үшін пайдалануға болады.

1. ${ displaystyle sigma _ {A land B} (R) = sigma _ {A} ( sigma _ {B} (R)) = sigma _ {B} ( sigma _ {A} (R) )}$
2. ${ displaystyle sigma _ {A lor B} (R) = sigma _ {A} (R) cup sigma _ {B} (R)}$

Таңдау және кросс-өнім

Кросс өнім бағалаудың ең қымбат операторы болып табылады. Егер кіріс қарым-қатынастар бар N және М жолдар, нәтиже болады ${ displaystyle NM}$ жолдар. Сондықтан кросс-өнім операторын қолданар алдында екі операндтың көлемін азайту үшін бар күшімізді салу өте маңызды.

Мұны тиімді түрде жасауға болады, егер кросс өнімнен кейін таңдау операторы жүрсе, мысалы. ${ displaystyle sigma _ {A} (R рет P)}$. Қосылудың анықтамасын ескере отырып, бұл ең ықтимал жағдай. Егер кросс-өнімнің артынан таңдау операторы жүрмесе, біз басқа таңдау ережелерін қолдана отырып, өрнек ағашының жоғары деңгейлерінен таңдауды төмендетуге тырысамыз.

Жоғарыдағы жағдайда біз шартты бұзамыз A жағдайға B, C және Д. күрделі таңдау шарттары туралы сплит ережелерін қолдану, осылайша ${ displaystyle A = B сына C сына D}$ және B тек атрибуттарды қамтиды R, C тек атрибуттарды қамтиды P, және Д. бөлігін қамтиды A екеуінің де атрибуттарын қамтиды R және P. Ескертіп қой B, C немесе Д. бос болуы мүмкін. Содан кейін келесідей:

${ displaystyle sigma _ {A} (R есе P) = sigma _ {B сына C сына D} (R есе P) = sigma _ {D} ( sigma _ {B} (R ) times sigma _ {C} (P))}$

Операторларды таңдау және орнату

Таңдау тарату орнатылған айырмашылық, қиылысу және біріктіру операторлары. Келесі үш ереже өрнек ағашындағы орнатылған амалдардан төмен таңдауды итеру үшін қолданылады. Орнатылған айырмашылық пен қиылысу операторлары үшін таңдау операторын түрлендіруден кейінгі операндалардың біріне ғана қолдануға болады. Бұл операндтардың біреуі кіші болған жағдайда тиімді болуы мүмкін, ал таңдау операторын бағалаудың артықшылығы кішірек нұсқаны пайдаланудан артық болады қатынас операнд ретінде.

1. ${ displaystyle sigma _ {A} (R setminus P) = sigma _ {A} (R) setminus sigma _ {A} (P) = sigma _ {A} (R) setminus P}$
2. ${ displaystyle sigma _ {A} (R кесе P) = sigma _ {A} (R) кубок sigma _ {A} (P)}$
3. ${ displaystyle sigma _ {A} (R cap P) = sigma _ {A} (R) cap sigma _ {A} (P) = sigma _ {A} (R) cap P = R cap sigma _ {A} (P)}$

Таңдау және проекциялау

Егер таңдау шартында көрсетілген өрістер проекциядағы өрістердің ішкі жиыны болса ғана, таңдау проекциямен жүреді. Проекцияға дейін таңдауды орындау операнд кросс өнім немесе біріктіру болған жағдайда пайдалы болуы мүмкін. Басқа жағдайларда, егер таңдау шартын есептеу салыстырмалы түрде қымбатқа түсетін болса, проекциядан тыс жылжу таңдаудың тексерілуі керек кортеждердің санын азайтуы мүмкін (өйткені проекцияда өткізіп алған өрістердің нәтижесінде қайталанатын көшірмелердің жойылуына байланысты аз кортеждер пайда болуы мүмкін).

${ displaystyle pi _ {a_ {1}, ldots, a_ {n}} ( sigma _ {A} (R)) = sigma _ {A} ( pi _ {a_ {1}, ldots , a_ {n}} (R)) { text {мұндағы өрістер}} A subseteq {a_ {1}, ldots, a_ {n} }}$

Болжам

Негізгі проекциялық қасиеттері

Проекция идемпотентті, сондықтан проекциялар қатары (жарамды) сыртқы проекцияға эквивалентті болады.

${ displaystyle pi _ {a_ {1}, ldots, a_ {n}} ( pi _ {b_ {1}, ldots, b_ {m}} (R)) = pi _ {a_ {1 }, ldots, a_ {n}} (R) { text {қайда}} {a_ {1}, ldots, a_ {n} } subseteq {b_ {1}, ldots, b_ { м} }}$

Проекциялау және орнату операторлары

Проекциялау тарату белгіленген одақ.

${ displaystyle pi _ {a_ {1}, ldots, a_ {n}} (R кесе P) = pi _ {a_ {1}, ldots, a_ {n}} (R) cup pi _ {a_ {1}, ldots, a_ {n}} (P). ,}$

Проекция қиылысу бойынша бөлінбейді және айырмашылықты орнатады. Қарсы мысалдар келтірілген:

${ displaystyle pi _ {A} ( { langle A = a, B = b rangle } cap { langle A = a, B = b ' rangle }) = emptyset}$

${ displaystyle pi _ {A} ( { langle A = a, B = b rangle }) cap pi _ {A} ( { langle A = a, B = b ' rangle }) = { langle A = a rangle }}$

және

${ displaystyle pi _ {A} ( { langle A = a, B = b rangle } setminus { langle A = a, B = b ' rangle }) = { langle = a rangle }}$

${ displaystyle pi _ {A} ( { langle A = a, B = b rangle }) setminus pi _ {A} ( { langle A = a, B = b ' rangle }) = emptyset ,,}$

қайда б ерекшеленеді деп болжануда b '.

Атын өзгерту

Атаулардың негізгі қасиеттері

Айнымалының кезекті атауын бір атау етіп жинауға болады. Жалпыға ортақ айнымалысы жоқ атауды өзгерту бір-біріне қатысты ерікті түрде қайта реттелуі мүмкін, оны пайдаланып, оларды ығыстыруға болатын етіп, қатарлас атау жасауға болады.

1. ${ displaystyle rho _ {a / b} ( rho _ {b / c} (R)) = rho _ {a / c} (R) , !}$
2. ${ displaystyle rho _ {a / b} ( rho _ {c / d} (R)) = rho _ {c / d} ( rho _ {a / b} (R)) , ! }$

Операторлардың атауын өзгерту және орнату

Атын өзгерту жиынтық айырмашылыққа, біріктіруге және қиылысқа бөлінеді.

1. ${ displaystyle rho _ {a / b} (R setminus P) = rho _ {a / b} (R) setminus rho _ {a / b} (P)}$
2. ${ displaystyle rho _ {a / b} (R кесе P) = rho _ {a / b} (R) cup rho _ {a / b} (P)}$
3. ${ displaystyle rho _ {a / b} (R cap P) = rho _ {a / b} (R) cap rho _ {a / b} (P)}$

Өнім және кәсіподақ

Декарттық өнім одаққа қарай таралады.

1. ${ displaystyle (A есе B) кубок (A рет C) = A рет (B кесе C)}$

Іске асыру

Кодд алгебрасына негізделген алғашқы сұрау тілі - доктор Коддтың өзі жасаған Альфа. Кейіннен, ISBL құрылды, және бұл ізашарлық жұмысты көптеген органдар мақтады [1] Коддтың идеясын пайдалы тілге айналдыру жолын көрсеткендей. Бизнес жүйесі 12 ISBL үлгісін ұстанған қысқа мерзімді салалық қатынасты ДҚБЖ болды.

1998 жылы Крис Дата және Хью Дарвен деп аталатын тілді ұсынды Оқу құралы D реляциялық мәліметтер қорының теориясын оқытуда қолдануға арналған және оның сұрау тілі ISBL идеяларына сүйенеді. Рел жүзеге асыру болып табылады Оқу құралы D.

Тіпті SQL реляциялық алгебраға негізделген, бірақ SQL-дегі операндтар (кестелер ) дәл емес қарым-қатынастар және реляциялық алгебра туралы бірнеше пайдалы теоремалар SQL аналогында болмайды (оптимизаторларға және / немесе пайдаланушыларға зиян келтіруі мүмкін). SQL кестесінің моделі - бұл сөмке (мультисет ) емес, жиынтық. Мысалы, өрнек ${ displaystyle (R cup S) setminus T = (R setminus T) cup (S setminus T)}$ жиынтықтардағы реляциялық алгебра үшін теорема, бірақ сөмкелердегі реляциялық алгебра үшін емес; реляциялық алгебраны сөмкелермен емдеу үшін «Толық» оқулығының 5-тарауын қараңыз Гарсия-Молина, Ульман және Widom.^[11]

Сондай-ақ қараңыз

Әдебиеттер тізімі

Әрі қарай оқу

Деректер базасындағы кез-келген академиялық оқулықта классикалық реляциялық алгебра егжей-тегжейлі қарастырылған.

• Имиелиски, Т.; Липски, В. (1984). «Мәліметтердің реляциялық моделі және цилиндрлік алгебралар». Компьютерлік және жүйелік ғылымдар журналы. 28: 80–102. дои:10.1016/0022-0000(84)90077-1. (Қарым-қатынас үшін цилиндрлік алгебралар ).

Сыртқы сілтемелер

Бұл мақала қолдану сыртқы сілтемелер Википедия ережелері мен нұсқаулықтарын сақтамауы мүмкін. өтінемін осы мақаланы жақсарту жою арқылы шамадан тыс немесе орынсыз сыртқы сілтемелер және қажет болған жағдайда пайдалы сілтемелерді түрлендіру сілтеме сілтемелері. (2017 жылғы қаңтар) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

• RAT. SQL-ге реляциялық алгебра аудармашысы
• Дәріс конспектілері: Реляциялық алгебра - SQL сұрауларын реляциялық алгебраға бейімдеуге арналған жылдам оқулық
• Реляциялық - реляциялық алгебраның графикалық орындалуы
• Сұраны оңтайландыру Бұл жұмыс реляциялық алгебраны сұраныстарды оңтайландыруда қолдануға кіріспе болып табылады және тереңірек зерттеу үшін көптеген дәйексөздерден тұрады.
• Oracle және Microsoft SQL Server үшін реляциялық алгебра жүйесі
• Pireal - Реляциялық алгебрамен жұмыс істеуге арналған эксперименттік білім беру құралы
• DES - реляциялық алгебра және басқа ресми тілдермен жұмыс істеуге арналған оқу құралы
• RelaX - реляциялық алгебра калькуляторы (тіркеусіз интернет-қызмет ретінде қол жетімді ашық бастапқы бағдарламалық жасақтама)
• RA: реляциялық алгебра аудармашысы
• SQL-ді реляциялық алгебраға аудару