Normalizasyon

Bu yazim da siz degerli okurlarima veritabani normalizasyonu hakkinda bildikleri mi aktarmaya calisacagim :) Fikir babasi Tonguç abi ye ve yazimi yazarken kaynaklarini kullandiğım Turgut Uyar hocama tesekkurlerimi sunuyorum oncelikle:)

Normalizasyonun bilinçli bir şekilde yapılabilmesi için işlevsel bağımlılık kavramının anlaşılması gerekteğinden öncelikle bu konuya değiniyoruz:

İşlevsel bağımlılık:
Z bir kümeyse, A ve B bu kümenin iki alt kümesi ise, A nın her elemanı için B de yalnız ve yalnız bir eleman karşılık düşmesi A nın B yi işlevsel olarak belirlemesi demektir.
Her işlevsel bağımlılık bir bütünlük kısıtlamasıdır çünkü A ve B nin bir arada bulunması anlamlıdır.
İşlevsel bağımlılığı açıklamak için aşağıda ki tabloyu göz önüne alalım:


Tabloda yer alan varsayımı inceleyecek olursak tablo da yer alan COUNTRY ( COU ) alanının LANGUAGE ( LANG ) alanını işlevsel gerektirdiğini görürüz. Bunun sebebi tablonun tasarimini yaparken kabul ettiğimiz koşuldur. Her film çevrildiği ülkenin dilin de çekildiğine göre her ülkeye yalnız bir dil karşılık düşürülmektedir.
Bunun tersi doğru değildir: Her dil e bir ülke karşı düşürülmemiştir örneğin EN ( english ) diline hem UK ( United Kingdom ) hem de US ( Seattle :p ) karşı düşürülmüştür. Bu yüzden LAN COU yu işlevsel gerektiriyor diyemiyoruz.

Açıklayıcı olması için bir örnek daha vermek istiyorum: Tablo da yer alan ACTORID ve NAME alanları birbirlerini karşılıklı işlevsel gerektirmektedirler. Buna göre her ACTORID ye karşılık yalnız bir NAME ve her NAME e karşılık yalnız bir ACTORID vardır.

İşlevsel bağımlılıkların yalnızca birer alan arasında olması diye bir zorunluluk yoktur. Örneğin: MOVIEID ve ACTORID ikisi birlikte ORD ( ORDER ) alanını işlevsel belirler. Burada ORD alanı aktörün filmde ki sırasını belirlemektedir. Bir film de birden fazla aktör olduğundan sadece MOVIEID alanı ORD alanını işlevsel olarak bağlayamaz çünkü böyle olsaydı bir MOVIEID ye karşılık sadece bir ORD alanı olması gerekir ki tabloyu inceleyecek olursak 70 id li movie ye karşılık ORD alanın da 2 farklı değer vardır. Ama MOVIEID ve ACTORID birlikte kullanıldığında tabloda karşılığı olan yalnız 1 ORD değeri olacaktır.

İndirgenemez küme: Bir S bağıntısında ( tablosunda ) yer alan bütün işlevsel bağımlılıkların kümesine T diyelim. T nin özelliği olabildiğince az eleman içermesi ( tabloda ki birbirine bağımlı sütunların mümkün olduğunca az tutulması ) ve S ana kümesinde ki her işlevsel bağımlılığın T kümesinden türetilebilmesidir. ( Yani tabloda ki veri tutarlılığı bütünlüğü bozulmasın).

Normalizasyon:
Burada değinmek istediğim normalizasyon türleri 1NF, 2NF, 3NF ve BCNF dir.
Her NF ( normal form ) bir öncekinin kapsamını daraltmaktadır.

1NF de nitelikler bölünemez. Bütün veriler bir tek tablo da yer alır. Yukarı da şeklini gördüğünüz tablo yapısı 1NF dir, kaydı tutulmak istenen her veri tabloya bir satır olarak girer. 1NF yapısı çoğu zaman tercih edilmez. Bu form da yer alan sorunlara bakarsak:
1) Bir filmin hangi ülkede çekildiğini biliyoruz ama film de oynayan bir oyuncu bilmediğimiz için yukardaki tablomuzda ülke bilgisini de saklayamıyoruz. ( veri ekleme sorunu )
2) Bir film de oynayan bir oyuncuyu silmek istiyoruz ancak tabloda film hakkında verisi olan tek satır bu ise, satır silindiği zaman film hakkında ki diğer bilgilerde kaybolmuş olacak. ( örn: filmin ülkesi, dili .. ) ( veri silme sorunu )
3) Bir kayıdı güncellemek istediğimiz de tabloda bulunan birden fazla kayıdı güncellemek zorunda kalabiliriz. Örneğin bir filmin ülkesi değiştirilmek istenirse, o filme ait kaç satır varsa hepsinde aynı değişikliği yapmamız gerekecek! ( güncelleme sorunu )

Bu sorunları engellemek için 2NF forma geçilebilir. 2NF form da anahtar olmayan her nitelik birincil anahtara bağlı olmak zorundadır:

Yukardaki tablodan inceleyecek olursak:
Ne demiştik; anahtar olmayan alanlar birincil anahtara bağlı olsunlar.
R1 tablosuna bakacak olursak MOVIEID alanı birincil anahtar, TITLE, COU ve LANG alanları birincil anahtara bağlı alanlardır. Burada MOVIED nin birincil anahtar seçilmesinin sebebi tabloda ki bir satırı tek başına temsil edebilmesidir. TITLE alanı birincil anahtar olamazdı çünkü aynı isimde filmler tabloda yer alabilir. Bu yapıda birincil anahtar olmayan alanların bir birincil anahtara bağlanması yeterlidir.
Bu yapı da ayrımı yaparken sadece bakacağımız koşul anahtar olmayan alanların birincil anahtara bağlı olmasıdır. Başka ek birşey yapılmaz. örneğin LANG alanı birincil anahtar dışında COU alanına da bağlıdır ancak bu durum göz ardı edilir.
R3 tablosunda ActorID ve NAME alanları ayrılmıştır ve ACTORID birincil anahtardır. Tablolar arası ilişkiyi kaybetmemek için R4 tablosu oluşturulmuştur. Burada amaç foreign key dediğimiz yapıyla R1 ve R3 tabloları arasında ki ilişkiyi sağlamaktır.

Bu yapının da ekleme silme ve güncelleme sorunları devam etmekdir.

3NF formda ise yapılması gereken şey bir alanın yalnız ve yalnız birincil anahtara bağlı olması başka hiçbir alana bağlı olmaması gereğidir. Bu durumda 2NF de bulunan LAN alanının R1 tablosundan çıkarılması gerekecektir. Çünkü LAN alanı hem MOVIEID hem COU ya bağlı olamaz. Tablonun yeni hali:


BCNF formu ise benim tam incelemediğim bir konudur:) Bilenler varsa comment lerse sevinirim her beraber öğrenmiş oluruz.
Sonra ki yazılarımda görüşmek dileğiyle...

Interviewing with Microsoft ( sde, sdet )

In this post, i write about the interviewing with microsoft. i write this post in english because of internets search results :)
The adventure starts with the sending a resume to hr. Resume should be good enough for passing to next stage. it should clearly identify your skills.
If hr likes your resume, then an email message arrives to your mail box, you feel excited at this stage:) mail tells you, you have a phone call with hr about two days and also they give you to exact date.
You wait until they call you. on the phone, Hr asks you some questions. These are genereally the basic questions for testing your knowledge. You should think a bit then answer the questions. a few questions which they asked to me:
1) how can you define a character pointer named foo
my answer: char * foo; // :))))
2) How can you describe best code
my answer: i dont describe security, easy to read etc. i simply say it should be well documented. because i thought other topics are discussed so much in every where and generally all people knows that a code must be secure or maintanable...


i was asked about 10 questions in the phone, and after 1 week, there was another mail in my inbox:) they said they came to Turkiye and wanted to interview with me face to face. They then sent lots of mail messages for giving info. and sources. i studied lot of things like OS's kernels, low level c , software testing methods etc...
In the interview day, i was a little excited but i pretended to be relax:) i was meeting with 5 people who are testers, developers and hr. it continued about 4.5 hours. they asked me lots of questions. they dont ask only about coding, but also about design. for instances i was asked for designing structures.
code questions are about data structres and algorithms. converting a hexa to decimal, designing a data structures etc.

After a long day, i felt tired and went back to my home, then we were waiting again until they told us the results of interview.
It was a nice day for me, different experience. Also maybe you wonder my result:) i accepted to SDE in USA! now i am waiting the next stages, offer letters another exciting phone call etc..

Let's Make It Faster...

Bu yazimda zaten hızlı olan bir seyi daha hızlı nasıl yapabiliriz onu gostericem :)

1. yol C dilinde asm komutları yazalım.
include

int main(){

int base, power ,result;

printf("us ve power degerleri:");
scanf("%d %d",&base,&power );

asm(
"movl %1, %%ebx\n\t" //base degiskeni ebx saklayıcısında
"movl %2, %%ecx\n\t" //power degiskeni ecx saklayıcısında"
"xorl %%edx, %%edx\n\t" //edx saklayıcısının içeri sıfırlandı çarpma işlemi için.
"movl $1, %%eax\n\t" //sonuc eax saklayıcısında tutulsun, baslangic degeri 1
"back:\n\t"
"cmp $0, %%ecx\n\t" //power == 0 mı ?
"je bitir\n\t" //evet ise dongu biter
"mul %%ebx\n\t" //degil ise base degiskeni ile sonucu carp ve sonuca ata
"decl %%ecx\n\t" //power ı 1 azalt
"jmp back\n" //donguye devam et, back e dallan
"bitir:\n\t" //dongu sonu

:"=a"(result) //result degiskeni eax saklayıcısından programa geri donecek
:"g"(base),"g"(power) //giris parametreleri base ve power degiskenleri
:"%ebx","%ecx","%edx" //asm blogunda degeri degisen saklayıcılar
);

printf("sonuc: %d\n",result);

return 0;
}


Program da goruldugu gibi hiz acisindan kritik olan kod parcasi asm blogu icinde assembly ile yazilmistir. Programci saglamsa cogu zaman derleyicinin urettigi koddan daha hizli olmaktadir:)
ornegin yukarıdaki kodun saf c karsiligi:

#include

int main(){

int base, power ,result;

printf("us ve power degerleri:");
scanf("%d %d",&base,&power );

result = 1;
for( ; power != 0; power--)
result = result * base;

printf("sonuc: %d\n",result);

return 0;
}

Ve bu fonksiyonu derleyip olusan object kodunu reassembler ettigimiz aman karsimiza gelen makine kodu:

lea ecx,[esp+4]
and esp,0xfffffff0
push DWORD PTR [ecx-4]
push ebp
mov ebp,esp
push ecx
sub esp,0x24
mov DWORD PTR [esp],0x0
call 19
lea eax,[ebp-16]
mov DWORD PTR [esp+8],eax
lea eax,[ebp-12]
mov DWORD PTR [esp+4],eax
mov DWORD PTR [esp],0x17
call 33
mov DWORD PTR [ebp-8],0x1
jmp 55
mov edx,DWORD PTR [ebp-12]
mov eax,DWORD PTR [ebp-8]
imul eax,edx
mov DWORD PTR [ebp-8],eax
mov eax,DWORD PTR [ebp-16]
sub eax,0x1
mov DWORD PTR [ebp-16],eax
mov eax,DWORD PTR [ebp-16]
test eax,eax
jne 40
mov eax,DWORD PTR [ebp-8]
mov DWORD PTR [esp+4],eax
mov DWORD PTR [esp],0x1d
call 6b
mov eax,0x0
add esp,0x24
pop ecx
pop ebp
lea esp,[ecx-4]
ret


Görüldüğü gibi makine kodunu benim yazdığım kodla karşılaştırmamız zor, çünkü ben c ve assemblyi karıştırdım, peki benim karıştırılmış kodumun object kodunu reassebler edersem ne görücem:

lea ecx,[esp+4]
and esp,0xfffffff0
push DWORD PTR [ecx-4]
push ebp
mov ebp,esp
push esi
push ebx
push ecx
sub esp,0x1c
mov DWORD PTR [esp],0x0
call 1b
lea eax,[ebp-24]
mov DWORD PTR [esp+8],eax
lea eax,[ebp-20]
mov DWORD PTR [esp+4],eax
mov DWORD PTR [esp],0x17
call 35
mov esi,DWORD PTR [ebp-20]
mov eax,DWORD PTR [ebp-24]
mov ebx,esi
mov ecx,eax
xor edx,edx
mov eax,0x1

0000004a :
cmp ecx,0x0
je 54
mul ebx
dec ecx
jmp 4a

00000054 :
mov DWORD PTR [ebp-16],eax
mov eax,DWORD PTR [ebp-16]
mov DWORD PTR [esp+4],eax
mov DWORD PTR [esp],0x1d
call 66
mov eax,0x0
add esp,0x1c
pop ecx
pop ebx
pop esi
pop ebp
lea esp,[ecx-4]
ret


anlaşılması kolay olsun diye satır numaraları ve byte code ları çıkarıp sadece assembly kodlarını koydum. Bu iki kodu karsilastirirsak gozuken o ki, benim yazdigim kod, derleyicinin urettigi koddan sadece 4 byte daha az :)) derleyicinin kodu 0x7c ye kadar giderken benim yazdığım kod 0x79 a kadar gitti. Aslında daha dikkatli asm bloğu ile bu farkı açabiliriz, ancak benim değinmek istedigim nokta iyi bir programcı daima compiler dan daha iyi kod yazabilir. Tabi bunu gerektirdigi noktalarda kullanmak gerekir. Tutupta butun kodu asm ile yazmak kotu bir yaklasimdir. Cunku bu adress binding dedigimiz, sembollerin adreslere dönüştürme işleminin erken gerçekleşmesine neden olur. Ancak hız kritik ve bellek kapasitesinin az olduğu uygulamalarda yukardaki yaklaşım önemlidir....

2.yol asm içinde C kutuphane fonksiyonlarının çağrılmasıdır. Bu konu ile ilgili örnekleri daha sonra verebilirim talep olursa:) ancak temek fikir ; çağrılacak C fonksiyonları asm kodunda extern olarak belirtilir. Böylece derleyici asm kodunu derlerken hata üretmez ve oluşturduğu object kodunun sembol tablosuna "imported symbol" olarak bu fonksiyon çağrısını ekler. Daha sonra linker da object kodunu C kutuphanesi ile link ederiz ve en son yürütülebilir dosya elimizde oluşur.
C fonksiyonlarını asm içinden çağırmak için gerekli olan bir önemli husus C nin calling conventions dedigimiz çağırma kurallarına uymamızdır. Parametre aktarımı yığın üzerinden olur ve fonksiyona aktarılacak parametreler, parametre listesine gore sagdan sola dogru yığına atılırlar.

Böylece bir yazımında sonuna gelmiş bulunmaktayım. Yeni yeni yazılarla karşınızda olmak dileğiyle şimdilik hoşçakalın :)))

RISC vs CISC revisited

Geçenlerde yazdığım RISC ve CISC ile ilgili bir yazıya gelen yorum su sekildeydi
( yorum sahibinden ozur dilerim bir turlu publish edemedim comment i )
"Peki hangi program icin RISC ve CISC bunu da biraz acabilirmisin??"

Yazımda kullanacağimiz uygulamaya göre işlemci türünü seçmeliyiz demiştim. Peki hangi türlerde hangi işlemci türü faydalı olur? Bunu aşağıdaki kriterlere göre incelemek istiyorum

1) BELLEK GEREKSINIMI
Uygulama bellek uzerinde cok islem yapiyorsa, bellegi yogun olarak kullaniyorsa, yada uygulamanin kendisi bellekte cok yer kapliyorsa ( ki bu sayfalama ya (paging) yol açar ) bu durumda işlemcinin belleğe hızlı erişmesi işlerimizi kolaylaştıracaktır. CISC mimarilerde bellek erişim komutları ve bellek üzerinde işlem yapan komutlar RISC lere göre daha gelişmiştir. Bu yüzden bellek gereksinimi yoğun ise CISC ler seçilebilir.

2) Giriş/Çıkış GEREKSİNİMİ

Bir program yazdık, io istegi cok fazla, dosya işlemleri yapiyor, database güncelliyor, dataware house işlemleri yapıyor, dışardan veri geliyor vs. Bu durumda modern sistemler giriş çıkış işlemini CPU üzerinden değil DMA ( direct memory access ) denetleyicisi kullanarak yaparlar. Daha eski bir tasarım CPU kullanarak kesme ile yapılan aktarımdır ancak bu işlemciyi gereksiz meşgul eder. Bunun yerine DMA denetliyicisi belleği veri aktarırken yada bellekten veri okurken CPU kendi içindeki bellek ile ilgili olmayan işlemlerini yürütebilir. Aslında DMA nın çalışması için iki yöntem vardır bunlar i) çevrim çalma ( cycle stealing ) ve ii ) blok aktarımdır ( block transfer ). DMA ile ilgili ayrıntıları bir başka gün ele alırım inş. Ancak burada değinmek istediğim eğer DMA denetliyicisi veri aktarımı yapıyorken CPU kendi iç işlemlerini gerçekleştirebiliyorsa iç register/saklayıcı sayısının fazla olmasını isteriz. Bu durumda RISC mimari daha uygun gözükmektedir.
Fakat DMA nın olmadığı bir sistem de io işlemi için CPU kullanılacağından bu durumda kesin bir şey söylemek mümkün değildir.

3) Interactive / Batch UYGULAMALAR

Bir uygulamanın interactive yada batch çalışmasına bağlı olması da işlemci seçiminde önemlidir. Mesala interactive uygulamalarda yanıt alma süresi önemlidir. RISC mimariler de pipeline ( iş hattı ) kullanılarak işler hızlandırılmış ve paralel hale getirilmiştir.. Bu yüzden interactive kullanım sadece CPU işleri ile ilgili ise RISC işlemci kullanılabilir. Diğer yandan bellek üzerinde çok işlem yapan türden bir uygulama ise CISC mimarisi daha uygundur.
Batch programlar ise genelde bir giriş e karşılık işlenen veriyi çıkışa aktarma şeklinde yürür. veri üzerinde yapılan işlem bellek kullanmayı gerektirecekse CISC seçilebilir. Diğer yandan CPU işleminin ve io işleminin yoğun olması durumu yüksek olacağından RISC mimari bu durumlar da seçilebilir.

RISC ve CISC lerin seçilmesine yönelik bilgi ve öneriler vermeye çalıştım. Burdaki bilgilerin hepsinin doğru olduğunu savunmuyorum. Aslında hepsi kendi görüşümdür.Kaynak belirtemem. Sonraki yazılarda yine beraber olmak dileğiyle :))