Tez No	İndirme	Tez Künye	Durumu
50500		Partial query evaluation for vertically partitioned signature files in very large unformatten databases / Çok büyük kalıpsız veri tabanlarında dikey dilimlenmiş imza kütükleri ile kısmi sorgu hesabı Yazar:SEYİT KOÇBERBER Danışman: DOÇ.DR. FAZLI CAN Yer Bilgisi: Boğaziçi Üniversitesi / Fen Bilimleri Enstitüsü Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Dosya erişimi = File access ; Sorgulama dili = Query lanquage ; Veri tabanı = Database ; İmza = Signature	Onaylandı Doktora İngilizce 1996 152 s.
ÖZET ÇOK BÜYÜK KALIPSIZ VERİTABANLARINDA DİKEY DİLİMLENMİŞ İMZA KÜTÜKLERİ İLE KISMİ SORGU HESABI Seyit KOÇBERBER Bilgisayar ve Enformatik Mühendisliği Doktora Tez Yöneticisi: Doçent Dr. Fazlı CAN Ocak 1996, 131 Sayfa İmza kütükleri sorgulara uygun olmayan kayıtların çoğunu eleyerek kalıplı ve kalıpsız bilgi kütüklerine randımanlı bir şekilde erişimi sağlar. İkil Dilimlenmiş İmza Kütükleri (İDİK) yöntemi okunacak ve işlenecek bilgi miktarını azaltarak randımanı daha da artırır. Fakat, artan sorgu sözcüklerinin daha fazla ikil dilim işlenmesini gerektirmesi İDİK yönteminin sorguya yanıt süresini artırır. Tez kapsamında, İDİK yöntemi için sorgu hesabının imza kütüğü işleme safhasını sorgu imzasının bütün "1" ikillerini kullanmadan tamamlamaya çalışan bir durma koşulu tanımlandı. Durma koşulunun amacı, beklenen yanlışlıkla uyan kayıt sayısını ikil dilimlenmiş imza kütükleri için en düşük yanıt süresini sağlayacak düzeye indirmektir. Bu kısmi hesap stratejisini kullanan Kısmi hesaplanan İkil Dilimlenmiş İmza Kütükleri (K- İDİK) yöntemi önerildi. K-İDİK durma koşulu ile birlikte çok sözcüklü sorgu ortamlarında farklı sayıda sözcük içeren sorguların sunulma olasılıklarını da gözleyerek sorgu yanıt süresini enküçük düzeyine indirir. Deneyler K-İDİK' in kullanılan disk alanı ve sorgu sözcük sayısına bağlı olarak İDİK' e göre yanıt süresinde yüzde 85 iyileşme sağladığını göstermektedir. Çok sözcüklü sorgu ortamlarında imza kütüğü parametrelerinin daha da eniyileştirilmesini sağlamak için, K-İDİK yönteminin geliştirilmişi olan, Çok Kısımlı İmza Kütüğü (ÇKİK) yöntemi önerildi. ÇKİK yöteminde kısmi hesap stratejisini kullanarak yanıt süresini eniyileştirmek amacıyla imza kütüğü herbiri farklı "1" yoğunluğuna sahip değişik büyüklükte dikey kısımlara ayrılmıştır. Sorgu hesabında vııdüşük "1" yoğunluklu kısımlara ait sorgu imzası "1" leri öncelikle kullanılır. Sorgulardaki sözcük sayısı artarken düşük "1" yoğunluğuna sahip kısımlarda bulunan sorgu imzası "1" lerinin sayısı da artar. Böylece durma koşuluna daha az hesaplama adımı ile erişilir ve dolayısıyla artan sorgu sözcük sayısı için ÇKİK'in sorgu yanıt süresi azalır. Analizler ek bir disk alanı gerektirmeden ÇKİK'in K-İDİK ve genellenmiş çerçeve dilimli imza kütüğü yöntemlerinden daha iyi sonuçlar verdiğini göstermektedir. İmza üretiminde kullanılan, sözcüklerden rasgele ikil konumu elde etme ve üst üste bindirme işlemleri nedeniyle sorguya uygun olmayan bir kaydın imzası sorgu imzasına uygun olabilmektedir. Bu türden kayıtlara yanlışlıkla uyan kayıt denir. İstenir bir yanıt süresi elde edebilmek için yanlışlıkla uyan kayıtların sayısının doğru kestirimi gereklidir. Değişken sayıda farklı sözcük içeren kayıtlardan oluşan veritabanlannda ortalama farklı sözcük sayısı kullanmak yerine yanlışlıkla uyan kayıtların sayısını daha doğru kestiren bir yöntem önerildi. Önerilen yöntemde veritabanmdaki kayıtlar içerdikleri farklı sözcük sayılarına göre kavramsal kısımlara ayrılır ve her kısımdaki yanlışlıkla uyan kayıt sayısı ayrı ayrı kestirilir. Gerçek veri ile yapılan deneylerde kullanılan disk alanına bağlı olarak sıradan erişimli, genellenmiş çerçeve dilimli ve ÇKİK yöntemleri için yüzde 33'e, yüzde 25'e ve yüzde 20'ye kadar varan sorgu yanıt süresi iyileştirmeleri elde edilmiştir. Çok büyük veritabanlannda ÇKİK'in bir ikil dilimi bile birçok disk bloğunu kapsayabilmektedir. ÇKİK'in ikil dilimlerini daha yoğun olarak saklayan Sıkıştırılmış Çok Kısımlı İmza Kütüğü (S-ÇKİK) yöntemi önerildi. ÇKİK'in seyrek "1" içeren ikil dilimlerinin sıkıştırılması daha düşük sorgu yanıt süreleri sağlamaktadır. Disk erişim sayısını eniyileştirmek için disk blok büyüklüğü ikil dilimlerin çoğunun sıkıştırma işleminden sonra bir disk bloğuna sığmasını sağlayacak biçimde ayarlanabilir. Böyle ortamlarda S-ÇKİK ikiden fazla terim içeren sorgulan sözcük başına bir disk erişimi ile hesaplayabilmektedir. Aynı ortamlarda tersyüz edilmiş kütükler ise biri sorgu sözcüğünü aramak diğeri de sorgu sözcüğüne ait kayıt listesine erişmek için olmak üzere ild disk erişimine gereksinim duymaktadır. Açar Sözcükler: Bilgi Erişimi, İmza Kütükleri, Dikey Kısımlanmış İmza Kütükleri, Sıkıştırma. vııı
ABSTRACT PARTIAL QUERY EVALUATION FOR VERTICALLY PARTITIONED SIGNATURE FILES IN VERY LARGE UNFORMATTED DATABASES Seyit KOÇBERBER Ph.D. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Dr. Fazlı CAN January 1996, 131 Pages Signature file approach is a well-known indexing technique. The Bit Sliced Signature File (BSSF) method provides an efficient retrieval environment by only accessing on-bits of query signatures. However, its response time increases for increasing number of query terms. For BSSF we define a stopping condition that tries to avoid the processing of all on-bits of query signatures through partial evaluation. The aim of the stopping condition is to reduce the expected number of false drops to the level that also provides the lowest response time within the framework of BSSF. We propose the Partially evaluated Bit-Sliced Signature File (P-BSSF) method that employs the partial evaluation strategy and minimizes the response time in a multi-term query environment by considering the submission probabilities of the queries with different number of terms. Experiments show that P- BSSF provides 85% improvement in response time over BSSF depending on space overhead and the number of query terms. To provide better optimization of the signature file parameters in multi-term query environments, we propose Multi-Fragmented Signature File (MFSF) method as an extension of P-BSSF. In MFSF, a signature file is divided into variable sized vertical fragments with different on-bit densities to optimize the response time using a similar query evaluation methodology. In query evaluation the query signature on-düşük "1" yoğunluklu kısımlara ait sorgu imzası "1" leri öncelikle kullanılır. Sorgulardaki sözcük sayısı artarken düşük "1" yoğunluğuna sahip kısımlarda bulunan sorgu imzası "1" lerinin sayısı da artar. Böylece durma koşuluna daha az hesaplama adımı ile erişilir ve dolayısıyla artan sorgu sözcük sayısı için ÇKİK'in sorgu yanıt süresi azalır. Analizler ek bir disk alanı gerektirmeden ÇKİK'in K-İDİK ve genellenmiş çerçeve dilimli imza kütüğü yöntemlerinden daha iyi sonuçlar verdiğini göstermektedir. İmza üretiminde kullanılan, sözcüklerden rasgele ikil konumu elde etme ve üst üste bindirme işlemleri nedeniyle sorguya uygun olmayan bir kaydın imzası sorgu imzasına uygun olabilmektedir. Bu türden kayıtlara yanlışlıkla uyan kayıt denir. İstenir bir yanıt süresi elde edebilmek için yanlışlıkla uyan kayıtların sayısının doğru kestirimi gereklidir. Değişken sayıda farklı sözcük içeren kayıtlardan oluşan veritabanlannda ortalama farklı sözcük sayısı kullanmak yerine yanlışlıkla uyan kayıtların sayısını daha doğru kestiren bir yöntem önerildi. Önerilen yöntemde veritabanmdaki kayıtlar içerdikleri farklı sözcük sayılarına göre kavramsal kısımlara ayrılır ve her kısımdaki yanlışlıkla uyan kayıt sayısı ayrı ayrı kestirilir. Gerçek veri ile yapılan deneylerde kullanılan disk alanına bağlı olarak sıradan erişimli, genellenmiş çerçeve dilimli ve ÇKİK yöntemleri için yüzde 33'e, yüzde 25'e ve yüzde 20'ye kadar varan sorgu yanıt süresi iyileştirmeleri elde edilmiştir. Çok büyük veritabanlannda ÇKİK'in bir ikil dilimi bile birçok disk bloğunu kapsayabilmektedir. ÇKİK'in ikil dilimlerini daha yoğun olarak saklayan Sıkıştırılmış Çok Kısımlı İmza Kütüğü (S-ÇKİK) yöntemi önerildi. ÇKİK'in seyrek "1" içeren ikil dilimlerinin sıkıştırılması daha düşük sorgu yanıt süreleri sağlamaktadır. Disk erişim sayısını eniyileştirmek için disk blok büyüklüğü ikil dilimlerin çoğunun sıkıştırma işleminden sonra bir disk bloğuna sığmasını sağlayacak biçimde ayarlanabilir. Böyle ortamlarda S-ÇKİK ikiden fazla terim içeren sorgulan sözcük başına bir disk erişimi ile hesaplayabilmektedir. Aynı ortamlarda tersyüz edilmiş kütükler ise biri sorgu sözcüğünü aramak diğeri de sorgu sözcüğüne ait kayıt listesine erişmek için olmak üzere ild disk erişimine gereksinim duymaktadır. Açar Sözcükler: Bilgi Erişimi, İmza Kütükleri, Dikey Kısımlanmış İmza Kütükleri, Sıkıştırma. vııı