Độ đo phụ thuộc hàm xấp xỉ trong cơ sở dữ liệu mô hình dạng khối

o vic ñm bo tính nht quán ca d 
liu, loi b bt d liu dư tha. Ph thuc hàm cũng th hin tính cht ng nghĩa gia các 
thuc tính và có th tn ti trong mt tp d liu ñc lp vi mô hình quan h. Nghiên cu 
v các ph thuc hàm là mt hưng quan trng trong thit k cơ s d liu quan h và ñã 
ñt ñưc nhiu thành tu [11, 12, 13, 20]; bên cnh ñó, nghiên cu v ph thuc hàm trong 
mô hình d liu dng khi [2] ñã có nhng kt qu [2, 5] ñ tăng cưng hơn na kh năng 
ñm bo ng nghĩa, góp phn hoàn chnh thêm v mô hình d liu dng khi. 
 n
 ()i
 Cho lưc ñ khi R = (id; A 1,A 2..., A n) , r(R) là mt khi trên R, X,Y ⊆ ∪id , 
 i=1
 X→ Y là kí hiu mt ph thuc hàm. Mt khi r tho X→ Y , nu vi mi t1, t 2 ∈ R sao 
cho t 1(X) = t 2(X) thì t 1 (Y) = t(Y). 
 T ñnh nghĩa ph thuc hàm  trên, ta nhn thy: nu tn ti t 1, t 2 ∈ r sao cho 
t1(X) = t 2(X) và t 1 (Y) = t(Y), thì có th kt lun rng r không tho ph thuc hàm X→ Y 
(hay ph thuc hàm X→ Y không ñúng trên r). 
 Trong thc hành, ñiu này t ra quá cht và cng nhc khi ta hình dung quan h r có 
hàng nghìn b, trong ñó ch có mt vài b vi phm ph thuc hàm X→ Y do có mt s d 
liu b sai lch hoc ngoi l. Do ñó vic m rng khái nim ph thuc hàm (kinh ñin) 
thành ph thuc hàm xp x (trong mô hình d liu quan h, mô hình d liu dng khi) 
theo mt cách thc, mt nghĩa nào ñó là nhu cu tt yu và t nhiên. 
 Các ph thuc hàm xp x khai phá ñưc t mô hình cơ s d liu quan h, mô hình 
 d liu dng khi là các mu quan trng, là nhng tri thc có giá tr v cu trúc ca các b 
 d liu. 
2. MÔ HÌNH D LIU DNG KHI 
2.1. Khi, lưc ñ khi 
 Khái nim toán hc làm nn tng cho mô hình cơ s d liu dng khi (gi tt là mô 
 hình khi) là các khi hiu theo nghĩa ca lí thuyt tp hp. Khi ñưc ñnh nghĩa như sau: 
 Đnh nghĩa 2.1: Gi R = (id; A 1, A 2, ... A n) là mt b hu hn các phn t, trong ñó id 
 là tp ch s hu hn khác rng, A i (i=1,n) là các thuc tính. Mi thuc tính A i (i=1,n) có 
min giá tr tương ng là dom(A i) . Mt khi r trên tp R, kí hiu r(R) gm mt s hu hn 
phn t mà mi phn t là mt h các ánh x t tp ch s id ñn các min tr ca các thuc 
 i
 tính A i, (i=1,n). Nói mt cách khác: t∈ r( R ) ⇔ t = {t : id  dom(A i)} i =1,n . 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 59 
 Ta kí hiu khi ñó là r(R) hoc r (id; A 1, A 2, ... A n), hoc kí hiu ñơn gin là r. 
 Khi ñó khi r(R) ñưc gi là có lưc ñ khi R. Như vy trên cùng mt lưc ñ khi R 
ta có th xây dng ñưc nhiu khi khác nhau. 
 Ví d 2.1: Ta xây dng khi nhân viên (kí hiu NV(R)) (hình 1) ñ qun lí nhân viên 
trong mt cơ quan như sau: 
 Cho lưc ñ khi R = (id; A 1, A 2, A3, A 4), trong ñó: id = {1/2009, 2/2009, 3/2009.., 
12/2009,và các thuc tính là A 1 = ma (mã), A 2 = ten (tên), A 3 = luong (lương), 
 A4 = trinh_do (trình ñ). 
 Vi khi NV(R)  hình 1, ta thy nó gm 3 phn t: t 1, t 2, t 3. 
 Hình 1.1.1. Biu din khi nhân viên NV(R). 
 Khi ñó ta có: 
 Lương ca nhân viên t 1  thi ñim tháng 1/2009 là: 
 t1(1/2009,luong) = 200. 
 ● Tên ca cán b t 2 vào tháng 2/2009 là: t 2(2/2009,ten) = 'B'. 
 ● Trình ñ ca cán b t 3 vào tháng 2/2009 là: 
 t3(2/2009,trinh_do) = ‘CD’. 
 ● Mã s ca cán b t 3 vào tháng 3/2009 là: t 3(3/2009,ma) = 'C01'. 
2.2. Lát ct 
 Cho R = (id; A 1, A 2, ... A n), r(R) là mt khi trên R. Vi mi x ∈ id ta kí hiu r(R x) là 
mt khi vi R x = ({x}; A 1, A 2, ... A n) sao cho: 
 i i
 tx ∈ r(R x) ⇔ t x = {t x = t } i =1,n vi t ∈ r(R), 
 i
 x và t = {t : id  dom(A i)} i =1,n 
 i i
  ñây t x(x) = t (x) vi i=1,n. 
60 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Khi ñó r(R x) ñưc gi là mt lát ct trên khi r(R) ti ñim x. 
 Ví d 2.2: Vi khi NV(R) ñã cho  trên, R = (id; A 1, A 2, A3, A 4) 
 Trong ñó: id = {1/2009, 2/2009, 3/2009..., 12/2009} 
 A1 = ma, A 2 = ten, A 3 = luong, A 4 = trinh_do. 
 Nu x = 2/2009 ∈ id thì lát ct r(R 2/ 2009) có dng như sau: 
 r(R 2/2009) : ma ten luong trinh_do 
 A01 A 350 ThS 
 A02 B 300 DH 
 A03 C 250 CD 
3. PH THUC HÀM XP X TRONG MÔ HÌNH D LIU DNG KHI 
3.1. Ph thuc hàm trong mô hình d liu dng khi 
 Sau ñây, ñ cho ñơn gin ta s dng các kí hiu: 
 (i) (i) (i)
 x = (x; A i) ; id = {x | x ∈ id}. 
 (i)
 Ta gi x (x ∈ id, i = 1..n) là các thuc tính ch s ca lưc ñ khi R = (id; A 1, A 2,... A n) . 
 Đnh nghĩa 3.1. Cho lưc ñ khi R = (id; A 1, A 2, ... A n) , r(R) là mt khi trên R, 
 n
 X,Y ⊆ ∪id ()i , X→ Y là kí hiu mt ph thuc hàm. Mt khi r tho X → Y nu vi mi 
 i=1
 t1, t 2 ∈ R sao cho t 1(X) = t 2(X) thì t 1(Y) = t 2(Y). 
3.2. Ph thuc hàm ñưc suy din t tp ph thuc hàm F 
 Cho lưc ñ khi R = (id; A 1, A 2, ... A n) , F là tp các ph thuc hàm trên R và X → Y 
 n
là mt ph thuc hàm vi X,Y ⊆ ∪id ()i . Nói rng X → Y ñưc suy din logic t F nu 
 i=1
 vi mi khi r xác ñnh trên R tho các ph thuc hàm trong F thì cũng tho X→ Y . Kí 
hiu là: 
 F│= X→ Y 
 3.3. Các tính cht ca ph thuc hàm trên khi 
 Cho lưc ñ khi R = (id, A 1, A 2, A n), r(R) là mt khi bt kì, F là tp các ph 
 n
 thuc hàm và X,Y, Z, W⊆ ∪ id (i ) , ta có mt s tính cht cơ bn ca các ph thuc hàm 
 i=1
 như sau: 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 61 
 F1) Nu Y 
 X thì X → Y (tính phn x) 
 F2) Nu X → Y thì XW → YW (tính gia tăng) 
 F3) Nu X → Y, Y → Z thì X → Z (tính bc cu) 
 F4) Nu X → Y, YZ → W thì XZ → W (tính ta bc cu) 
 F5) Nu X → Y, Z → W thì XZ →YW (cng tính ñy ñ) 
 F6) Nu X → Y thì XZ→Y (tính m rng v trái) 
 F7) Nu X → Y, X → Z thì X → YZ (cng tính v phi) 
 F8) Nu X → YZ thì X → Y (b phn v phi) 
 F9) Nu X → YZ, Z → WV thì X → YZW (tính tích lu) 
 Khái nim ph thuc hàm trong mô hình d liu khi, mt khi r tho X→ Y là ñúng 
 nu vi mi t 1, t 2 ∈ r sao cho t 1(X) = t 2(X) thì t 1(Y) = t 2(Y). Điu này trong thc hành t ra 
 quá cng ngt bi có th ph thuc hàm X→ Y trong khi d liu R= (id, A 1, A 2, A n) 
 vi phm do mt vài sai lch hoc ngoi l. Do ñó vic m rng ph thuc hàm trong mô 
 hình d liu khi thành ph thuc hàm xp x trong mô hình d liu khi là ñiu tt yu. 
Nói cách khác là ph thuc hàm trong mô hình d liu khi ch ñúng trên các tp con ca 
khi r(R), tc là khi r’(R) nhn ñưc bng cách loi b ñi mt s rt ít các phn t trong 
khi r(R). Có th xem ph thuc hàm xp x trong mô hình d liu khi là m rng ca 
ph thuc hàm xp x trong mô hình d liu quan h. 
 Cho R = (id; A 1, A 2, A n), r là mt khi trên R, , X→ Y là kí hiu 
mt ph thuc hàm. Gi s r tho ph thuc hàm X→ Y là ñúng. Khi ñó nu id = {x} thì: 
 r tr thành quan h r(id;A 1, A2,..A n). 
 Ph thuc hàm X→ Y tr thành ph thuc hàm trong mô hình d liu quan h. 
3.4. Ph thuc hàm xp x trong mô hình d liu quan h 
 Đnh nghĩa 3.2: Cho U là mt tp thuc tính, R(U) là mt lưc ñ quan h trên U . 
 Cho X,Y, ⊆ U . Khi ñó, Y ñưc gi là ph thuc hàm xp x vào X trên lưc ñ R(U) vi 
 mc ñ α ∈[0,1] và kí hiu X≈α Y , da trên s ti thiu nhng hàng cn loi b khi r ñ 
ph thuc X≈α Y thành X→ Y ñưc xác ñnh như sau: 
 = 
 Đnh nghĩa 3.3: Cho U là mt tp thuc tính, R(U) là mt lưc ñ quan h trên U. 
ChoX , Y⊆ U , Đ ño li ca ph thuc hàm xp x X≈α Y ñưc xác ñnh như sau: 
62 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 T ñó: X→ Y ñúng trên ng vi mt ngưng li α ∈[0,1] khi và ch khi 
 g3 ( X→ Y ) ≤ α 
 X→ Y là ph thuc hàm khi và ch khi g 3 = 0 
 Mt s tính cht: 
 − Tính cht 1 : Cho r là mt quan h trên tp thuc tính R. Mt ph thuc hàm ñúng 
 trên r cũng là ph thuc hàm xp x loi 2 vi mc  tuỳ ý (0 δ  <1) ñúng trên r. 
 Tính cht này d dàng suy theo ñnh nghĩa ca ph thuc hàm xp x loi 2. 
 − Tính cht 2 : Cho r là mt quan h trên R:X , Y⊆ R , δ1, δ 2 là 2 s sao cho 
 0≤δ 1 ≤ δ 21 ≤ . Kí hiêu X≈δ1 Y và X≈δ 2 Y là 2 ph thuc hàm xp x loi 2 mc δ1 và 
mc δ 2 gia X và Y trên r, khi ñó nu X≈δ1 Y ñúng trên r thì X≈δ 2 Y cũng ñúng trên r. 
 − Tính cht 3: Tính phn x 
 Nu Y≈ X khi ñó X≈δ Y là ph thuc hàm xp x loi 2 vi mc δ tuỳ ý ( 0≤δ < 1 ) 
 − Tính cht 4: Tính bc cu 
 Nu X≈δ Y và Y≈δ Z thì X≈δ Z 
 − Tính cht 5: Tính gia tăng 
 Vi mi XYZ, , ⊆ R và mc δ nào ñó, nu X≈δ Y thì XZ≈δ YZ 
3.5. Ph thuc hàm xp x trong mô hình d liu dng khi 
 Đnh nghĩa 3.5: Cho lưc ñ khi R = (id; A 1, A 2,... An) , r(R) là mt khi trên R, 
 n
 ()i
 X,Y ⊆ ∪id . Khi ñó, Y ñưc gi là ph thuc hàm xp x và X trên khi R là s hàng 
 i=1
nhiu nht cn phi loi b trong tt c các lát ct thuc khi R ñ ph thuc hàm X→ Y id 
(trên lát ct id) và X→ Y R trên khi R là ñúng. 
 R id
 Kí hiu g 3( X→ Y ) là ñ ño li ca ph thuc hàm X→ Y trên khi R, ( X→ Y ) là 
ph thuc hàm X→ Y trên lát ct id, id∈ R . 
 R
 g3( X→ Y ) ñưc xác ñnh như sau: 
 R id
 g3( X→ Y ) = max(g 3( X→ Y ) , id∈ R ) 
 Khi g 3 = 0 thì tt c các ph thuc hàm xp x trên lát ct chính là ph thuc hàm 
(kinh ñin). 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 63 
 Minh ho: 
 Vi khi R = (id; X; Y), trong ñó: id = {1, 2, 3}, 2 thuc tính X, Y 
 X Y 
 Có th biu din khi d liu trên  hình 1. dưi dng bng d liu như sau: 
 BBBngBng 1. Bng biu din khi d liu 
 Id X Y 
 1 A @ 
 1 B # 
 1 C $ 
 2 A % 
 2 B & 
 2 D $ 
 3 A ! 
 3 A * 
 3 C & 
 Xét ph thuc hàm xp x X→ Y trên khi R, ta tính ñưc 
 1 
 g3( X→ Y ) = 1 –(1+1+1)/3 = 0. 
 Ph thuc hàm X→ Y trên lát ct 1 là ñúng 
 2
 g3( X→ Y ) = 1 (1+1+1)/3= 0. 
 Ph thuc hàm X→ Y trên lát ct 2 là ñúng. 
 3
 g3( X→ Y ) = 1 (1+1)/3 = 0.34. 
 Ph thuc hàm X→ Y trên lát ct 3 có ñ li là 0.34 
64 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Do ñó: 
 R
 g3( X→ Y ) = max(0,0,0.34) = 0.34 
 Như vy, ñ li ca ph thuc hàm X→ Y trên khi R là 0.34 
4. KT LUN 
 Trong báo cáo này, chúng tôi trình bày mô hình d liu dng khi ñưc xem là m 
rng ca mô hình d liu quan h. Trình bày ph thuc hàm trong mô hình d liu dng 
khi và các tính cht ca ph thuc hàm trong mô hình d liu quan h. 
 Trong bài bào trình bày phương pháp xây dng ñ ño ph thuc xp x trong mô hình 
 d liu dng khi. Vi hai tp thuc tính X và Y thuc khi R, ñ ño ñưc xây dng da 
 trên vic tính toán các ñ ño xp x t các lát ct và ly giá tr ln nht ca các ñ ño ñó. 
 Giá tr ñ ño xp x ca ph thuc hàm trên khi R nm trong khong [01]. Mt ph thuc 
 hàm xp x trên khi có ñ ño bng 0 thì tt c các ph thuc hàm xp x trên lát ct chính 
 là ph thuc hàm. 
 Da trên các nghiên cu v ph thuc hàm xp x trong mô hình d liu dng khi 
chúng tôi s nghiên cu thut toán khai phá các ph thuc hàm xp x trên khi vi 
ngưng ph thuc cho trưc. 
 TÀI LIU THAM KHO 
1. Nguyn Xuân Huy (2006), Các ph thuc logic trong cơ s d liu , Nxb Thng kê, Hà Ni. 
 2. Trnh Đình Thng (2011), Mô hình d liu dng khi , Nxb Lao ñng. 
 3. Vũ Đc Thi (1997), Cơ s d liu Kin thc và thc hành , Nxb Thng kê, Hà Ni. 
 4. Nguyn Tu (2008), Giáo trình cơ s d liu , Nxb Đi hc Quc gia Hà Ni. 
 5. Trnh Đình Vinh (2011), Mt s ph thuc d liu trong cơ s d liu dng khi , Lun án 
 Tin sĩ, Vin Công ngh Thông tin. 
 6. Lê Tin Vương (1997), Nhp môn Cơ s d liu quan h , Nxb Khoa hc và kĩ thut, Hà Ni. 
 7. Aravind Krishna Kalavagattu (2008), Mining Approximate Functional Dependencies as 
 Condensed Representations of Association Rules, Arizona State University. 
 8. Dalkilic, M.M., Robertson, E.L (2000): "Information Dependencies", Proceedings of ACM 
 PODS ., pp.245–253. 
 9. Giannella, Chris and Robertson (2004), Edward, "On Approximation Measures for Functional 
 Dependencies", Information Systems Archive , 29(6), pp.483507. 
 10. Han J., and Kamber M. (2000), Data Mining Concepts and Techniques , Morgan Kanuf mann. 
 11. Hong Yao, Howard J. Hamilton, Cory J. Butz, FD_Mine: "Discovering Functional 
 Dependencies in a Database Using Equivalences", Second IEEE International Conference on 
 Data Mining , 2002. 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 65 
12. Hector GarciaMolina, Jeffrey D. Ullman, and Jennifer Widom (2000), Database Systems : The 
 Complete Book , Prentice Hall Publisher. 
 13. Huhtala, Y., Karkkainen, J., Porkka P., and Toivonen, H., TANE (1999): An Efficient 
 Algorithm for Discovering Functional and Approximate Dependencies, The Computer 
 Journal , 42(2), pp.100111. 
 14. Jalal Atoum (2009), "Mining Approximate Functional Dependencies from Databases Based on 
 Minimal Cover and Equivalent Classes", European journal of scientific research , 33 (2), pp. 
 338346. 
 15. Kivinen, J., and Mannila (1995), "H. Approximate Inference of Functional Dependencies 
 From Relations", Theoretical Computer Science , 149, pp.129149. 
 16. KwokWa Lam, Victor C.S.Lee (2004), "Building Decision Trees Using Functional 
 Dependencies", Processdings, of the International Conference on Information Technology: 
 Coding and Computing (ITCC’04 ). 
17. L.B. Cristofor (2000), "A Rough Sets Based Generalization of Functional Dependencies", 
 Umass/Boston, Dept. of Mathand Comp. Sci. Technical Report . 
18. Q. Wei, GQ. Chen (2004), "Efficient Discovery of Functional Dependencies with Degrees of 
 Satisfaction", International journal of intelligent systems , Vol. 19. 
 19. Ronald S. King, James J. Legendre (2003), "Discovery of Functional and Approximate 
 Functional Dependencies in Relational Databases", Journal of applied mathematics and 
 decision sciences , 7(1), pp.4959. 
 20. Stéphane Lopes, JeanMarc Petit, and Lotfi Lakhal (2000), "Efficient Discovery of Functional 
 Dependencies and Armstrong Relations", EDBT 2000, LNCS 1777 , pp.350364. 
 MEASURING THE APPROXIMATE FUNCTIONAL 
 DEPENDENCY ON DATABASE OF CUBE MODEL 
 AbstractAbstract: In this report, we present data model of building blocks, which is considered as 
 an extension of the relational data model. Functional Dependency (FD) is a data binding 
 of the attributes in a relational database to ensure the consistency of the data and to 
 eliminate redundant data. Dependencies in the data model and the nature of blocks are 
 great interests that should be researched. 
 The article presents the method of approximation measurement in model building blocks. 
 With two sets of attributes X and Y of R, the measurement is based on the calculation of 
 the approximate measurement of the sections (approximate measurement values range 
 from 0 to 1), and takes the largest values. The approximate measurement value of the FD 
 in R is in the range of [01]. If the measurement of an approximate FD equals 0 then all 
 approximate FDs on sections are Functional Dependencies (classic). 
 KeywordsKeywords: Functional Dependency, data exploitation, approximate Functional Dependency, 
 data model, relation, cube data model