B GIO DC V O TO TRNG I HC s PHM H NI L ấ T H T H U H I N MễT S TNH CHT CA V TRI cc TIấU TRONG LC KHI L U N VN T H C s M Y T N H H NI, 2016 B GIO DC V O TO TRNG I HC s PHM H NI L ấ T H T H U H I N MT S TNH CHT CA V TRI cc TIấU TRONG Lc KHI Chuyờn ngnh: Khoa hc mỏy tớnh Mó s: 60480101 L U N VN T H C s M Y T N H Ngi hng dn khoa hc PGS.TS Trnh ỡnh Thng H NI, 2016 i LI CM N hon thnh lun ny tụi ó nhn c s giỳp tn tỡnh ca thy hng dn khoa hc, ca cỏc thy cụ trng i hc S phm H Ni Tụi xin chõn thnh cm om cỏc thy cụ phũng Sau i Hc, th vin trng i hc S phm H Ni ó to iu kin hc tp, nghiờn cu v giỳp tụi rt nhiu quỏ trỡnh lm lun Tụi xin gi li cm om sõu sc ti thy PGS.TS Tinh ỡnh Thng ang cụng tỏc ti trng i hc S phm H Ni ó trc tip hng dn, nh hng chuyờn mụn, ch bo tụi sut quỏ trỡnh hc tp, nghiờn cu ti v giỳp tụi hon thnh lun ny Tụi xin c by t s bit om sõu sc n gia ỡnh ó to mi iu kin tt nht tụi cú th hon thnh tt mi cụng vic quỏ trỡnh thc hin lun Bờn cnh ú, tụi cng xin gi li cm om ca mỡnh ti bn bố v ng nghip, luụn quan tõm, chia s, ng viờn tụi sut thi gian thc hin lun Trong quỏ trỡnh thc hin cụng tỏc nghiờn cu nhng lun khụng th trỏnh nhng thiu sút Tụi xin chõn thnh cm om nhng ý kin gúp ý ca quý thy cụ, quý ng nghip v bn bố H Ni, ngy thỏng nm 2016 Hc viờn Lờ Th Thu Hin ii LI CAM OAN Tụi xin cam oan ton b ni dung c trỡnh by bn lun ny l kt qu tỡm hiu v nghiờn cu ca riờng tụi, õy l kt qu nghiờn cu ca tụi di s hng dn khoa hc ca PGS.TS Trnh ỡnh Thng Cỏc s liu, kt qu nờu lun l trung thc, rừ rng v cha tng c cụng b bt k cụng trỡnh no khỏc Hoc viờn Lờ Th Thu Hin Ill MUC LUC LICM N i LI CAM OAN ii MC LC iii DANH MC Kí H U V CH CI VIT TT V DANH MC CC BNG vi DANH MC CC HèNH V vii CHNG CC Mễ HèNH D LIU 1.1 Khỏi nim mụ hỡnh d li u 1.2 Mụ hỡnh thc th - liờn kt 1.3 Mụ hỡnh hng i tng 14 Mụ hỡnh phõn cp 1.5 Mụ hỡnh d liu dng datalog 1.6 Mụ hỡnh d liu quan h 1.6.1 Cỏc khỏi nim c bn 1.6.2 Cỏc phộp toỏn i s quan h 10 1.6.3 Ph thuc hm 16 1.6.4 Bao úng 17 1.6.5 Khoỏ ca lc quan h 22 Kt lun 22 CHNG 2: Mễ HèNH D LIU DNG KHI 24 2.1 Khi, lc v lỏt ct 24 2.1.1 Khi, lc 24 2.1.2 Lỏt ct .26 2.2 Cỏc phộp tớnh trờn 28 2.2.1.Phộp chốn 28 ĂV 2.2.2.Phộp loi b .29 2.2.3 Phộp sa i 29 2.3 i s quan h trờn 29 2.3.1 Phộp h p 30 2.3.2 Phộp giao 31 2.3.3 Phộp tr 32 2.3.4 Tớch cỏc 32 2.3.5 Tớch cỏc theo ch s 33 2.3.6 Phộp chiu 33 2.3.7 Phộp chn .34 2.3.8 Phộp kt ni 34 2.3.9 Phộp chia 36 2.4 Ph thuc hm 36 2.5 Bao úng ca thuc tớnh ch s 39 2.6 Khúa ca 40 2.6 Kt lun 42 CHNG MT S TNH CHT CA V TRI cc TIU 43 3.1 Tp cỏc v trỏi cc tiu mụ hỡnh d liu dng 43 3.2 Mt s tớnh cht m rng ca v trỏi cc tiu lc kh 45 KT LU N 50 Ti liu tham kho 51 V DANH MUC Kí HIấU V CH CI VIT TT Trong lun ny dựng thng nht cỏc ký hiu v ch cỏi vit tt sau: K ớhiờu í ngha FD Ph thuc hm LS v i LR v phi h Suy dn theo tiờn (theo logic) b Suy dn theo quan h * Khỏc V Vi mi n Phộp giao u Phộp hp \ Phộp tr c Tp Nm e Thuc Khụng thuc Bao úng ca thuc tớnh X Tng ng m Khụng tng ng Rng Tn ti vi DANH MC CC BNG Bng 1.1 Biu din quan h r Bng 1.2 Biu din vớ d hc sinh Bng 1.3 Bng biu din quan h r, s, r u s Bng 1.4 Bng biu din quan h r, s, r u s Bng 1.5 Bng biu din quan h r, s, r - s, s - r Bng 1.6 Bng biu din cỏc quan h r, s, rx s Bng 1.7 Bng biu din cỏc quan h r, s,r*s Bng 1.8 Bng biu din cỏc quan h r, s,r -r s Bng 2.1 Bng biu din im hc viờn DiemHV(R) Bng 2.3 Bngbiu din lỏt ct r(RHck2) Bng 2.4.Biu din h gm quan h ri r2 DANH MUC CC HèNH V Hỡnh 2.1 Biu din im sinh viờn DiemSV(R) Hỡnh 2.2 Biu din cỏc r(R), s(R), t(R) Hỡnh 2.3 Biu din r, s Hỡnh 2.4 Biu din cỏc r, s, r u s Hỡnh 2.5 Biu din cỏc r, s, r n s Hỡnh 2.6 Biu din cỏc r, s, r - s Hỡnh 2.7 Biu din cỏc r, r = np(r) M U Lớ chn ti Trong vi thp k qua, vi s phỏt trin mnh m ca khoa hc cụng ngh hin i, c bit l cụng ngh in t dn n s ũi hng lot cỏc thit b khụng dõy m bo cỏc thit b hot ng c tt cn phi cú nhng ngun nng lng phự hp, cú dung lng ln, hiu sut cao, cú th dựng li nhiu ln v c bit l gn nh v an ton Ngy nay, cụng ngh thụng tin ang cú nhng bc tin mnh m, vic s dng cụng ngh thụng tin tr nờn rng rói v vai trũ ca cụng ngh thụng tin ngy cng c khng nh nhiu lnh vc khỏc nh: Hc tp, khoa hc k thut, kinh doanh, qun lý vi nhng quy mụ khỏc C s d liu l mt nhng lnh vc nghiờn cu úng vai trũ nn tng s phỏt trin ca cụng ngh thụng tin Mun xõy dng c mt h thng c s d liu tt ngi ta thng s dng cỏc mụ hỡnh d liu thớch hp ó cú rt nhiu mụ hỡnh c s dng cỏc h thng c s d liu nh: Mụ hỡnh thc th - liờn kt, mụ hỡnh mng, mụ hỡnh phõn cp, mụ hỡnh hng i tng, mụ hỡnh d liu datalog v mụ hỡnh quan h Trong ú thỡ mụ hỡnh quan h c quan tõm hn c vỡ nú c xõy dng trờn c s toỏn hc cht ch - ú l lớ thuyt toỏn hc v cỏc quan h cú ỏp dng rng rói cỏc cụng c i s v logic Tuy nhiờn, mụ hỡnh ny cha ỏp ng i vi cỏc ng dng phc tp, cỏc c s d liu cú cu trỳc phi tuyn Vỡ vy tụi chn ti: Mt s tớnh cht ca v trỏi cc tiu lc nhm b sung thờm vo lý thuyt thit k mụ hỡnh d liu dng c y hn Mc ớch nghiờn cu - Tỡm hiu v mụ hỡnh d liu dng - nh ngha tớnh cht ca v trỏi cc tiu trờn lc 37 Cho lc a = (R, F),R = (id; Ai,A2, ,An), F l cỏc ph thuc hm trờn R v X ằ Y l mt ph thuc hm vi X, Y ầ J Núi i=l rng X ằ Y c suy din logic t F nu vi mi r xỏc nh ờn R tha cỏc ph thuc hm ong F thỡ cng tha X ằ Y.K hiu l:F f=x ằ Y nh ngha 2.3 (bao úng ca ph thuc hm) Cho lc R = (id; A h A2, , An ), F l cỏc ph thuc hm trờn R Khi ú bao úng ca Fkớ hiu F+ c xỏc nh nh sau: F4- = {X -ằ Y I F => X >Y} Neu X = {x(m)} ỗ id(m), Y = {yđ} ỗ id(k)thi ta kớ hiu ph thuc hm X ^ Y n gin l x(m)ằ y(k) Khi r tho x(m)^ y(k) nu vi mi ti, t2e r cho ti(x(m)) = t2(x(m)) thỡ ti(yđ) = t 2(y(k)) Trong ú: ti(x(m)) = ti(x; Am), t2(x(m)) = t2(x; Am), ti(y(k)) = ti(y; Ak), t2(y(k)) = t2(y; Ak) Mnh 2.4 Cho R = (id; Al, A2, , An ), r(R) l mt trờn R,x, Y ỗ J i=l XằY l kớ hiu mt ph thuc hm Gi s r(R) tho ph thuc hm X ằ Y Khi ú nu id = {x} thỡ: r(R) tr thnh quan h r(Ai, A2, , An ) v Ph thuc hm X > Y, (X, Y ầ J i=l mụ hỡnh d liu quan h Mnh 2.5 ) thnh ph thuc hm 38 Cho R = (id; Al, A2, , An), r(R) l mt trờn R, x(m)e id(m), x(k) Kx l khúa ca a x G i p x l khúa ca a x cha Kx Ta chng minh: p x= Kx N u px khụng cha v trỏi cc tiu no ca Fhx thỡ IJ ầZKx i=n D o ú px= Kx Gi s px cha v trỏi cc tiu no ú ca Fhx , ú Px ầ Kx m Kx ch cha v trỏi cc tiu nht l Lx => Lx ầ Px t Qx =PX\L X ta cú Px = Lx \Qx 48 ^>QX Qxl siờu khúa ca ax \ x Mt khỏc vỡ Mx l khúa ca ax \x v Qx eMx ^>Qx =Mx Nh vy: Px =LXQX=LXMX=Kx Do ú Kx l khúa ca ax Mnh 3.4 Cho lc v a = (/?,FA)l v trỏi cc tiu L Khi ú VAf G Key(a\ỹx), mi khúa K ca a cha LM phi cha M Chng minh: Gi s ta cú: VM &Key(a\ĩ),K l khúa ca a,K (e LM, ta phi chng minh KdM Tht vy, vỡ K ầ IM m K l khúa ca lc a => IM l siờu khúa ca lc a Ta xột K = PI ngha l K = P vj Q = P r \Q = Vúi p - K r \ L , Q - K r \ M Vỡ LnM = nM = Nờn suy raPnQ l siờu khúa ca a \ Siờu khúa ny cha khúa M ca a \ Do ú theo tớnh cht ti thiu ca khúa Q =M t ú ta cú K cha M (pcm) 49 Mờnh 3.5 Cho er = (R,FfJ,R = (idm , A 1,A 2, ,An), v v trỏi cc tiu L Khi ú \/M x e Key(ax\ x) , mi khúa Kx ca a x cha LxMx u phi cha Mx Chng minh: Gi s Kx l khúa ca ax,Mx e Key(ax \L+ X,KXầ LXMX) Ta phi chng minh Kx d Mj Tht vy, gi s Kx l khúa ca axKx ỗ LXMX,MXe Key(ax\x) Khi ú LXMXl siờu khúa t Kx =PxvQx,vi PxnQx =0 Px =KxnL x,Qx =Kxn M x Vỡ Lxn M x =xn M x =0 ^ P xnQx=0 Trong lỏt ct ca ti X Theo b v siờu khúa phộp dch chuyn lc ta cú Kx\L+ x = Kx\Lx =PxQx \L x =Qx,Q x l siờu khúa ca a, \L\ Khi ú: siờu khúa ny cha Mx ca ax\x Do ú t tớnh cht ti thiu ca khúa trờn lỏt ct ti X => ụ* = Mx Nh vy Kx cha Mx Vjt e id Kt luõn Chng ny trỡnh by cỏc khỏi nim v cỏc tớnh cht m rng ca v trỏi cc tiu lc Nhng kt qu v trỏi cc tiu mụ hỡnh d liu dng c nghiờn cu trờn ó lm rừ thờm cu trỳc thit k ca mụ hỡnh d liu dng v tớnh cht m rng v lc Trong trng hp suy bin thnh quan h thỡ mt s kt qu ny li trựng vi cỏc kt qu ó c nhiu tỏc gi a i vi quan h mụ hỡnh d 50 liu quan h Mt s kt qu khỏc c xột trng hp riờng ca cỏc ph thuc hm F lc nh ph thuc hm Fh, ph thuc hm Fh y Trờn c s ca cỏc kt qu ny ta sỏng t v tớnh cht ca v ỏi cc tiu lc khi, gúp phn lm hon chnh thờm lớ thuyt thit k mụ hỡnh c s d liu dng 51 KẫT LUN Quỏ trỡnh nghiờn cu v mụ hỡnh c s d liu quan h v mụ hỡnh c s d liu dng ti ó gii quyt c yờu cu chớnh ca lun gúp phn hon thin thờm v lý thuyt thit k mụ hỡnh d liu dng C th l ó t c cỏc kt qu sau: Tỡm hiu v mụ hỡnh d liu dng nh ngha tớnh cht ca v trỏi cc tiu trờn lc Phỏt biu v chng minh mt s tớnh cht mi m rng ca v trỏi cc tiu lc Hng phỏt trin ca ti Nhng kt qu nghiờn cu ca lun mt s tớnh cht ca v trỏi cc tiu lc c xột ph thuc hm Fh, tỡm thờm nhng kt qu ta m rng thờm Fh thnh ph thuc hm thụng thng F Khi ú hi vng s thu c kt qu phong phỳ hn [...]... chứng minh tính chất vế trái cực tiểu ừên lược đồ khối 3 Nhiệm vụ nghiên cứu - Tìm hiểu mô hình dữ liệu dạng khối - Đề xuất tính chất của vế trái cực tiểu trong lược đồ khối - Chứng minh vế trái cực tiểu trong lược đồ khối 4 Đổi tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu: Tính chất của vế trái cực tiểu trong lược đồ khối - Phạm vi nghiên cứu: Nằm trong vế trái cực tiểu trong lược đồ khối 5 Phưong... DẠNG KHỐI 2.1 Khối, lát cắt của khối 2.2 Các phép tính trên khối 3 2.3 Đại số quan hệ trên khối 2.4 Phụ thuộc hàm trên lược đồ khối 2.5 Bao đóng của các tập thuộc tính chỉ số trên lược đồ khối 2.6 Khóa của khối C h ư ơ n g 3: V Ế T R Á I cực T IỂ U T R O N G M Ô H ÌN H D Ữ L IỆ U D Ạ N G K H Ố I 3.1 v ế trái cực tiểu trong mô hình dữ liệu dạng khối Định nghĩa 3.1 3.2 Một số tính chất mở rộng của vế trái. .. khối 5 Phưong pháp nghiên cứu Thu thập tài liệu, phân tích, suy luận tổng họp, đánh giá Từ đó đưa ra và một số tính chất của vế trái cực tiểu trong lược đồ khối 6 Dự kiến đóng góp mói Đề xuất và chứng minh một số tính chất mới của vế trái cực tiểu trong lược đồ khối 7 Cấu trúc luận văn Luận vãn gồm: Lời mở đầu, ba chương nội dung, phần kết luận và sau đó là tài liệu tham khảo Chương 1: CÁC MÔ HÌNH DỮ... ở chương 2 đã được nói trong các tài liệu [4,5,7] 2.1 Khối, lược đồ khối và lát cắt 2.1.1 Khối, lược đồ khối Khái niệm toán học làm nền tảng cho mô hình cơ sở dữ liệu dạng khối (gọi tắt là mô hình khối) là các khối hiểu theo nghĩa của lý thuyết tập hợp Khối được định nghĩa như sau: Định nghĩa 2.1 Gọi R = (id; Ai, A2, , An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai... hiệu đơn giản là r Khi đó khối r(R) được gọi là c lược đồ khối R Như vậy, ừên cùng một lược đồ khối R ta có thể xây dựng được nhiều khối khác nhau Ví du 2.1: Ta xây dựng khối điểm sinh viên (ký hiệu DiemSV(R)) (hình 2.1) để quản lý điểm của sinh viên ừong một trường đại học như sau: 25 Cho lược đồ khối R = (id; Als A2 A3, A 4), trong đó: id = {Học kỳ 1, Học kỳ 2},và các thuộc tính là Ai = Ma (mã), A2... hiện của cơ sở dữ liệu trong mô hình phân cấp tương ứng vói một lược đồ sẽ chứa tập các cây có các nút là mẫu tin, mỗi cây được gọi là một mẫu tin cơ sở dữ liệu (database record) Một mẫu tin cơ sở dữ liệu tương ứng vói một cây trong lược đồ cơ sở dữ liệu và mẫu tin gốc của một mẫu cơ sở dữ liệu tương ứng vói một thực thể của kiểu mẫu tin gốc 1.5 Mô hình dữ liệu datalog Mô hình toán học nền tảng của. .. mở rộng của vế trái cực tiểu trong lược đồ khối III KẾT LUẬN - Nêu tóm tắt các kết quả của luận văn - Đề xuất hướng nghiên cứu mở rộng sau này của luận văn 4 CHƯƠNG 1: CÁC MÔ HÌNH DỮ LIÊU Mô hình dữ liệu quan hệ là một trong những mô hình đuợc quan tâm nhiều nhất hiện nay Nhiều tác giả đã quan tâm nghiên cứu và đã thu được các kết quả tốt Mô hình dữ liệu quan hệ sẽ được trình bày trong phần dưới đây... với thực thể khác Một nhóm bao gồm tất cả các thực thể “tương tự” tạo ra một tập thực thể (entity set) Tính “tương tự” ít nhất cũng đòi hỏi rằng có thể tìm được một tập các đặc tính chung cho tất cả các phần tử của một tập thực thể 6 Các đặc tính của tập thực thể gọi là các thuộc tính Mục đích của mô hình này là cho phép mô tả lược đồ khái niệm của một tổ chức mà không cần chú ý đến tính hiệu quả hoặc... r, s, rx s e Phép chiếu Cho r là một quan hệ n ngôi xác định trên tập thuộc tính ư={Ai, A2, An}, X là tập con của u Phép chiếu của quan hệ r trên tập thuộc tính X, kíhiệu là nx(r), là tập các bộ của r xác định ừên tập thuộc tính X Ta có: n x(r) = { t x | t e r } Phép chiếu thực chất là phép toán giữ lại một số thuộc tính cần thiết của quan hệ và loại bỏ những thuộc tính không cần thiết f Phép chọn... (id; Al, A2, , An), r(R) là một khối ừên R Với mỗi x e id thì lát cắt r(Rx) là một quan hệ Trong trường hợp tập chỉ so id chỉ gồm một phần tử thì r(R) trở thành một quan hệ Như vậy mỗi quan hệ r(Ai, A2, , An) là một trường hợp đặc biệt của khối, đó chính là khối r(R) với R = ({x}; Ai, A2, , An ) Mệnh đề 2.2 Cho R = (id; Al, A2, , An), r(R) là một khối trên R, khi đó tồn tại một họ quan hệ duynhất biểu