Veritabanlarındaki işlevsel bağımlılıkları verimli bir şekilde bulun

Verilerde işlevsel bağımlılıkların bulunması, veri analizinin çeşitli alanlarında kullanılır: veritabanı yönetimi, veri temizleme, veritabanı tersine mühendislik ve veri araştırması. Bağımlılıkların kendileri hakkında zaten yayınlamıştık Makale Anastasia Birillo ve Nikita Bobrov. Bu kez Bilgisayar Bilimleri Merkezi'nden bu yıl mezun olan Anastasia, merkezde savunduğu araştırma çalışması kapsamında bu çalışmanın gelişimini paylaşıyor.

görev seçimi

Bilgisayar Bilimleri merkezinde okurken veritabanlarını derinlemesine incelemeye, yani işlevsel ve fark bağımlılıklarını aramaya başladım. Bu konu üniversitedeki ders çalışmamın konusuyla ilgiliydi, dolayısıyla ders üzerinde çalışırken veritabanlarındaki çeşitli bağımlılıklar hakkında makaleler okumaya başladım. Bu alanla ilgili bir inceleme yazdım - ilk incelemelerimden biri makaleler İngilizce olarak SEIM-2017 konferansına sundum. Sonuçta kabul edildiğini öğrendiğimde çok mutlu oldum ve konuyu daha derinlemesine araştırmaya karar verdim. Konseptin kendisi yeni değil - 90'lı yıllarda kullanılmaya başlandı, ancak şimdi bile birçok alanda kullanılıyor.

Merkezdeki ikinci dönemimde fonksiyonel bağımlılıkları bulmaya yönelik algoritmaları geliştirmek için bir araştırma projesi başlattım. JetBrains Research'te St. Petersburg Devlet Üniversitesi yüksek lisans öğrencisi Nikita Bobrov ile birlikte bu konu üzerinde çalıştı.

İşlevsel bağımlılıkları aramanın hesaplama karmaşıklığı

Temel sorun hesaplama karmaşıklığıdır. Olası minimum ve önemsiz bağımlılıkların sayısı yukarıda belirtilen değerle sınırlıdır. Nerede — tablo niteliklerinin sayısı. Algoritmaların çalışma süresi yalnızca öznitelik sayısına değil aynı zamanda satır sayısına da bağlıdır. 90'lı yıllarda, normal bir masaüstü bilgisayardaki federal yasa arama algoritmaları, 20'ye kadar öznitelik ve onbinlerce satır içeren veri kümelerini birkaç saate kadar işleyebiliyordu. Çok çekirdekli işlemciler üzerinde çalışan modern algoritmalar, yüzlerce özellikten (200'e kadar) ve yüzbinlerce satırdan oluşan veri kümelerinin bağımlılıklarını yaklaşık aynı anda tespit eder. Ancak bu yeterli değildir: Böyle bir süre, çoğu gerçek dünya uygulaması için kabul edilemez. Bu nedenle mevcut algoritmaları hızlandıracak yaklaşımlar geliştirdik.

Bölüm kesişimleri için önbellekleme şemaları

Çalışmanın ilk bölümünde bölüm kesişim yöntemini kullanan bir algoritma sınıfı için önbellekleme şemaları geliştirdik. Bir öznitelik için bölüm, her listenin belirli bir öznitelik için aynı değerlere sahip satır numaralarını içerdiği bir dizi listedir. Bu tür listelerin her birine küme adı verilir. Birçok modern algoritma, bir bağımlılığın tutulup tutulmadığını belirlemek için bölümleri kullanır, yani şu lemmaya uyarlar: Bağımlılık eğer tutulursa ... Buraya bir bölüm belirlenir ve bölüm boyutu kavramı kullanılır - içindeki kümelerin sayısı. Bölümleri kullanan algoritmalar, bağımlılık ihlal edildiğinde bağımlılığın sol tarafına ek nitelikler ekler ve ardından bölümlerin kesişme işlemini gerçekleştirerek yeniden hesaplar. Bu işleme yazılarda uzmanlaşma denir. Ancak, yalnızca birkaç uzmanlaşma turundan sonra tutulabilecek bağımlılıklara yönelik bölümlerin aktif olarak yeniden kullanılabileceğini ve kesişim işleminin pahalı olması nedeniyle algoritmaların çalışma süresini önemli ölçüde azaltabileceğini fark ettik.

Bu nedenle Ters Entropi adını verdiğimiz metriğimizin yanı sıra Shannon Entropi ve Ginny Belirsizliğine dayalı bir buluşsal yöntem önerdik. Shannon Entropisinin küçük bir modifikasyonudur ve veri setinin benzersizliği arttıkça artar. Önerilen buluşsal yöntem aşağıdaki gibidir:

öyle — yakın zamanda hesaplanan bölümün benzersizlik derecesi Ve bireysel niteliklerin benzersizlik derecelerinin ortancasıdır. Yukarıda açıklanan üç metriğin tümü bir benzersizlik metriği olarak test edildi. Buluşsal yöntemde iki değiştiricinin olduğunu da fark edebilirsiniz. Birincisi, geçerli bölümün birincil anahtara ne kadar yakın olduğunu gösterir ve potansiyel anahtardan uzaktaki bölümleri daha büyük ölçüde önbelleğe almanıza olanak tanır. İkinci değiştirici, önbellek doluluğunu izlemenize olanak tanır ve böylece boş alan varsa önbelleğe daha fazla bölüm eklenmesini teşvik eder. Bu sorunun başarılı çözümü, PYRO algoritmasını veri setine bağlı olarak %10-40 oranında hızlandırmamızı sağladı. PYRO algoritmasının bu alanda en başarılı olduğunu belirtmekte fayda var.

Aşağıdaki şekilde, temel yazı-tura önbelleğe alma yaklaşımıyla karşılaştırıldığında önerilen buluşsal yöntemin uygulanmasının sonuçlarını görebilirsiniz. X ekseni logaritmiktir.

Bölümleri saklamanın alternatif bir yolu

Daha sonra bölümleri depolamanın alternatif bir yolunu önerdik. Bölümler, her biri belirli nitelikler için aynı değerlere sahip demetlerin sayılarını depolayan bir dizi kümedir. Bu kümeler, örneğin bir tablodaki veriler sıralanmışsa, uzun dizi sayıları içerebilir. Bu nedenle, bölümleri depolamak için, yani değerlerin bölüm kümelerinde aralıklı olarak depolanması için bir sıkıştırma şeması önerdik:

$$display$$pi(X) = {{alt destek{1, 2, 3, 4, 5}, 7__{İlk aralık}, alt destek{8, 10__{İkinci aralık}, 1}}\ downarrow{ Sıkıştırma} \ pi(X) = {{alt destek{$, 5, 7__{Birinci~aralık}, alt destek{8, 10}__{İkinci~aralık}, XNUMX}}$$display$$

Bu yöntem, TANE algoritmasının çalışması sırasındaki bellek tüketimini %1'den %25'e düşürmeyi başardı. TANE algoritması, federal yasaları aramak için kullanılan klasik bir algoritmadır; çalışması sırasında bölümleri kullanır. Uygulamanın bir parçası olarak TANE algoritması seçildi, çünkü önerilen yaklaşımın işe yarayıp yaramadığını değerlendirmek için aralık depolamayı uygulamak, örneğin PYRO'ya göre çok daha kolaydı. Elde edilen sonuçlar aşağıdaki şekilde gösterilmektedir. X ekseni logaritmiktir.

Konferans ADBIS-2019

Araştırmanın sonuçlarına dayanarak Eylül 2019'da bir makale yayınladım. Verimli İşlevsel Bağımlılık Keşfi için Akıllı Önbelleğe Alma 23. Avrupa Veritabanları ve Bilgi Sistemlerinde Gelişmeler Konferansı'nda (ADBIS-2019). Sunum sırasında çalışma, veritabanları alanında önemli isimlerden Bernhard Thalheim tarafından not edildi. Araştırma sonuçları, St. Petersburg Devlet Üniversitesi'nde matematik ve mekanik alanında yüksek lisans derecemdeki tezimin temelini oluşturdu; bu sırada önerilen her iki yaklaşım da (önbellekleme ve sıkıştırma) her iki algoritmada da uygulandı: TANE ve PYRO. Aynı zamanda, sonuçlar önerilen yaklaşımların evrensel olduğunu gösterdi, çünkü her iki algoritmada da her iki yaklaşımda da bellek tüketiminde önemli bir azalma ve algoritmaların çalışma süresinde önemli bir azalma gözlemlendi.

Kaynak: habr.com