İşlevsel bağımlılık - Functional dependency

İçinde ilişkisel veritabanı teori, bir işlevsel bağımlılık bir kısıtlama iki öznitelik kümesi arasında ilişki bir veritabanından. Başka bir deyişle, işlevsel bir bağımlılık, iki anahtar arasındaki bir kısıtlamadır. R, bir dizi özellik X içinde R söylendi işlevsel olarak belirlemek başka bir özellik kümesi Y, Ayrıca R, (yazılı XY) eğer ve sadece her biri X değer R tam olarak bir ile ilişkilidir Y değer R; R sonra söylendi tatmin etmek işlevsel bağımlılık XY. Eşdeğer olarak, projeksiyon bir işlevi yani Y bir fonksiyonudur X.[1][2] Basit bir deyişle, eğer X öznitelikler biliniyor (öyle olduklarını söyle x), ardından Y karşılık gelen özellikler x onlara bakarak belirlenebilir hiç demet nın-nin R kapsamak x. Geleneksel olarak X denir belirleyici ayarla ve Y bağımlı Ayarlamak. İşlevsel bir bağımlılık FD'si: XY denir önemsiz Eğer Y bir alt küme nın-nin X.

Başka bir deyişle, bir bağımlılık FD'si: XY değerlerinin olduğu anlamına gelir Y değerleri ile belirlenir X. Aynı değerleri paylaşan iki demet X aynı değerlere sahip olacak Y.

Fonksiyonel bağımlılıkların belirlenmesi, veri tabanlarının tasarlanmasının önemli bir parçasıdır. ilişkisel model, ve veritabanı normalleştirme ve normalsizleştirme. İşlevsel bağımlılıkların basit bir uygulaması Heath teoremi; bir ilişki olduğunu söylüyor R bir öznitelik kümesi üzerinden U ve işlevsel bir bağımlılığı tatmin etmek XY güvenli bir şekilde iki ilişkiye bölünebilir kayıpsız birleşim ayrıştırma mülkiyet, yani içine nerede Z = UXY niteliklerin geri kalanıdır. (Sendikalar Veri tabanı teorisinde öznitelik kümelerinin sayısı geleneksel olarak yalnızca yan yana koymalarla gösterilir.) Bu bağlamdaki önemli bir fikir, aday anahtar, bir ilişkideki tüm öznitelikleri işlevsel olarak belirleyen minimum öznitelikler kümesi olarak tanımlanır. İşlevsel bağımlılıklar, öznitelik alanları, uygun olmayan verileri olabildiğince dışlayacak kısıtlamalar oluşturacak şekilde seçilirler. kullanıcı alanı sistemden mümkün olduğunca.

Bir kavram mantıksal çıkarım fonksiyonel bağımlılıklar için şu şekilde tanımlanır: bir dizi fonksiyonel bağımlılık mantıksal olarak başka bir bağımlılık kümesini ima eder herhangi bir ilişki varsa R tüm bağımlılıkları tatmin etmek ayrıca tüm bağımlılıkları karşılar ; bu genellikle yazılır . İşlevsel bağımlılıklar için mantıksal çıkarım kavramı, ses ve tamamlayınız sonlu aksiyomatizasyon, olarak bilinir Armstrong'un aksiyomları.

Örnekler

Arabalar

Birinin araçları ve motorlarının kapasitesini izlemek için bir sistem tasarladığını varsayalım. Her aracın benzersiz bir araç Tanımlama Numarası (VIN). Biri yazardı VINMotor kapasitesi çünkü bir aracın motorunun birden fazla kapasiteye sahip olması uygun değildir. (Bu durumda, araçların yalnızca bir motoru olduğunu varsayarsak.) Diğer yandan, Motor kapasitesiVIN yanlıştır çünkü aynı motor kapasitesine sahip birçok araç olabilir.

Bu işlevsel bağımlılık, EngineCapacity özniteliğinin, aday anahtar VIN. Ancak bu her zaman uygun olmayabilir. Örneğin, bu işlevsel bağımlılık, geçişli işlevsel bağımlılıklar VIN → VehicleModel ve VehicleModel → EngineCapacity, bu durumda normalleştirilmiş bir ilişki ile sonuçlanmaz.

Dersler

Bu örnek, işlevsel bağımlılık kavramını göstermektedir. Modellenen durum, üniversite öğrencilerinin her birine bir öğretim asistanı (TA) atanmış bir veya daha fazla dersi ziyaret etmesidir. Ayrıca, her öğrencinin bir sömestrde olduğunu ve benzersiz bir tam sayı kimliği ile tanımlandığını varsayalım.

Öğrenci KimliğiDönemDersTA
12346Sayısal yöntemlerJohn
12214Sayısal yöntemlerSmith
12346Görsel HesaplamaBob
12012Sayısal yöntemlerPeter
12012Fizik IISimon

Bu tablodaki iki satırda aynı Öğrenci Kimliği bulunduğunda, bunların da zorunlu olarak aynı Dönem değerlerine sahip olduğunu görürüz. Bu temel gerçek, işlevsel bir bağımlılıkla ifade edilebilir:

  • Öğrenci Kimliği → Dönem.

Öğrencinin farklı bir dönem değerine sahip olduğu bir satır eklendiğinde, fonksiyonel bağımlılığın, FD'nin artık mevcut olmayacağını unutmayın. Bu, FD'yi geçersiz kılacak değerlere sahip olmanın mümkün olması nedeniyle, veriler tarafından FD'nin ima edildiği anlamına gelir.

Diğer önemsiz işlevsel bağımlılıklar belirlenebilir, örneğin:

  • {StudentID, Lecture} → TA
  • {Öğrenci Kimliği, Ders} → {TA, Sömestr}

İkincisi, {StudentID, Lecture} kümesinin bir süper ilişkinin.

Çalışan departmanı modeli

İşlevsel bağımlılığın klasik bir örneği, çalışan departmanı modelidir.

Çalışan kimliğiİşçi adıDepartman KimliğiBölüm Adı
0001John Doe1İnsan kaynakları
0002Jane Doe2Pazarlama
0003John Smith1İnsan kaynakları
0004Jane Goodall3Satış

Bu durum, birden çok işlevsel bağımlılığın tek bir veri temsilinde gömülü olduğu bir örneği temsil eder. Bir çalışan yalnızca bir departmanın üyesi olabileceğinden, o çalışanın benzersiz kimliğinin departmanı belirlediğini unutmayın.

  • Çalışan Kimliği → Çalışan Adı
  • Çalışan Kimliği → Departman Kimliği

Bu ilişkiye ek olarak, tablonun anahtar olmayan bir öznitelik aracılığıyla işlevsel bir bağımlılığı da vardır.

  • Departman Kimliği → Departman Adı

Bu örnek, bir FD Çalışan Kimliği → Departman Kimliği olsa bile, çalışan kimliğinin departman kimliğinin belirlenmesi için mantıksal bir anahtar olmayacağını göstermektedir. Verilerin normalleştirme süreci tüm FD'leri tanıyacak ve tasarımcının verilere dayalı olarak daha mantıklı tablolar ve ilişkiler oluşturmasına izin verecektir.

Fonksiyonel bağımlılıkların özellikleri ve aksiyomatizasyonu

Verilen X, Y, ve Z bir ilişkideki öznitelik kümeleridir Rişlevsel bağımlılıkların çeşitli özellikleri türetilebilir. En önemlileri arasında, genellikle adı verilen Armstrong'un aksiyomları:[3]

  • Yansıtma: Eğer Y alt kümesidir X, sonra XY
  • Büyütme: Eğer XY, sonra XZYZ
  • Geçişlilik: Eğer XY ve YZ, sonra XZ

"Refleksivite" sadece yani gerçek bir aksiyom diğer ikisinin uygun olduğu yerde çıkarım kuralları, daha doğrusu aşağıdaki sözdizimsel sonuç kurallarına yol açmaktadır:[4]



.

Bu üç kural bir ses ve tamamlayınız fonksiyonel bağımlılıkların aksiyomatizasyonu. Bu aksiyomatizasyon bazen sonlu olarak tanımlanır çünkü çıkarım kurallarının sayısı sonludur,[5] aksiyom ve çıkarım kurallarının tümü olduğu uyarısıyla şemalar yani X, Y ve Z tüm temel terimler (öznitelik kümeleri) üzerinden değişir.[4]

Bu kurallardan şu ikincil kuralları çıkarabiliriz:[3]

  • Birlik: Eğer XY ve XZ, sonra XYZ
  • Ayrışma: Eğer XYZ, sonra XY ve XZ
  • Sözde aktarım: Eğer XY ve WYZ, sonra WXZ

Birleşme ve ayrıştırma kuralları bir mantıksal eşdeğerlik bunu belirterekXYZ, tutar iff XY ve XZ. Bu bazen bölme / birleştirme kuralı olarak adlandırılır.[6]

Bazen kullanışlı olan başka bir kural şudur:[7]

  • Kompozisyon: Eğer XY ve ZW, sonra XZYW

İşlevsel bağımlılığın kapatılması

Kapanış, esasen, işlevsel bağımlılıkları kullanılarak belirli bir ilişki için bir dizi bilinen değerden belirlenebilen tam değerler kümesidir. Biri kullanır Armstrong'un aksiyomları bir kanıt sağlamak için - yani dönüşlülük, güçlendirme, geçişlilik.

Verilen ve tutan bir dizi FD : Kapanış içinde (belirtilen +) mantıksal olarak ima edilen tüm FD'lerin kümesidir. .

Bir dizi özniteliğin kapatılması

Bir dizi özellik X'in kapatılması X kümesi+ kullanılarak X tarafından işlevsel olarak belirlenen tüm özniteliklerin +.

Misal

Aşağıdaki FD listesini hayal edin. Bu ilişkiden A için bir kapanış hesaplayacağız.

1. BirB
2. B → C
3. ABD

Kapanış aşağıdaki gibi olacaktır:

a) A → A (Armstrong'un yansımasına göre)
b) A → AB (1. ve (a) ile)
c) A → ABD ((b), 3 ve Armstrong geçişliliği)
d) A → ABCD ((c) ve 2'ye göre)

Bu nedenle kapatma A → ABCD'dir. A'nın kapanışını hesaplayarak, kapanışı ilişkideki her bir veri değeri olduğu için A'nın da iyi bir aday anahtar olduğunu doğruladık.

Kapaklar ve eşdeğerlik

Kapaklar

Tanım: kapakları eğer her FD buradan çıkarılabilir . kapakları Eğer ++
Her işlevsel bağımlılık kümesinin bir kanonik kapak.

İki set FD'nin denkliği

İki set FD ve şema üzerinde eşdeğerdir, yazılı , Eğer + = +. Eğer , sonra için bir kapak ve tam tersi. Başka bir deyişle, eşdeğer işlevsel bağımlılık kümeleri denir kapakları birbirinden.

Yedeksiz kapaklar

Bir set Uygun bir alt küme yoksa FD'lerin yüzdesi yedeksizdir nın-nin ile . Eğer böyle bir var, gereksizdir. yedek olmayan bir teminattır Eğer için bir kapak ve gereksizdir.
Yedeksizliğin alternatif bir karakterizasyonu şudur: FD yoksa yedeksizdir XY içinde öyle ki - {XY} XY. FD'yi arayın XY içinde gereksiz Eğer - {XY} XY.

Normalleştirme uygulamaları

Heath teoremi

İşlevsel bağımlılıkların önemli bir özelliği (anında uygulama sağlayan), eğer R bazı özellikler kümesinden adlandırılan sütunlarla bir ilişkidir U ve R bazı işlevsel bağımlılıkları karşılar XY sonra nerede Z = UXY. Sezgisel olarak, işlevsel bir bağımlılık varsa XY tutar R, bu durumda ilişki sütunun yanında güvenli bir şekilde iki ilişkiye bölünebilir X (hangisinin anahtarı ) iki parça geri birleştirildiğinde hiçbir verinin kaybolmamasını sağlamak, yani işlevsel bir bağımlılık bir yapı oluşturmak için basit bir yol sağlar. kayıpsız birleşim ayrışması nın-nin R iki küçük ilişkide. Bu gerçek bazen denir Heaths teoremi; veritabanı teorisindeki erken sonuçlardan biridir.[8]

Heath teoremi etkili bir şekilde şu değerleri çıkarabileceğimizi söylüyor Y büyük ilişkiden R ve bunları tek bir yerde saklayın, için satırda değer tekrarı olmayan X ve etkili bir arama tablosu için Y tarafından anahtarlanmış X ve sonuç olarak güncellemek için tek bir yer vardır Y her birine karşılık gelen X "büyük" ilişkinin aksine R her birinin potansiyel olarak birçok kopyasının bulunduğu X, her biri kendi kopyasıyla Y güncellemelerde senkronize tutulması gereken. (Bu fazlalığın ortadan kaldırılması, OLTP pek çok değişikliğin beklendiği, ancak çok fazla olmayan bağlamlar OLAP Çoğunlukla sorguları içeren bağlamlar.) Heath'in ayrışması yalnızca X gibi davranmak yabancı anahtar büyük masanın geri kalanında .

Ancak işlevsel bağımlılıklar ile karıştırılmamalıdır dahil etme bağımlılıkları yabancı anahtarlar için biçimcilik olan; normalleştirme için kullanılsalar bile, işlevsel bağımlılıklar bir ilişki (şema) üzerindeki kısıtlamaları ifade ederken, dahil etme bağımlılıkları bir ilişkideki ilişki şemaları arasındaki kısıtlamaları ifade eder. veritabanı şeması. Dahası, bu iki kavram, bağımlılıkların sınıflandırılması: işlevsel bağımlılıklar eşitlik üreten bağımlılıklar oysa dahil etme bağımlılıkları demet oluşturan bağımlılıklar. İlişki şeması ayrıştırılmasından (normalleştirme) sonra referans kısıtlamaların uygulanması, yeni bir biçimcilik, yani dahil etme bağımlılıkları gerektirir. Heath teoreminden kaynaklanan ayrıştırmada, tuplelerin eklenmesini engelleyen hiçbir şey yoktur. bazı değerlere sahip olmak X bulunamadı .

Normal formlar

Normal formlar veritabanı normalleştirme bir tablonun "iyiliğini" belirleyen seviyeler. Genel olarak üçüncü normal biçim ilişkisel veritabanı için "iyi" bir standart olarak kabul edilir.[kaynak belirtilmeli ]

Normalleştirme, veritabanını güncelleme, ekleme ve silme anormalliklerinden kurtarmayı amaçlar. Ayrıca, ilişkiye yeni bir değer eklendiğinde, veritabanı üzerinde minimum etkiye sahip olmasını ve böylece veritabanını kullanan uygulamalar üzerinde minimum etkisinin olmasını sağlar.[kaynak belirtilmeli ]

Sete bağlı olarak indirgenemez fonksiyon

Küme aşağıdaki üç özelliğe sahipse, bir dizi S işlevsel bağımlılık indirgenemez:

  1. S'nin işlevsel bağımlılığının her sağ kümesi yalnızca bir öznitelik içerir.
  2. S'nin işlevsel bağımlılığının her sol kümesi indirgenemez. Sol kümeden herhangi bir özniteliği düşürmenin S'nin içeriğini değiştireceği anlamına gelir (S bazı bilgileri kaybedecektir).
  3. Herhangi bir işlevsel bağımlılığı azaltmak, S'nin içeriğini değiştirecektir.

Bu özelliklere sahip işlevsel bağımlılık kümeleri de denir kanonik veya en az. Girdi olarak sağlanan bazı S 'giriş kümelerine eşdeğer olan işlevsel bağımlılıkların bu tür bir S kümesinin bulunması, bulma olarak adlandırılır. minimal kapak S ': bu problem polinom zamanda çözülebilir.[9]

Ayrıca bakınız

Referanslar

  1. ^ Terry Halpin (2008). Bilgi Modelleme ve İlişkisel Veritabanları (2. baskı). Morgan Kaufmann. s. 140. ISBN  978-0-12-373568-3.
  2. ^ Chris Tarihi (2012). Veritabanı Tasarımı ve İlişkisel Teori: Normal Formlar ve Cazın Tümü. O'Reilly Media, Inc. s. 21. ISBN  978-1-4493-2801-6.
  3. ^ a b Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Veritabanı Sistem Kavramları (6. baskı). McGraw-Hill. s. 339. ISBN  978-0-07-352332-3.
  4. ^ a b M. Y. Vardi. Bağımlılık teorisinin temelleri. E. Borger, editör, Trends in TheoreticalComputer Science, sayfa 171-224. Computer Science Press, Rockville, MD, 1987. ISBN  0881750840
  5. ^ Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995), Veritabanlarının Temelleri, Addison-Wesley, s.164–168, ISBN  0-201-53771-0
  6. ^ Hector Garcia-Molina; Jeffrey D. Ullman; Jennifer Widom (2009). Veritabanı sistemleri: tam kitap (2. baskı). Pearson Prentice Hall. s. 73. ISBN  978-0-13-187325-4.
  7. ^ S. K. Singh (2009) [2006]. Veritabanı Sistemleri: Kavramlar, Tasarım ve Uygulamalar. Pearson Education Hindistan. s. 323. ISBN  978-81-7758-567-4.
  8. ^ Heath, I.J. (1971). "İlişkisel bir veri tabanında kabul edilemez dosya işlemleri". 1971 ACM SIGFIDET (şimdi SIGMOD) Veri Tanımı, Erişim ve Kontrol Çalıştayı Bildirileri - SIGFIDET '71. s. 19–33. doi:10.1145/1734714.1734717. Atıf:
  9. ^ Meier Daniel (1980). "İlişkisel veritabanı modelinde asgari kapsam". ACM Dergisi. doi:10.1145/322217.322223.kapalı erişim

Dış bağlantılar