Graf (çizge) kavramı aslında temel olarak matematik biliminden çıkmış olsa da yazılım dünyasında gerek bilerek gerekse bilmeyerek hemen hergün kullandığımız bir konudur. Bu yazımda temel graflardan bahsederek grafların bilgisayar programlamasında bir ilişkisel veritabanı kullanarak nasıl tutulabileceği hakkında bilgi vermeyi düşünüyorum. Zamanında programlama ve veri yapıları çalışırken bir tane blog yazısına denk gelmiştim. Yazıda yazarın bir cümlesi beni hem düşündürüp hem de bir gülümseme hissi yaratmıştı ki cümleyi her zaman hatırlarım.
Graflar önemlidir. Eğer grafların zaten önemli olduğunu düşünüyorsanız, size tekrar düşünmenizi tavsiye ederim, keza graflar düşündüğünüzden daha önemlidir.
Öncelikle graf yapısına bir göz atalım
Graf (Çizge)
Bilindiği gibi graflar temel olarak matematik konusu olarak değerlendirilen, belirli problemlerin örneklenmesi ve çözümünde yoğun bir şekilde kullanılan yapılardır.
Grafın tanımı wikipedia üzerinde aşağıdaki şekilde verilmektedir.
(1) Çizge, uçlar ve bu uçları birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Matematik ve bilgisayar biliminde kullanılan kuramı bir toplulukta bulunan nesneler arasındaki ilişkileri modelleyen matematiksel yapıları çizitleri inceler. Bu bağlamda çizit düğümlerden ‘köşeler’ ve bu köşeleri birbirine bağlayan kenarlardan oluşur.
Günlük hayatımızdaki olaylar gibi hemen hemen her konunun graflar tarafından rahatlıkla modellenebilmesinden dolayı graflar disiplinler arası bir konu haline gelmiştir. Aşağıdaki örneklerin ilkinde evlerin arasındaki uzaklık ve birbirlerine bağlantıları, ikincisinde twitter üzerindeki takipleşme yapısını görebiliriz.
(2) Genel olarak graflar, bilgisayar bilimleri, biyoloji, fizik, genetik, matematik, kimyasal yapılar, tarih, iktisat ve dilbilgisi gibi konularda da kullanılmaktadır. Sözü edilen bu alanlara ilişkin problemlerin herbirinde iki nokta arasında bir güzergahın veya somutlaştırılabilir bir bağlantının kurulması söz konusudur.
İlişkisel veri tabanı üzerinde grafların gösterimi birkaç farklı şekilde olmaktadır. Bunlar;
- İlişki matrisi (incidence matrix) (3)
- Komşuluk matrisi (adjacency matrix)(4)
- Kenar listesi (Edge List) (5)
İlişki Matrisi
İlk yaklaşımımız olan ilişki matrisi yönetmi için hafızada bir matris oluşturulur. Tabii ki ben matris diye belirttiğim zaman veri tabanı üzerinde bir tabloya denk gelmektedir. Matrisin satır ve sütunları düğüm ve bağlantıları için kullanılır. Aşağıdaki örneğimizde satırlar düğümler, sütunlar ise bağlantılar için kullanılmaktadır. Bu şekilde bir düğüm ile bağlantının arasındaki ilişki hafızada tutulmuş olur.
Tabloya bakarak,
- a düğümünden 1 numaralı bağlantı çıkış yapıyor
- b düğümüne 1 numaralı bağlantı giriş yapıyor
- c düğümüne 3 numara giriş yapıyor
Bilgilerine ulaşabiliyoruz. Görece olarak zor bir yaklaşım olmasının yanı sıra bağlantılara ait özellikleri tutmak için de ayrıca bir yapı kurmak gerekebilir. Örneğin, a(Ankara) ->b(Bolu) arasında bir yol olduğunu anlayabiliyoruz, ilişkinin yönü için negatif/pozitif sayılar, ilişkinin uzunluğu için sayı değerleri kullanılabilir, fakat bilgi çoğaltıldıkça muhtemelen alternatif bilgi tutma yöntemlerine gitmek gerekecektir.
Komşuluk Matrisi
Bu matris şeklinde ise i x j şeklinde bir matris değil de i x i şeklinde bir matris oluşturuluyor ve hem satırına hem de sütununa grafa ait düğümler ekleniyor. Daha sonra da düğümlerin hangilerinde bir bağlantı varsa o matris elemanında belirtiliyor. Kavramı daha iyi anlamak için aşağıdaki resme bakalım.
Bu matrise bakarak hangi düğümler arasında bağantı olduğunu görmek daha kolay. Örneğin; sütunlarda 2 ile satırlarda 23 arasında bir bağlantı olduğunu görebiliriz. Sadece bu bağlantıyı görmekle kalmayıp bağlantıya bir de anlam yükleyebiliriz. Buradaki örnekde arada kırmızı bir bağlantı var. Bu görmek için de bu matrisin temsil ettiği grafa bakalım
Bu grafı veri tabanında bir tabloya eklerken özellikle grafın i x i büyüklüğünde olduğunu düşünürsek böyle bir tablo oluşturmamız gerekiyor gibi düşünülebilir, fakat zaten arada bağlantı olamayan matris elemanlarını tutmaya gerek yok. O yüzden biraz sadeleştirip sadece bağlantıların listesini tutabiliriz. Bu da bizi en etkin çözümümüze bir adım daha yaklaştırıyor.
Kenar Listesi
Önceki seçeneklerimizi biraz incelediğimizde ilk ikisinin gerek RAM gerekse sabit disk üzerinde fazladan yer kaplayacağını göreceğiz. İkinci seçeneği biraz daha optimize ederek yeni bir seçenek elde ediyoruz. Bu seçenek de “Kenar Listesi (Edge List)” olarak isimlendiriliyor.
(6)
Bildiğimiz gibi database üzerindeki normalizasyon aşamalarını tablolarımıza uyguladığımız zaman, iki tablo arasında bir ilişki varsa bu ilişki için ayrı bir tablo kurmamız önerilir. Temel olarak iki tablo arasında bir ilişki varsa ve bu ilişki için üçüncü bir tablo kullanıyorsak zaten istediğimiz yere gelmiş oluyoruz. Biraz açmak gerekirse aşağıdaki resimde de görüldüğü üzere düğümlerimizi birer tabloda, ilişkilerimizi de başka tablolarda tutmamız durumunda a tablosundaki bir kayıttan c tablosundaki bir kayda ilişki var demiş oluyoruz.
Bu yaklaşım bize hem diskte daha az yer kaplama, hem sorgulama işlemlerinin daha rahat olması gibi kolaylıklar sağlıyor. Ayrıca aradaki bağlantıların (ilişkilerin) tutulduğu tabloya farklı alanlar da eklenerek bağlantıya özgü özellikler de tutulabilir. Örneğin, eğer bir harita tutuyorsak bağlantılarımız yollar olacak. Yolların uzunluğu, genişliği, şerit sayısı, durumu hakkında da bilgiler tutabiliriz. İlk iki seçenekde bu bilgileri çoğaltmak biraz daha zahmetli bir iş olmaktadır.
Sonuç
İlişkisel veri tabanları kullanılarak graf yapılarının oluşturulması zaten programcıların gündelik hayatlarında var. Bazen konunun matematiksel yaklaşımını bilmeden veya jargona hakim olmadan yaptığımız yaklaşım olarak da görüyoruz. İlla ki iki tablo arasında ilişki kuruyoruz veya many-to-many ilişki kurarken araya bir tane ilişki tablosu ekliyoruz.
Konunun teorisine de hakim olmak programcı olarak bizi bir adım öteye götürecektir.
Referanslar
- http://tr.wikipedia.org/wiki/%C3%87izge_kuram%C4%B1
- Prof. Dr. Vasif Vagifoğlu NABIYEV- Algoritmalar, sayfa 299
- http://en.wikipedia.org/wiki/Incidence_matrix
- http://en.wikipedia.org/wiki/Adjacency_matrix
- http://www.sommer.jp/aa10/aa8.pdf
- http://www.slideshare.net/quipo/rdbms-in-the-social-networks-age
- http://gotocon.com/dl/goto-chicago-2014/slides/MaxDeMarzi_AddressingTheBigDataChallengeWithAGraph.pdf
- https://medium.com/t%C3%BCrkiye/graf-teorisine-giri%C5%9F-c90cbdf9564c