Функциональ хамаарлын танилцуулга

Энэ нийтлэлд бид өгөгдлийн сангийн функциональ хамаарлыг авч үзэх болно - тэдгээр нь юу болох, хаана ашиглагддаг, тэдгээрийг олох алгоритмууд байдаг.

Бид харилцааны мэдээллийн сангийн хүрээнд функциональ хамаарлыг авч үзэх болно. Товчоор хэлбэл, ийм мэдээллийн санд мэдээлэл хүснэгтэд хадгалагддаг. Эндээс бид хатуу харилцааны онолд сольж болохгүй ойролцоо ойлголтуудыг ашиглах болно: бид хүснэгтийг өөрөө хамаарал, баганын шинж чанаруудыг (тэдгээрийн олонлог нь харилцааны схем), атрибутуудын дэд багц дээрх мөрийн утгуудын багцыг tuple гэж нэрлэх болно.

Жишээлбэл, дээрх хүснэгтэд (Бенсон, М, М эрхтэн) нь шинж чанаруудын багц юм (Өвчтөн, Пол, эмч).
Илүү албан ёсоор үүнийг дараах байдлаар бичнэ. [Өвчтөн, хүйс, эмч] = (Бенсон, М, М эрхтэн).
Одоо бид функциональ хамаарал (FD) гэсэн ойлголтыг танилцуулж болно:

Тодорхойлолт 1. R хамаарал нь FD X → Y-г (үүнд X, Y ⊆ R) хангана. , ∈ R хангагдсан: хэрэв [X] = [X], тэгвэл [Y ] = [Y ]. Ийм тохиолдолд бид X (тодорхойлогч, эсвэл тодорхойлох олонлог) нь Y (хамааралтай олонлог) функциональ байдлаар тодорхойлдог гэж бид хэлдэг.

Өөрөөр хэлбэл, Холбооны хууль байгаа эсэх X → Y гэсэн үг хэрэв бидэнд хоёр tuple байгаа бол R мөн тэдгээр нь шинж чанараараа таарч байна X, дараа нь тэдгээр нь шинж чанараараа таарах болно Y.
Одоо бүх зүйлийг дарааллаар нь авч үзье. Шинж чанаруудыг авч үзье. Өвчтөн и Хүйс Үүний тулд бид тэдгээрийн хооронд хамаарал байгаа эсэхийг мэдэхийг хүсч байна. Ийм олон тооны шинж чанаруудын хувьд дараахь хамаарал байж болно.

1. Өвчтөн → Хүйс
2. Хүйс → Өвчтөн

Дээрх тодорхойлолтын дагуу эхний хамаарлыг хадгалахын тулд баганын өвөрмөц утга бүрийг Өвчтөн зөвхөн нэг баганын утга таарч байх ёстой Хүйс. Мөн жишээ хүснэгтийн хувьд энэ нь үнэхээр тийм юм. Гэсэн хэдий ч, энэ нь эсрэгээрээ ажиллахгүй, хоёр дахь хамаарал хангагдаагүй, шинж чанар Хүйс тодорхойлох хүчин зүйл биш юм Өвчтөн. Үүнтэй адилаар, хэрэв бид хараат байдлыг авч үзвэл Эмч → Өвчтөн, энэ нь зөрчигдөж байгааг харж болно, учир нь үнэ цэнэ Робин Энэ шинж чанар нь хэд хэдэн өөр утгатай - Эллис, Грэм.

Тиймээс функциональ хамаарал нь хүснэгтийн шинж чанаруудын багц хоорондын одоо байгаа харилцааг тодорхойлох боломжийг бидэнд олгодог. Эндээс бид хамгийн сонирхолтой харилцааг, эсвэл илүү нарийвчлалтай авч үзэх болно X → Yтэдгээр нь:

• өчүүхэн бус, өөрөөр хэлбэл хараат байдлын баруун тал нь зүүн талын дэд хэсэг биш юм (Y ̸⊆ X);
• хамгийн бага, өөрөөр хэлбэл ийм хамаарал байхгүй Z → Y, тэр Z ⊂ X.

Өнөөг хүртэл хэлэлцсэн хамаарал нь хатуу байсан бөгөөд энэ нь хүснэгтэд ямар нэгэн зөрчил гаргахыг зөвшөөрдөггүй гэсэн үг юм. Гэсэн хэдий ч, tuple утгуудын хооронд зарим нэг зөрчилтэй байхыг зөвшөөрдөг зүйлүүд бас байдаг. Эдгээр хамаарлыг ойролцоо гэж нэрлэдэг тусдаа ангид ангилдаг бөгөөд тодорхой тооны хэлхээгээр зөрчихийг зөвшөөрдөг. Энэ тоо нь хамгийн их алдааны экспонент emax-аар зохицуулагддаг. Жишээлбэл, алдааны түвшин = 0.01 нь хамаарлыг авч үзэж буй шинж чанарын багцын 1% -иар зөрчиж болно гэсэн үг юм. Өөрөөр хэлбэл, 1000 бичлэгийн хувьд хамгийн ихдээ 10 товхимол нь FD-г зөрчиж болно. Бид харьцуулсан хэлхээнүүдийн хос тус бүрийн утгууд дээр үндэслэн арай өөр хэмжүүрийг авч үзэх болно. Хамааралтай байдлын хувьд X → Y хандлага дээр r дараах байдлаар тооцоолно.

Алдааг тооцоолъё Эмч → Өвчтөн дээрх жишээнээс. Бидэнд утгууд нь шинж чанараараа ялгаатай хоёр багц байдаг Өвчтөн, гэхдээ тэд давхцдаг Доктор: [Эмч, өвчтөн] = (Робин, Эллис) болон [Эмч, өвчтөн] = (Робин, Грэм). Алдааг тодорхойлсоны дараа бид бүх зөрчилдөөнтэй хосуудыг харгалзан үзэх ёстой бөгөөд энэ нь тэдгээрийн хоёр нь байх болно гэсэн үг юм: (, ) ба түүний урвуу байдал (, ). Томъёог орлуулаад дараахийг авна уу:

Одоо “Энэ бүхний учир нь юу вэ?” гэсэн асуултад хариулахыг оролдъё. Үнэн хэрэгтээ FD-ийн янз бүрийн хэлбэрүүд байдаг. Эхний төрөл нь мэдээллийн баазын дизайны үе шатанд администраторын тодорхойлсон хамаарал юм. Тэдгээр нь ихэвчлэн цөөн тооны, хатуу бөгөөд үндсэндээ өгөгдлийг хэвийн болгох, харилцааны схемийн дизайн хийхэд ашиглагддаг.

Хоёрдахь төрөл нь "далд" өгөгдөл болон шинж чанаруудын хоорондын урьд өмнө мэдэгддэггүй хамаарлыг илэрхийлдэг хамаарал юм. Эдгээр хамаарлыг дизайны үе шатанд авч үзээгүй бөгөөд одоо байгаа өгөгдлийн багцад зориулж нээсэн бөгөөд олон тодорхойлсон функциональ хамаарал дээр үндэслэн хадгалагдсан мэдээллийн талаар дүгнэлт хийх боломжийг бидэнд олгодог. Эдгээр нь яг бидний хамтран ажилладаг хамаарал юм. Эдгээр нь мэдээллийн олборлолт гэж нэрлэгддэг бүхэл бүтэн талбарын сэдэв бөгөөд тэдгээрт суурилсан янз бүрийн хайлтын арга техник, алгоритмууд юм. Аливаа өгөгдлийн илрүүлсэн функциональ хамаарал (яг эсвэл ойролцоо) хэрхэн ашигтай болохыг судалж үзье.

Өнөөдөр өгөгдөл цэвэрлэх нь хамаарлын үндсэн хэрэглээний нэг юм. Энэ нь "бохир өгөгдөл" -ийг тодорхойлох, дараа нь засах үйл явцыг боловсруулахад хамаарна. "Бохир өгөгдөл"-ийн нийтлэг жишээнд давхардсан, өгөгдлийн алдаа эсвэл үсгийн алдаа, дутуу утгууд, хуучирсан өгөгдөл, нэмэлт зай гэх мэт зүйлс орно.

Өгөгдлийн алдааны жишээ:

Өгөгдөл дэх давхардлын жишээ:

Жишээлбэл, бидэнд заавал биелүүлэх ёстой хууль тогтоомжийн шаардлагуудын хүснэгт, багц байдаг. Энэ тохиолдолд өгөгдлийг цэвэрлэх нь хуульд заасан шаардлагыг хангахын тулд өгөгдлийг өөрчлөх явдал юм. Өөрчлөлтийн тоо хамгийн бага байх ёстой (энэ процедурын тодорхой алгоритмууд байдаг бөгөөд бид энэ нийтлэлд анхаарлаа хандуулахгүй). Ийм өгөгдөл хувиргах жишээг доор харуулав. Зүүн талд нь хууль тогтоомжийн шаардлагад нийцэхгүй байгаа анхны харилцаа (хуулийн шаардлагын аль нэгийг зөрчсөн жишээг улаанаар тэмдэглэсэн). Баруун талд ногоон нүд нь өөрчлөгдсөн утгыг заадаг шинэчлэгдсэн харилцаа юм. Энэ процедурын дараа шаардлагатай хамаарлыг хадгалсан.

Өөр нэг алдартай програм бол мэдээллийн сангийн дизайн юм. Энд ердийн хэлбэр, хэвийн байдлыг дурдах нь зүйтэй. Нормчилал гэдэг нь харилцааг өөрийн гэсэн ердийн хэлбэрээр тодорхойлсон олон шаардлагад нийцүүлэх үйл явц юм. Бид янз бүрийн ердийн маягтуудын шаардлагыг тайлбарлахгүй (үүнийг анхан шатны өгөгдлийн сангийн ямар ч сургалтанд хийж болно), гэхдээ тус бүр нь функциональ хамаарлын тухай ойлголтыг өөр өөрийн арга замаар ашигладаг гэдгийг тэмдэглэх болно. Эцсийн эцэст, ердийн хэлбэрүүд нь үндсэндээ мэдээллийн баазыг төлөвлөхдөө харгалзан үздэг бүрэн бүтэн байдлын хязгаарлалтууд юм (энэ хүрээнд ердийн хэлбэрийг заримдаа супер түлхүүр гэж нэрлэдэг).

Доорх зурган дээрх дөрвөн хэвийн хэлбэрт тэдгээрийн хэрэглээг авч үзье. Boyce-Codd хэвийн хэлбэр нь гурав дахь хэлбэрээс илүү хязгаарлагдмал, харин дөрөв дэх хэлбэрээс бага хязгаарлалттай гэдгийг санаарай. Дөрөв дэх хэлбэрийг бид одоохондоо авч үзэхгүй, учир нь түүний томъёолол нь энэ нийтлэлд бидний сонирхлыг татахгүй байгаа олон утгатай хамаарлын талаархи ойлголтыг шаарддаг.

Хамаарал нь хэрэглэгдэх болсон өөр нэг талбар бол гэнэн Bayes ангилагчийг бүтээх, чухал шинж чанаруудыг гаргаж авах, регрессийн загваруудыг дахин параметржүүлэх зэрэг асуудлуудын орон зайн хэмжээсийг багасгах явдал юм. Анхны баримт бичгүүдэд энэ асуудлыг онцлог шинж чанар, онцлогийн хамаарал [5, 6] гэж нэрлэдэг бөгөөд мэдээллийн сангийн үзэл баримтлалыг өргөнөөр авч үзсэн болно. Ийм бүтээлүүд гарч ирснээр мэдээллийн сан, аналитик, дээр дурдсан оновчлолын асуудлыг нэг хэрэгсэл болгон нэгтгэх шийдлүүдийн эрэлт хэрэгцээ нэмэгдэж байна гэж дүгнэж болно [7, 8, 9].

Мэдээллийн багцаас холбооны хуулийг хайх олон алгоритмууд (орчин үеийн болон хуучин аль аль нь) байдаг. Эдгээр алгоритмуудыг гурван бүлэгт хувааж болно.

• Сүлжээгээр дамжин өнгөрөх алгоритмууд
• Ялгаатай ба тохиролцсон алгоритмууд
• Хамааралтай индукцийн алгоритмууд

Алгоритмын төрөл бүрийн товч тайлбарыг доорх хүснэгтэд үзүүлэв.


Энэ ангиллын талаарх дэлгэрэнгүй мэдээллийг [4] -ээс олж болно. Төрөл бүрийн алгоритмын жишээг доор үзүүлэв.

Функциональ хамаарлыг олох хэд хэдэн аргыг хослуулсан шинэ алгоритмууд одоогоор гарч ирж байна. Ийм алгоритмуудын жишээнд Pyro [2] болон HyFD [3] орно. Тэдний үйл ажиллагааны дүн шинжилгээг энэ цувралын дараагийн нийтлэлүүдэд оруулах болно. Энэ нийтлэлд бид зөвхөн хамаарлыг илрүүлэх арга техникийг ойлгоход шаардлагатай үндсэн ойлголтууд болон леммагийн талаар ярилцах болно.

Хамгийн энгийнээс эхэлцгээе: хоёр дахь төрлийн алгоритмд ашигладаг олонлогуудыг ялгаж, зөвшөөр. Ялгаатай олонлог гэдэг нь ижил утгатай биш олонлог, харин зөвшөөрч буй олонлог нь ижил утгатай багцуудын багц юм. Энэ тохиолдолд бид зөвхөн хараат байдлын зүүн талыг авч үздэг гэдгийг тэмдэглэх нь зүйтэй.

Дээр дурдсан өөр нэг чухал ойлголт бол алгебрийн сүлжээ юм. Орчин үеийн олон алгоритмууд энэ үзэл баримтлалд тулгуурладаг тул энэ нь юу болохыг ойлгох хэрэгтэй.

Сүлжээний тухай ойлголтыг нэвтрүүлэхийн тулд хэсэгчлэн эрэмбэлсэн багцын (эсвэл товчоор посет) тодорхойлолт шаардлагатай.

Тодорхойлолт 2. a, b, c ∈ S бүрт дараах шинж чанаруудыг хангасан тохиолдолд S олонлогийг ⩽ хоёртын хамаарлаар хэсэгчлэн эрэмбэлсэн гэж нэрлэдэг.

1. Рефлекс, өөрөөр хэлбэл a ⩽ a
2. Эссиметри, өөрөөр хэлбэл a ⩽ b ба b ⩽ a бол a = b
3. Дамжин өнгөрөх чадвар, өөрөөр хэлбэл, a ⩽ b ба b ⩽ c-ийн хувьд a ⩽ c байна.

Ийм хамаарлыг (хатуу бус) хэсэгчилсэн дараалал гэж нэрлэдэг ба олонлогийг өөрөө хэсэгчилсэн эрэмбэлэгдсэн олонлог гэж нэрлэдэг. Албан ёсны тэмдэглэгээ: ⟨S, ⩽⟩.

Хэсэгчилсэн эрэмбэлэгдсэн олонлогийн энгийн жишээ болгон бид ердийн дарааллын ⩽ харьцаатай бүх натурал тоон N олонлогийг авч болно. Шаардлагатай бүх аксиомууд хангагдсан эсэхийг шалгахад хялбар байдаг.

Илүү бодит жишээ. Оруулсан хамаарлаар эрэмблэгдсэн {1, 2, 3} бүх дэд олонлогийг ⊆ гэж үзье. Үнэн хэрэгтээ энэ хамаарал нь хэсэгчилсэн эрэмбийн бүх нөхцлийг хангадаг тул ⟨P ({1, 2, 3}), ⊆⟩ нь хэсэгчилсэн эрэмблэгдсэн олонлог юм. Доорх зурагт энэ олонлогийн бүтцийг дүрсэлсэн болно: хэрэв сумны дагуу нэг элементээс нөгөө элемент рүү хүрэх боломжтой бол тэдгээр нь дарааллын харьцаатай байна.

Бидэнд математикийн салбараас хоёр энгийн тодорхойлолт хэрэгтэй болно: supremum болон infimum.

Тодорхойлолт 3. ⟨S, ⩽⟩ нь хэсэгчилсэн эрэмбэлэгдсэн олонлог, A ⊆ S байг. A-ийн дээд хязгаар нь ∀x ∈ S: x ⩽ u байх u ∈ S элемент юм. U нь S-ийн бүх дээд хязгаарын олонлог байг. Хэрэв U хамгийн бага элементтэй бол түүнийг дээд хэмжээ гэж нэрлэх ба A sup гэж тэмдэглэнэ.

Яг доод хязгаарын тухай ойлголтыг үүнтэй төстэй байдлаар нэвтрүүлсэн.

Тодорхойлолт 4. ⟨S, ⩽⟩ нь хэсэгчилсэн эрэмбэлэгдсэн олонлог, A ⊆ S байг. А-ийн доод хязгаар нь l ∈ S элемент бөгөөд ∀x ∈ S: l ⩽ x болно. L нь S-ийн бүх доод хязгаарын олонлог байг. Хэрэв L нь хамгийн их элементтэй бол түүнийг infimum гэж нэрлэх ба inf A гэж тэмдэглэнэ.

Жишээ болгон дээр өгөгдсөн хэсэгчилсэн эрэмбэлэгдсэн ⟨P ({1, 2, 3}), ⊆⟩ олонлогийг авч үзээд түүний дээд ба инфимумыг олъё:

Одоо бид алгебрийн торны тодорхойлолтыг томъёолж болно.

Тодорхойлолт 5. ⟨P, ⩽⟩ нь хоёр элементийн дэд олонлог бүр хамгийн бага дээд доод хязгаартай байхаар хэсэгчлэн эрэмбэлэгдсэн олонлог байг. Дараа нь P-г алгебрийн сүлжээ гэж нэрлэдэг. Энэ тохиолдолд sup{x, y}-г x ∨ y, inf {x, y}-г x ∧ y гэж бичнэ.

Бидний ажилласан жишээ ⟨P ({1, 2, 3}), ⊆⟩ нь тор мөн эсэхийг шалгацгаая. Үнэн хэрэгтээ, a бүрийн хувьд b ∈ P ({1, 2, 3}), a ∨ b = a ∪ b, a ∧ b = a ∩ b байна. Жишээлбэл, {1, 2} ба {1, 3} олонлогуудыг авч үзээд тэдгээрийн доод ба дээд утгыг ол. Хэрэв бид тэдгээрийг огтлолцвол инфимум болох {1} олонлогийг олж авна. Дээд утгыг тэдгээрийн нэгдлээр олж авна: {1, 2, 3}.

FD-г илрүүлэх алгоритмд хайлтын орон зайг ихэвчлэн нэг элементийн багц (хайлтын сүлжээний эхний түвшнийг уншина уу, хамаарлын зүүн тал нь нэг шинж чанараас бүрддэг) нь анхны харилцааны шинж чанар бүрийг төлөөлдөг тор хэлбэрээр илэрхийлэгддэг.
Эхэндээ ∅ → төрлийн хамаарлыг авч үзнэ Ганц шинж чанар. Энэ алхам нь ямар шинж чанарууд нь үндсэн түлхүүр болохыг тодорхойлох боломжийг олгодог (ийм шинж чанаруудыг тодорхойлох хүчин зүйл байхгүй тул зүүн гар тал нь хоосон байна). Дараа нь эдгээр алгоритмууд нь торны дагуу дээшээ хөдөлдөг. Торыг бүхэлд нь дамжих боломжтой гэдгийг тэмдэглэх нь зүйтэй бөгөөд хэрэв зүүн талын хүссэн дээд хэмжээг оролт болгон өгвөл алгоритм нь тухайн хэмжээтэй түвшнээс цааш явахгүй гэсэн үг юм.

Доорх зурагт алгебрийн торыг FD олох асуудалд хэрхэн ашиглаж болохыг харуулав. Энд ирмэг бүр (X, XY) нь хамаарал юм X → YЖишээлбэл, бид эхний шатыг давж, донтолтыг хадгалсан гэдгийг мэддэг. A → B (бид үүнийг оройн хоорондох ногоон холболтоор харуулах болно A и B). Энэ нь цаашид бид сүлжээг дээшлэхэд бид хамаарлыг шалгаж чадахгүй гэсэн үг юм A, C → B, учир нь энэ нь цаашид хамгийн бага байх болно. Үүний нэгэн адил, хэрэв хараат байдал хэвээр байвал бид үүнийг шалгахгүй. C → B.

Цаашилбал, дүрмээр бол холбооны хуулиудыг хайх орчин үеийн бүх алгоритмууд нь хуваалт гэж нэрлэгддэг өгөгдлийн бүтцийг ашигладаг (анхны эх сурвалжид хуулагдах хуваалт [1]). Хуваалтын албан ёсны тодорхойлолт нь дараах байдалтай байна.

Тодорхойлолт 6. X ⊆ R нь r харилцааны шинж чанаруудын багц байг. Кластер гэдэг нь X-ийн хувьд ижил утгатай, өөрөөр хэлбэл c(t) = {i|ti[X] = t[X]} r-ийн багцын индексүүдийн багц юм. Хуваалт гэдэг нь нэг урттай кластеруудыг оруулаагүй кластеруудын багц юм:

Энгийнээр хэлбэл аттрибутын хуваалт X Жагсаалт бүр нь ижил утгатай мөрийн тоог агуулсан жагсаалтын багц юм XОрчин үеийн уран зохиолд хуваалтуудыг төлөөлдөг бүтцийг байрлалын жагсаалтын индекс (PLI) гэж нэрлэдэг. Нэг урттай кластеруудыг PLI шахалтын зорилгоор хассан, учир нь эдгээр кластерууд нь үргэлж амархан танигдах өвөрмөц утгатай зөвхөн бичлэгийн дугаарыг агуулдаг.

Нэг жишээ авч үзье. Өвчтөнүүдтэй нэг хүснэгтэд буцаж очоод баганын хуваалтуудыг үүсгэцгээе. Өвчтөн и Хүйс (зүүн талд хүснэгтийн мөрийн дугаар тэмдэглэгдсэн шинэ багана гарч ирэв):

Энэ тохиолдолд тодорхойлолтын дагуу баганын хуваалт Өвчтөн Нэг кластеруудыг хуваалтаас хассан тул үнэндээ хоосон байх болно.

Хуваалтыг олон шинж чанараар авч болно. Үүнийг хийх хоёр арга бий: хүснэгтийг давтах, шаардлагатай бүх шинж чанаруудаар нэг дор хуваах, эсвэл шинж чанаруудын дэд бүлэгт хуваалтуудыг огтлох. Холбооны хуулийн хайлтын алгоритмууд хоёр дахь сонголтыг ашигладаг.

Энгийнээр хэлбэл, жишээ нь, баганаар хуваах ABC, та хуваалтуудыг авч болно AC и B (эсвэл бусад салангид дэд олонлогууд) ба тэдгээрийг огтолно. Хоёр хуваалтын огтлолцох ажиллагаа нь хоёр хуваалтад нийтлэг байдаг хамгийн урт кластеруудыг тодорхойлдог.

Нэг жишээг харцгаая:

Эхний тохиолдолд бид хоосон хуваалтыг олж авсан. Хэрэв та хүснэгтийг анхааралтай ажиглавал хоёр шинж чанарын хувьд ижил утга байхгүй гэдгийг харах болно. Гэсэн хэдий ч, хэрэв бид хүснэгтийг бага зэрэг өөрчилвөл (баруун талд байгаа тохиолдол) бид хоосон бус уулзварыг олж авна. Түүнээс гадна 1 ба 2-р мөр нь шинж чанаруудын хувьд ижил утгыг агуулна. Хүйс и Эмч.

Дараа нь бидэнд хуваалтын хэмжээ гэсэн ойлголт хэрэгтэй болно. Албан ёсоор:

Энгийнээр хэлэхэд хуваалтын хэмжээ нь хуваалтад багтсан кластеруудын тоо юм (ганц кластерууд хуваалтад ороогүй гэдгийг санаарай!):

Одоо бид өгөгдсөн хуваалтуудын хувьд хамаарал байгаа эсэхийг тодорхойлох боломжийг олгодог үндсэн леммауудын нэгийг тодорхойлж болно:

Лемма 1. A, B → C хамаарал нь зөвхөн болон зөвхөн тохиолдолд л хэрэгжинэ

Леммийн дагуу, хамаарал байгаа эсэхийг тодорхойлохын тулд дөрвөн алхам хийх ёстой.

1. Хараат байдлын зүүн талын хуваалтыг тооцоол
2. Хамааралтай байдлын баруун талын хуваалтыг тооцоол
3. Эхний болон хоёр дахь алхмын үржвэрийг тооцоол
4. Эхний болон гурав дахь үе шатанд олж авсан хуваалтын хэмжээг харьцуулна уу

Өгөгдсөн леммийн дагуу хамаарал биелэх эсэхийг шалгах жишээг доор харуулав.

Энэ нийтлэлд бид функциональ хамаарал, функциональ хамаарал зэрэг ойлголтуудыг судалж, тэдгээрийн хэрэглээний талаар ярилцаж, функциональ хамаарлыг олох одоо байгаа алгоритмуудын талаар ярилцав. Бид мөн функциональ хамаарлыг олох орчин үеийн алгоритмуудад идэвхтэй хэрэглэгддэг үндсэн боловч чухал ойлголтуудыг дэлгэрэнгүй авч үзсэн.

Лавлагаа:

1. Huhtala Y. et al. TANE: Функциональ ба ойролцоо хамаарлыг илрүүлэх үр дүнтэй алгоритм // Компьютерийн сэтгүүл. – 1999. – Т. 42. – No2. – 100-111-р тал.
2. Kruse S., Naumann F. Ойролцоогоор хамаарлыг үр дүнтэй илрүүлэх // VLDB Endowment-ийн эмхтгэл. – 2018. – Т. 11. – No7. – 759-772 х.
3. Папенброк Т., Науман Ф. Функциональ хамаарлыг илрүүлэх эрлийз хандлага // Мэдээллийн менежментийн 2016 оны олон улсын бага хурлын эмхэтгэл. – МУЗ, 2016. – 821-833 х.
4. Papenbrock T. et al. Функциональ хамаарлын нээлт: Долоон алгоритмын туршилтын үнэлгээ //VLDB Endowment-ийн эмхтгэл. – 2015. – Т. 8. – No 10. – 1082-1093 х.
5. Kumar A. et al. Нэгдэх үү, үгүй ​​юу?: Онцлогыг сонгохын өмнө нэгдэх талаар хоёр удаа бодоорой // Мэдээллийн менежментийн 2016 оны олон улсын бага хурлын эмхэтгэл. – МУЗ, 2016. – 19-34-р тал.
6. Abo Khamis M. et al. Сийрэг тензороор мэдээллийн санд суралцах нь // Өгөгдлийн сангийн системийн зарчмуудын тухай ACM SIGMOD-SIGACT-SIGAI 37 дахь симпозиумын эмхэтгэл. – МУЗ, 2018. – 325-340-р тал.
7. Hellerstein JM et al. MADlib аналитик номын сан: эсвэл MAD ур чадвар, SQL //VLDB хандивын эмхэтгэл. – 2012. – Т. 5. – No 12. – 1700-1711 х.
8. Qin C., Rusu F. Terascale distributed gradient descent optimization-д зориулсан таамаглалын ойролцоо тооцоо // Үүлэн дэх өгөгдлийн аналитикийн дөрөв дэх семинарын эмхтгэл. – МУЗ, 2015. – P. 1.
9. Мэн X. нар. Mllib: Apache spark дахь машин сургалт // The Journal of Machine Learning Research. – 2016. – Т. 17. – No1. – 1235-1241-р тал.

Нийтлэлийн зохиогчид: Анастасия Бирило, судлаач JetBrains судалгаа, CS төвийн оюутан и Никита Бобров, судлаач JetBrains судалгаа

Эх сурвалж: www.habr.com