Кіріспе

Реляциялық деректер қоры теориясы

Деректер қоры теориясында реляциялық алгебра – деректерді модельдеу үшін алгебралық құрылымдарды пайдаланатын және дұрыс негізделген семантикамен сұраныстарды анықтайтын теория. Теорияны Эдгар Ф. Кодд енгізді. Реляциялық алгебраның басты қолданысы – реляциялық деректер қорына теориялық негіз беру, әсіресе мұндай деректер қорына арналған сұрау тілдері, олардың ішінде SQL ең маңыздысы. Реляциялық деректер қоры қатынастар түрінде ұсынылған кестелік деректерді сақтайды. Реляциялық деректер қорына жасалған сұраулар көбінесе қатынастар түрінде ұсынылған кестелік деректерді қайтарады. Реляциялық алгебраның негізгі мақсаты – бір немесе бірнеше кіріс қатынастарын шығыс қатынасына түрлендіретін операторларды анықтау. Осы операторлар қатынастарды кіріс ретінде қабылдап, қатынастарды шығыс ретінде шығаратындықтан, оларды біріктіріп, деректері деректер қорында сақталатын бірнеше кіріс қатынастарын бір шығыс қатынасына (сұрау нәтижесіне) түрлендіретін күрделі сұрауларды білдіруге болады. Унар операторлар бір қатынасты кіріс ретінде қабылдайды. Мысалға, кіріс қатынасынан белгілі бір атрибуттарды (бағандарды) немесе жазбаларды (жолдарды) сүзуге арналған операторларды жатқызуға болады. Бинар операторлар екі қатынасты кіріс ретінде қабылдайды және оларды бір шығыс қатынасына біріктіреді. Мысалы, екі қатынаста да кездесетін барлық жазбаларды (бірінді) алу, екінші қатынаста кездесетін бірінші қатынастағы жазбаларды жою (айырма), бірінші қатынастағы жазбаларды екінші қатынастағы жазбалармен белгілі бір шарттарға сәйкес кеңейту және т.б. Басқа да жетілдірілген операторларды қосуға болады, онда белгілі бір операторларды қосу немесе алып тастау алгебралар отбасын құрайды.

Кіріспе

Реляциялық алгебраға 1970 жылы Э.Ф. Коддтың деректердің реляциялық моделі жарияланғанға дейін таза математикадан тыс жерлерде көңіл аз бөлінді. Кодд мұндай алгебраны деректер базасына сұрау тілдерінің негізі ретінде ұсынды. (Қолданылу бөлімін қараңыз.) Реляциялық алгебра біртекті түбірлер жиынтығымен жұмыс істейді, мұнда m – кестедегі қатарлар саны, ал n – бағандар саны деп түсіндіріледі. Әрбір бағандағы барлық элементтер бірдей типте болады. Кодд алгебрасының бес бастауыш операторы – таңдау, проекция, Картезиан көбейтіндісі (кейде қиылыс көбейтіндісі немесе қиылыс қосылысы деп те аталады), жиынтық біріктіру және жиынтық айырмашылығы.

Орнатушылар

Реляциялық алгебра жиын теориясынан жинақтардың бірігуін, жинақтардың айырмашылығын және Картезиандық көбейтуді пайдаланады, бірақ бұл операторларға қосымша шектеулер қояды. Жинақтардың бірігуі мен жинақтардың айырмашылығы үшін қатыстырылған екі реляция да бірігуге үйлесімді болуы керек – яғни, екі реляцияның атрибуттар жиыны бірдей болуы керек. Жинақтардың қиылысы жинақтардың бірігуі және жинақтардың айырмашылығы арқылы анықталғандықтан, жинақтардың қиылысына қатыстырылған екі реляция да бірігуге үйлесімді болуы керек. Картезиандық көбейтудің анықталуы үшін қатыстырылған екі реляцияның тақырыптары (header) бөлек болуы керек – яғни, оларда ортақ атрибут атауы болмауы керек. Сонымен қатар, Картезиандық көбейту жиын теориясындағыдан өзгеше анықталады, операция мақсаты үшін туплдар "жазық" деп есептеледі. Яғни, n туплдар жиынының m туплдар жиынымен Картезиандық көбейтуі "жазықталған" (n + m) туплдар жиынын береді (ал негізгі жиын теориясы әрқайсысында n тупл және m тупл бар 2 туплдар жиынын қарастырар еді). Формальды түрде R × S келесідей анықталады:

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

Жобалау ()

Проекция – атрибут атаулары жиынтығы ретінде жазылатын унарлық операция. Мұндай проекцияның нәтижесі – R жиынындағы барлық кортеждер атрибуттар жиынына шектелгенде алынатын жиын. Ескерту: SQL стандартында іске асырылғанда "стандартты проекция" жиынның орнына көп жиынтық қайтарады, ал дубликатты деректерді жою үшін Π проекциясы DISTINCT кілт сөзін қосу арқылы қол жеткізіледі.

Таңдау (σ)

Жалпыланған таңдау – бұл бірлік операция, жазылуы мынадай: , мұнда – нормальді таңдауда рұқсат етілген атомдардан және логикалық операторлардан (және), (немесе) және (жоққа шығару) тұратын логикалық формула. Бұл таңдау R қатынасынан формуланың орындалатын барлық жазбаларды таңдайды. Мысалы, адрестік кітапшадағы барлық достар мен іскер серіктестердің тізімін алу үшін таңдау мына түрде жазылуы мүмкін: . Нәтижесінде size=90% шарты орындалатын әрбір ерекше жазбаның барлық атрибуттарын қамтитын қатынас пайда болады.

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

Атын өзгерту – бұл унарлық операция, ол былай жазылады: , мұнда нәтиже R-мен толықтай сәйкес келеді, бірақ барлық жазбалардағы b атрибуты a атрибуты деп қайта аталды. Бұл қатынастың атрибутын немесе қатынастың өзін қайта атау үшін қолданылады. Мысалы, қатынастағы "isFriend" атрибутын "isBusinessContact" деп өзгерту үшін қолданылуы мүмкін. Сондай-ақ, жазбасы бар, онда R x деп қайта аталса, ал атрибуттары деп аталды.

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

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

Сыртқы буындар

Бірлесудің (немесе ішкі біріктірудің) нәтижесі екі операнда сәйкес келетін тупларды біріктіру арқылы құрылған туплардан тұрады, ал сыртқы біріктіруде осы туплармен қатар, екінші операндағы белгілі бір атрибуттар үшін «толтыру» мәндерімен кеңейтілген, сәйкес келмеген туплар да болады. Сыртқы біріктірулер осы уақытқа дейін талқыланған классикалық реляциялық алгебраның құрамына кірмейді. Осы бөлімде анықталған операторлар, толтыру мәндері үшін пайдаланылатын нөлдік мән, ω, бар екенін қарастырады, біз оны анықтамаймыз; практикалық тұрғыда бұл SQL-дегі NULL-ге сәйкес келеді. Нәтижедегі кестедегі келесі таңдау операцияларын мағыналы ету үшін нөлдерге семантикалық мағына тағайындалуы керек; Коддтың тәсілінде таңдау үшін қолданылатын мәндік логика үшмәнді логикаға дейін кеңейтіледі, бірақ біз осы мақалада бұл егжей-тегжейлі мәліметтерді жіберуге рұқсат етеміз. Үш сыртқы біріктіру операторы анықталған: сол жақ сыртқы біріктіру, оң жақ сыртқы біріктіру және толық сыртқы біріктіру. ("Сыртқы" деген сөз кейде алынып тасталады.)

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

Осы уақытқа дейін енгізілген реляциялық алгебрада деректер домендеріндегі есептеулерді (теңдік қатысты пропозициялық өрнектерді бағалаудан басқа) жүзеге асыруға мүмкіндік беретін ештеңе жоқ. Мысалы, екі бағандағы сандарды көбейту үшін – бірлік бағасын санына көбейтіп, жалпы соманы алу үшін – тек қана осы алгебраны қолдану мүмкін емес. Бірақ, практикалық сұраныс тілдерінде мұндай мүмкіндіктер бар, мысалы, SQL SELECT арифметикалық операцияларды пайдаланып нәтижеде жаңа бағандарды анықтауға мүмкіндік береді: SELECT бірлік бағасы * саны ТОЛЫҚ баға РЕТІНДЕ t, ал Tutorial D-нің EXTEND кілт сөзі осыған ұқсас мүмкіндікті одан да нақтырақ қамтамасыз етеді. Деректер базасы теориясында мұны кеңейтілген проекция деп атайды.

Транзитивті жабылу

Реляциялық алгебра көптеген практикалық мақсаттар үшін жеткілікті қуатты көрінсе де, реляциялық алгебра арқылы өрнектеуге келмейтін қатынастардағы кейбір қарапайым және табиғи операторлар бар. Олардың бірі – екілік қатынастың транзитивті жабылуы. D доменін қарастыра отырып, R екілік қатынасы D×D жиынының ішкі жиыны болсын. R-дың транзитивті жабылуы R+ – R-ды қамтитын және келесі шартты қанағаттандыратын D×D жиынының ең кіші ішкі жиыны болып табылады: R-ді айнымалы аргумент ретінде қабылдап, R+ шығаратын реляциялық алгебра өрнегі E(R) жоқ екенін дәлелдеуге болады. Дегенмен, SQL 1999 жылдан бері мұндай бекітілген нүктелік сұраныстарды ресми түрде қолдайды, ал оған дейін де осы бағыттағы жеткізушіге қатысты кеңейтімдер болған.

Таңдау

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

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

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

Күрделі шарттармен таңдап алуды ажырату

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

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

Кросс-көбейту – бағалау үшін ең қымбат оператор. Егер кіріс қатынастарында N және M қатарлар болса, нәтижеде N*M қатар болады. Сондықтан, кросс-көбейту операторын қолданудан бұрын екі операндтың да мөлшерін азайту маңызды. Бұл тиімді түрде, егер кросс-көбейтуден кейін іріктеу операторы қолданылса, мысалы, қосылудың анықтамасын ескере отырып, бұл ең мүмкін жағдай. Егер кросс-көбейтуден кейін іріктеу операторы келмесе, біз өрнек ағашының жоғары деңгейлерінен басқа іріктеу ережелерін қолдана отырып, іріктеуді төмен түсіруге тырыса аламыз. Жоғарыдағы жағдайда А шарты күрделі іріктеу шарттарына қатысты бөлу ережелерін қолдану арқылы B, C және D шарттарына бөлінеді, сондықтан B тек R-дан атрибуттарды, C тек P-дан атрибуттарды, ал D – R және P-дан атрибуттарды қамтитын А бөлігін қамтиды. Есімізде болсын, B, C немесе D бос болуы мүмкін. Онда келесідей шарт орындалады:

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

Таңдау жинақ айырмашылығы, қиылысу және одақ операторлары бойынша үлестіріледі. Өрнек ағашындағы жинақтық операциялардың астына таңдауды түсіру үшін келесі үш ереже қолданылады. Жинақ айырмашылығы және қиылысу операторлары үшін, түрлендіруден кейін таңдау операторын тек бір операндқа қолдану мүмкін. Егер операндардың бірі шағын болса, бұл тиімді болуы мүмкін, ал таңдау операторын есептеуге кеткен қосымша шығын кіші қатынасты операнд ретінде пайдаланудың пайдасын басып өтеді.

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

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

Бастапқы проекциялық қасиеттері

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

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

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

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

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

Өнім және одақ

Декарт көбейтіндісі біріктіру бойынша таралу заңына бағынады.

Қолданылу

Кодд алгебрасына негізделген алғашқы сұраныс тілі Альфа болды, оны доктор Кодд өзі әзірледі. Содан кейін ISBL құрылды, және бұл пионерлік жұмыс көптеген сарапшылар Коддтың идеясын қолдануға болатын тілге айналдыру жолын көрсеткендігі үшін жоғары бағаланды. Бизнес-жүйе 12 – ISBL үлгісімен жасалған, бірақ қысқа ғұмыр сүрген, өнеркәсіптік деңгейдегі реляциялық СҚДБ болды. 1998 жылы Крис Дате мен Хью Дарвен реляциялық деректер базасы теориясын оқытуға арналған Tutorial D деп аталатын тілді ұсынды, ал оның сұраныс тілі де ISBL идеяларына сүйенеді. Rel – Tutorial D-нің іске асырылуы.

Тіпті SQL сұраныс тілі де реляциялық алгебраға шала-шала негізделген, бірақ SQL-дегі операндар (кестелер) нақты қатынастар емес, сондай-ақ реляциялық алгебраға қатысты бірнеше пайдалы теоремалар SQL-де жарамсыз (мүмкін, оптимизаторлар мен/немесе пайдаланушылар үшін зиянды). SQL кестесінің моделі жиын емес, пакет (көп жиынтық) болып табылады. Мысалы, өрнегі жиындардағы реляциялық алгебра үшін теорема болып табылады, бірақ пакеттердегі реляциялық алгебра үшін емес; пакеттердегі реляциялық алгебраны қарастыру үшін Гарсия Молина, Ульман және Видомның «Толық» оқулығының 5-тарауын қараңыз.