Phụ thuộc hàm xấp xỉ và phân tử ngoại lai đối với phụ thuộc hàm

Chia sẻ: Nguyễn Minh Vũ | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

55
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

The aim of this paper is to present the concepts about Type 2 Approximate Functional Dependency - AFD 2 (relating to the correlation between atributes of the relational file) and the outliers with functional dependency. The paper also gives some properties of ADF 2 and algorithms for finding the outliers with functional dependency.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phụ thuộc hàm xấp xỉ và phân tử ngoại lai đối với phụ thuộc hàm

’ Tap ch´ Tin hoc v` Diˆu khiˆ n hoc, T.23, S.1 (2007), 80—85 ı e e . . a ` . ’. ´ ’ ` ˆ ` ˆ ˆ PHU THUOC HAM XAP XI VA PH` N TU NGOAI LAI A . . . . ´ ˆ ` ˆ ´ DOI VO I PHU THUOC HAM . . ’ ˜ ´. VU DU C THI1 , PHAM HA THUY2 . . 1 Viˆn e . Cˆng nghˆ thˆng tin, Viˆn Khoa hoc v` Cˆng nghˆ Viˆt Nam o e o e e e . . . a o . . ’m to´n Nh` nu.´.c o tˆm Khoa hoc v` BDCB - Kiˆ a e a a . a 2 Trung Abstract. The aim of this paper is to present the concepts about Type 2 Approximate Functional Dependency - AFD 2 (relating to the correlation between atributes of the relational ﬁle) and the outliers with functional dependency. The paper also gives some properties of ADF 2 and algorithms for ﬁnding the outliers with functional dependency. ´ ´ ´ T´m t˘t. B`i b´o gi´.i thiˆu vˆ phu thuˆc h`m xˆ p xı loai 2 (loai phu thuˆc h`m xˆ p xı liˆn quan o a a a o e ` e o a a ’ . o a a ’ e . . . . . . ` ´n su. tu.o.ng quan gi˜.a c´c thuˆc t´ cua mˆt quan hˆ) v` phˆn tu. ngoai lai dˆi v´.i phu thuˆc ´ o ’ ’ u a o ınh o e a a o dˆ e o . . . . . . . ´ ´ ´ h`m. B`i b´o c˜ng tr` b`y mˆt sˆ t´ chˆ t cua phu thuˆc h`m xˆ p xı loai 2 v` thuˆt to´n x´c a a a u ınh a o o ınh a ’ o a a ’ . a a a a . . . . ` ´ o a dinh phˆn tu. ngoai lai dˆi v´.i phu thuˆc h`m. a ’ o o . . . . ´. ˆ GIO I THIEU . ´ a Kh´i niˆm phu thuˆc h`m xˆ p xı (Approximate functional dependency) v` phu.o.ng ph´p a e o a a ’ a . . . ´ ´p xı d˜ du.o.c nhiˆu t´c gia dˆ cˆp dˆn v` du.o.c u.ng dung ` a ’ a ’ ` a e a e . ph´t hiˆn c´c phu thuˆc h`m xˆ a e a o a a e . . . . . ´ . ’ ˜ ` ’ u o a e e trong nhiˆu b`i to´n phˆn l´.p cua data mining ([1, 2]). Nh˜.ng phu thuˆc nhu. vˆy biˆ u diˆn e a a a o . . . . phu thuˆc tu. nhiˆn gi˜.a c´c thuˆc t´ trong mˆt quan hˆ nhu.ng c´ ch´.a mˆt v`i h`ng o . e u a o ınh o e o u o a a su . . . . . . . ´ ’ o c´ sai s´t ho˘c khˆng thoa luˆt (goi l` phu thuˆc h`m xˆ p xı loai 1). Mˆt tru.`.ng ho.p phu o o a o a a o a a ’ . o . . . . . . . . ´ o o o ınh a u u u o o . thuˆc xˆ p xı kh´c l` c´ nh˜.ng nh´m thuˆc t´ m˘c d` gi˜.a ch´ng khˆng c´ su. phu thuˆc o a ’ a a o u . . . . . ’ a o a a ıa o a o h`m theo kiˆu b˘ ng nhau tuyˆt dˆi (theo c´ch dinh ngh˜ phu thuˆc h`m thˆng thu.`.ng) m` a e ` e o . . . . ´ . phu thuˆc xˆ p xı theo kiˆu tu.o.ng quan h`m sˆ (tuyˆn t´ ho˘c phi tuyˆn), (goi l` phu ’ ´ ´ ´ c´ su o . o a ’ e a o e ınh a e . . ´ . . a . ´ ´ ` o a ’ a ` e a e thuˆc h`m xˆ p xı loai 2). Tru.`.ng ho.p n`y xay ra kh´ nhiˆu v` liˆn quan dˆn nhiˆu b`i to´n o a a ’ . e e a a . . ´ ’ e a a o ’ o thu.c tˆ. V´ du trong bang quan hˆ ghi lai t` h` mua v`o c´c loai h`ng h´a cua mˆt doanh . e ı . . . ınh ınh . a . ’ ´ ´ o a a a ı e a o a nghiˆp ta thˆ y quan hˆ gi˜.a khˆi lu.o.ng h`ng mua v`o v` chi ph´ dˆ mua l` phu thuˆc h`m e a e u . . . . . . chˆnh lˆch gi˜.a khˆi lu.o.ng h`ng mua v`o nho ho.n mˆt m´.c n`o d´ ´ ´ ´ ’ o o u a o e u a a xˆ p xı loai 2. Nˆu su e a ’ . e . . . . ’ ’ ’ e ı u a . ’ th` c˜ng k´o theo su. chˆnh lˆch cua chi ph´ hai do.t mua c˜ng nho (gi´ tri cua hai ban ghi tai ı u e . e . . . .o.c ph´p c´ su. chˆnh lˆch tu.o.ng u.ng). C˜ ng vˆy dˆi v´.i chı tiˆu doanh ´ ’ e c´c thuˆc t´ n`y du . a o ınh a e o . e e ´ u a o o . . . ’ ’ a thu v` chi ph´ trong bang kˆ vˆ tinh h` kinh doanh... Viˆc khao s´t loai phu thuˆc h`m a ı e ` e ınh e o a . . . . ˜ ´ ´ e e a e u e a o xˆ p xı n`y c´ u.ng dung thu.c tiˆn trong viˆc ph´t hiˆn nh˜.ng hiˆn tu.o.ng bˆ t thu.`.ng (ngoai a ’ a o´ . . . . . . . ’ ´ ´ ’ y ’ e a a e e lai) trong san xuˆ t kinh doanh, phuc vu cho hoat dˆng kiˆm to´n v` quan l´ kinh tˆ. Viˆc a . . . . . o ´ ´ e e e a u o a e a o o u quyˆt dinh m´.c chˆnh lˆch cho ph´p (vu.o.t qu´ m´.c d´ l` hiˆn tu.o.ng bˆ t thu.`.ng) thu.`.ng e . . . . . .o.c x´c dinh theo hu.´.ng hˆ tro. quyˆt dinh ([3]) c´ ngh˜ l` c`n t`y thuˆc thˆm c´c yˆu tˆ ˜ . ´ ´ ´ o o e . du . a . o ıa a o u o e a e o . ` e ` ´ ’ a vˆ yˆu cˆu v` kinh nghiˆm cua c´c chuyˆn gia trong c´c l˜ vu.c thu.c tˆ. e a a e e a ınh . e . . ´ ’ ` ’. ˆ ` ˆ ˆ PHU THUOC HAM XAP XI VA PH` N TU NGOAI LAI A . . . 81 ´ ´ ’ o a a a e Du.´.i dˆy l` kh´i niˆm cua phu thuˆc h`m xˆ p xı loai 2 v` khao s´t mˆt sˆ t´ chˆ t cua o a a ’ . a ’ a o o ınh a ’ . . . . ´ .i, mˆt sˆ kh´i niˆm, dinh ngh˜ vˆ phˆn tu. ngoai lai theo phu thuˆc h`m v` ` o o a e o a a o o ıa ` ` e a ’ n´. Dˆ ng th` o . ´ . . . . . ` l`m co. so. cho viˆc xˆy du.ng thuˆt to´n x´c dinh phˆn tu. ngoai lai dˆi v´.i phu ` ´ o ’ e a a a a . e a ’ o c´c mˆnh dˆ a a e . . . . . . ınh a thuˆc h`m c˜ ng du.o.c tr` b`y. o a u . . ´ ’ ´ ˆ ˆ ` ˆ 1. KHAI NIEM PHU THUOC HAM XAP XI LOAI 2 . . . . Cho r l` mˆt quan hˆ trˆn tˆp thuˆc t´ R = {a1 , a2 , ..., an } trong d´ c´c thuˆc t´ a o e e a o ınh o a o ınh . . . . . ’ l` c´c thuˆc t´ dinh danh(categorical), r`.i rac ho˘c liˆn tuc (tru.`.ng sˆ). ´ a e . o o a1 , a2 , ..., an c´ thˆ a a o e o ınh . o . . . .i nh˜.ng thuˆc t´ dinh danh, ta tiˆn h`nh thu.c hiˆn ´nh xa tˆ t ca c´c gi´ tri c´ thˆ ’ ´ ´ ´ Dˆi v´ o o e a u o ınh . e a a . o e . . . . a ’ a .i mˆt tˆp c´c sˆ nguyˆn du.o.ng liˆn kˆ. ´ ` ` e e e t´ o a a o o . . .a 2 bˆ gi´ tri trˆn tˆp thuˆc t´ ’ o a . e a o ınh). Dinh ngh˜ 1.1. (khoang c´ch gi˜ ıa a u . . . . .i 2 bˆ t1 , t2 ∈ r , ta k´ hiˆu ρ(t1 (X), t2 (X)) l` khoang c´ch gi˜.a t1 v` t2 trˆn tˆp thuˆc ’ o ı e a a u a e a o V´ o . . . . a . t´ X ⊆ R, du.o.c x´c dinh nhu. sau: ınh . (|t1 (ai ) − t2 (ai )| , ai ∈ X, ρ(t1 (X), t2 (X)) = max max(|t1 (ai )|, |t2 (ai )|) ´ ´ ´ a o h`m max(x, y) l` h`m chon ra sˆ l´.n nhˆ t trong 2 sˆ x, y . a a a o o . .`.ng ho.p max(|t1 (ai )|, |t2 (ai )|) = 0, ta qui u.´.c: o Tru o . |t1 (ai ) − t2 (ai )|/ max(|t1 (ai )|, |t2 (ai )|) = 0. ’ ´ ´ ´ ’ o a . e a o ınh o e a a o ’ a o o a Khoang c´ch gi˜.a 2 bˆ gi´ tri trˆn tˆp thuˆc t´ c´ thˆ coi l` h`m sˆ cua c´c dˆi sˆ v` a u . . . ’ a quan hˆ v` tˆp c´c thuˆc t´ l` c´c bˆ gi´ tri cu a a o a . e a a a o ınh. . . . . ´ ’ Mˆt sˆ t´nh chˆ t cua h`m khoa ng c´ch ρ(t1 (X), t2 (X)) o o ı a ’ a a . ´ .ng minh dinh ngh˜ khoang c´ch ρ(t1 (X), t2 (X)) thoa m˜n c´c t´ chˆt cua ˜ a ´ ’ ’ Dˆ d`ng ch´ e u ıa a a a ınh a ’ . ’ o h`m khoang c´ch ∀t1 , t2 , t3 ∈ r, ∀X, Y ⊆ R, ta c´: a a ρ(t1 (X), t2 (X)) 0 a1) a2) ρ(t1 (X), t2 (X)) = 0 ↔ t1 (X) = t2 (X) a3) ρ(t1 (X), t2 (X)) ρ(t1 (X), t3 (X)) + ρ(t3 (X), t2 (X)) ˜ u ´ a ınh a V` ngo`i ra c˜ng dˆ ch´.ng minh c´c t´ chˆ t sau: a a u e ´u X ⊆ Y th` ρ(t1 (X), t2 (X)) ρ(t1 (Y ), t2 (Y )) ı a4) Nˆ e a5) ρ(t1 (XY ), t2 (XY )) = max(ρ(t1 (X), t2 (X)), ρ(t1 (Y ), t2 (Y ))) ´ Dinh ngh˜ 1.2. (phu thuˆc h`m xˆ p xı loai 2 - Type 2 Approcimate Functional Depenıa o a a ’ . . . . ’ ’ a o o o o ` a a . a o dency). Gia su. X, Y ⊆ R v` v´.i mˆt sˆ δ cho tru.´.c, 0 δ < 1, ta n´i r˘ ng X x´c dinh h`m . ´ .c δ (ho˘c gi˜.a X, Y c´ phu thuˆc h`m xˆ p xı loai 2 m´.c δ ), k´ hiˆu l` X ≈ Y nˆu ´ ´ Y m´ u a u o o a a ’ . u y e a >δ e . . . . .i moi c˘p bˆ t , t ∈ r , m` ρ(t (X), t (X)) δ th` ta c˜ng c´ ρ(t (Y ), t (Y )) δ. a ı u o v´ o 1 2 1 2 . a o 1 2 . . V´ du 1. X´t bang quan hˆ sau: ı . e ’ e . A 2.5 2.51 3.6 3.65 4.25 4.26 B 18 18 20 20 25 25 C 160 160.5 320 323 641 643 D 25 15 30 45 60 70 E 12 13 16 28 19 57 ’ ˜ ´. VU DU C THI, PHAM HA THUY . . 82 ’ ´ ´ ` o o o o o Ta thˆ y gi˜.a c´c cˆt A, B c´ mˆi tu.o.ng quan v´.i cˆt C. V´.i δ = 0.05 ta kiˆm tra diˆu a u a o e e . . ´ kiˆn phu thuˆc h`m xˆ p xı loai 2: AB →0.05 C. e o a a ’ . . . . o V´.i c˘p h`ng 1, 2, ta c´ o a a . ρ(t1 (AB),t2 (AB)) = max(|t1 (A) − t2 (A)|/ max(|t1 (A)|, |t2 (A)|), |t1 (B) − t2 (B)|/ max(|t1 (B)|, |t2 (B)|) = 0.00394 < 0.05. Ta c˜ ng t´ du.o.c: ρ(t1 (C), t2 (C)) = 0.00311 < 0.05. u ınh . .o.ng tu. ta c˜ng s˜ kiˆm tra dˆ d`ng v´.i c˘p h`ng 3, 4 v` c˘p h`ng 5, 6 c˜ ng nhu. c´c ’ ˜ a Tu u e e e o a a a a a u a . . . c˘p h`ng kh´c. a a a . > a . a u Vˆy ta c´: AB ≈ 0.05 C (AB x´c dinh h`m C m´.c 0.05). a o . ´ ´ ’ ´ ’ ˆ ˆ INH CHAT CUA PHU THUOC HAM XAP XI LOAI 2 ˆ ˆ ` ˆ 2. MOT SO T´ . . . . ´ T´ chˆt 1. Cho r l` mˆt quan hˆ trˆn tˆp thuˆc t´nh R. Mˆt phu thuˆc h`m d´ng trˆn r ınh a a o e e a o ı o o a u e . . . . . . . ´ u u y u e c˜ng l` phu thuˆc h`m xˆ p xı loai 2 v´.i m´.c δ t`y ´ (0 δ < 1) d´ng trˆn r. u a . o a a ’ . o . ´t n`y dˆ d`ng suy theo Dinh ngh˜a 1.2. T´ chˆ a ˜ a ınh a e ı . ´ ´ a o e e a o T´ chˆt 2. Cho r l` mˆt quan hˆ trˆn R; X, Y ⊆ R; δ1 , δ2 l` hai sˆ sao cho 0 δ1 < δ2 < 1. ınh a . . ´ K´ hiˆu X ≈ δ1 Y v` X ≈ δ2 Y l` hai phu thuˆc h`m xˆ p xı loai 2 m´.c δ1 v` m´.c δ2 gi˜.a ı e > a > a o a a ’ . u a u u . . . ´ X v` Y trˆn r , khi d´ nˆu X ≈ δ1 Y d´ng trˆn r th` X ≈ δ2 Y c˜ng d´ng trˆn r. a e o e > u e ı > u u e ´ o a Hay viˆt mˆt c´ch h` th´.c: X ≈ δ1 Y ⇒ X ≈ δ2 Y. e ınh u > > . Thˆt vˆy, d˘t e = δ2 − δ1 . a a a . . . ´ ’ ’ Gia su. X ≈ δ1 Y d´ng trˆn r , t´.c l` v´.i moi c˘p t1 , t2 ∈ r nˆu ρ(t1 (X), t2 (X)) δ1 th` > u e u a o e ı . a . ta c˜ng c´ ρ(t1 (Y ), t2 (Y )) δ1 . u o ´ Do vˆy v´.i moi c˘p bˆ t1 , t2 ∈ r , nˆu ρ(t1 (X), t2 (X)) δ1 + e th` ρ(t1 (Y ), t2 (Y )) δ1 + e. a o e ı . a o . . . .c l` nˆu ρ(t1 (Y ), t2 (Y )) δ2 th` ρ(t1 (Y ), t2 (Y )) δ2 . ´ T´ a e u ı Suy ra X ≈ δ2 Y d´ng trˆn r. > u e ´ ´ ´ ’ T´ ınh chˆt 3. (t´ phan xa) Nˆu Y ⊆ X khi d´ X ≈ δ Y l` phu thuˆc h`m xˆp xı loai 2 a ınh e o > a . o a a ’ . . . u u y v´.i m´.c δ t`y ´ (0 δ < 1). o ´ ´ Thˆt vˆy, nˆu Y ⊆ X th` X → Y l` phu thuˆc h`m d´ng trˆn r th` theo T´ chˆ t 1 n´ a a e ı a o a u e ı ınh a o . . . . ´p xı loai 2 v´.i m´.c δ t` y y (0 δ < 1). ’ . u ´ c˜ng l` phu thuˆc h`m xˆ u a o a a o u . . ´ a ´ ´ T´ chˆt 4. (t´ b˘ c cˆu) Nˆu X ≈ δ Y v` Y ≈ δ Z th` X ≈ δ Z. ınh a ınh a ` e > a > ı > Thˆt vˆy: a a . . ´ ´ > ı o e o Nˆu X ≈ δ Y th` v´.i moi bˆ t1 , t2 ∈ r. Nˆu ρ(t1 (X), t2 (X)) δ , ta c´ ρ(t1 (Y ), t2 (Y )) δ. e . o . . ρ(t (Y ), t (Y )) > e u δ suy ra ρ(t1 (Z), t2 (Z)) δ, c´ ngh˜ l` o ıa a C˜ng do Y ≈ δ Z nˆn t` u 1 2 ` ’ X ≈ δ Z. Diˆu phai ch´.ng minh. > e u ´ ´ T´ ınh chˆt 5. (t´ gia t˘ng) V´.i moi X, Y, Z ⊆ R v` m´.c δ n`o d´, nˆu X ≈ δ Y th` a ınh a o a u a o e > ı . XZ ≈ δ Y Z . > Thˆt vˆy, v´.i moi c˘p bˆ t1 , t2 ∈ r m` ta c´ ρ(t1 (XZ), t2 (XZ)) δ th` do a a o a o ı . . . a o . . ρ(t1 (X), t2 (X)) ρ(t1 (XZ), t2 (XZ)) nˆn ta c´ e o ρ(t1 (X), t2 (X)) δ. ´ ’ ` ’. ˆ ` ˆ ˆ PHU THUOC HAM XAP XI VA PH` N TU NGOAI LAI A . . . M˘t kh´c, do X ≈ δ Y nˆn ta c´ ρ(t1 (Y ), t2 (Y )) δ , v` a a > e o a . ρ(t1 (Z), t2 (Z)) ρ(t1 (XZ), t2 (XZ)) δ, t`. d´ u o ρ(t1 (Y Z), t2 (Y Z)) = max(ρ(t1 (Z), t2 (Z)), ρ(t1 (Y ), t2 (Y ))) ` ’ Suy ra diˆu phai ch´.ng minh. e u 83 δ. ’. ´ ˆ ` ˆ ˆ ´. 3. PH` N TU NGOAI LAI DOI VO I PHU THUOC HAM A . . . o a . ’ Trong mˆt quan hˆ, phu thuˆc h`m mˆ ta su. phu thuˆc d˜. liˆu m` trong d´ gi´ tri cua o e o a o ’ . o u e a . . . . . . . mˆt tˆp thuˆc t´ n`y x´c dinh gi´ tri cua tˆp thuˆc t´nh kia. V´ du thu nhˆp cua cˆng ch´.c o a o ınh a a . a . ’ a o ı ı . a ’ o u . . . . . . ` ´ ’ ’ a o a u a a e ` e trong mˆt do.n vi do.n thuˆn chı phu thuˆc v`o m´.c lu.o.ng v` phu cˆ p. Trong bang kˆ vˆ thu o . . . . . ´ ´ ’ a e o nhˆp, ta c´ phu thuˆc h`m phan ´nh nh´m thuˆc t´ hˆ sˆ lu.o.ng, hˆ sˆ phu cˆ p x´c dinh a o o a o o ınh e o . ´ . a a . . . . . . ´ ´ ’ ’ u o ı a e o u o a . e o e o thu nhˆp cua t`.ng ngu.`.i. V` vˆy nˆu c´ nh˜.ng ban ghi c´ gi´ tri hˆ sˆ lu.o.ng, hˆ sˆ phu a . . . ´ . . . nhau nhu.ng gi´ tri thu nhˆp kh´c nhau th` l` mˆt hiˆn tu.o.ng bˆ t thu.`.ng, l`m cho ´ ´ a . a a ı a o e a o a cˆ p nhu a . . . . ´ u a a e o o phu thuˆc h`m n`y khˆng d´ ng. Dˆy l` hiˆn tu.o.ng ngoai lai dˆi v´.i phu thuˆc h`m. Nh˜.ng o a a o o a u . . . . . . . ´ ’ a e a a a e u o a u e hiˆn tu.o.ng n`y thu.`.ng xay ra trong thu.c tˆ khi cˆp nhˆt ho˘c sao ch´p nh˜.ng tˆp d˜. liˆu. e . . . . . . . . ’ o e ` a e Nguyˆn nhˆn c´ thˆ do sai s´t ho˘c gian lˆn. Viˆc ph´t hiˆn nh˜.ng hiˆn tu.o.ng n´i trˆn cˆn e a o e o a a e a e u . . . . . . ’ ´ o o a u o ınh a a thiˆt trong viˆc kiˆm tra v` l`m sach d˜. liˆu. Nˆi dung du.´.i dˆy ch´ng tˆi tr` b`y kh´i e e e a a u e . . . . .o.ng ph´p ph´t hiˆn tru.`.ng ho.p ngoai lai n`y. a a e o a niˆm v` phu e a . . . . ` ´ ’ ’ o a Dinh ngh˜ 3.1. (Phˆn tu. ngoai lai dˆi v´.i phu thuˆc h`m) Gia su. X → Y l` mˆt phu ıa a ’ o o a o . . . . . . .o.c gia thiˆt d´ng trˆn quan hˆ r . Khi d´ c˘p phˆn tu. (t1 , t2 ) v´.i t1 , t2 ∈ r l` ` ´ ’ e e o a a ’ o a thuˆc h`m du . o a e u . . . ` ´ ´ c˘p phˆn tu. ngoai lai dˆi v´.i phu thuˆc h`m X → Y nˆu t1 (X) = t2 (X) v` t1 (Y ) = t2 (Y ). a a ’ o a o o e a . . . . ` e ` o a a e e . a ınh a Trong nˆi dung du.´.i dˆy ch´ng tˆi su. dung kh´i niˆm vˆ hˆ b˘ ng nhau du.o.c tr` b`y o u o ’ . . . . trong [4]. ´ ’ ’ ’ e a o e ı e a ’ u e a e Gia su. r = {t1 , t2 , ..., tm } l` bang d˜. liˆu du.o.c gia thiˆt l` mˆt quan hˆ. K´ hiˆu Er l` hˆ . . . . . . ` ng nhau cua r du.o.c x´c dinh nhu. sau: ’ b˘ a . a . Er = {Ei,j : 1 i j m v` Ei,j = {a ∈ R; ti (a) = tj (a)}}. a ´ . ´ o a Dinh l´ 3.1. (Nhˆn biˆt c˘p ngoai lai dˆi v´.i phu thuˆc h`m) Cho r l` mˆt ba ng d˜. liˆu y a e a o o a o ’ u e . . . . . . . .o.c gia thiˆt l` mˆt quan hˆ trˆn tˆp thuˆc t´nh R, Er l` hˆ b˘ ng nhau cua r, X → Y l` ` ´ ’ ’ e a o e e a o ı du . a e a a . . . . . .o.c gia thiˆt d´ng trˆn r . C˘p phˆn tu. (t , t ) v´.i t , t ∈ r l` ngoai lai ´ ` ’ e u e a a ’ i j o i j a mˆt phu thuˆc h`m du . o o a . . . . . ´ o a dˆi v´.i phu thuˆc h`m X → Y khi v` chı khi Ei,j ∈ Er m` X ⊆ Ei,j nhu.ng Y ⊂ Ei,j . o o a ’ a . . .ng minh. Thˆt vˆy, gia su. (ti , tj ) l` c˘p ngoai lai dˆi v´.i phu thuˆc h`m X → Y , c´ ´ ’ ’ a a o a Ch´ u a a o o o . . . . . . .ng ti (Y ) = tj (Y ). T`. dinh ngh˜ Ei,j ta c´ X ⊆ Ei,j v` u . ıa o a ngh˜ l` ta c´ ti (X) = tj (X) nhu ıa a o Y ⊂ Ei,j . ´ e o Ngu.o.c lai, nˆu c´ Ei,j ∈ Er (Ei,j x´c dinh theo ti , tj ) m` X ⊆ Ei,j v` Y ⊂ Ei,j th` c˜ng a . a a ı u . . .i a ∈ Ei,j . Do X ⊆ Ei,j nˆn ti (X) = tj (X). o o e theo c´ch x´c dinh Ei,j ta c´ ti (a) = tj (a) v´ a a . ` C˜ng do Y ⊂ Ei,j nˆn tˆ n tai b ∈ Y m` ti (b) = tj (b) hay l` ti (Y ) = tj (Y ). Theo Dinh ngh˜ u e o . a a ıa . .ng minh. ` ’ a a e u 2.1 th` (ti , tj ) l` c˘p ngoai lai. Diˆu phai ch´ ı . . ´ o a T`. dinh l´ trˆn ta c´ thuˆt to´n x´c dinh c´c c˘p ngoai lai dˆi v´.i phu thuˆc h`m nhu. u . y e o a a a . a a o o . . . . . sau. ´ o a a a o o a a Thuˆt to´n 1. (X´c dinh c´c c˘p ngoai lai dˆi v´.i tˆp c´c phu thuˆc h`m) a a a . . . . . . . ’ u e e Input: Tˆp thuˆc t´ R = {a1 , a2 , ..., an ), bang d˜. liˆu r = {t1 , t2 , ..., tm } trˆn R a o ınh . . . ’ ˜ ´. VU DU C THI, PHAM HA THUY . . 84 Tˆp c´c phu thuˆc h`m F = {X1 → Y1 ; X2 → Y2 , ..., Xm → Ys } a a o a . . . ´ o a Output: OUTLI - tˆp c´c c˘p ngoai lai dˆi v´.i phu thuˆc h`m a a a o o . . . . . ´ a B˘t dˆu a ` ’ o ı e ` Bu.´.c 1: T´nh hˆ b˘ ng nhau cua r: . a Er = {Ei,j |1 i