Optimization of SPARQL queries using artificial intelligence techniques
Yapay zeka teknikleri kullanılarak SPARQL sorgularının optimizasyonu
- Tez No: 328374
- Danışmanlar: YRD. DOÇ. DR. DERYA BİRANT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: İngilizce
- Üniversite: Dokuz Eylül Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 109
Özet
Bugün internetteki oldukça yüksek miktardaki veriyi yönetmek ve yapılandırmak önemli bir problemdir. Anlamsal Ağ yoğun miktarda veriyi yapılandırmak ve yönetmek için önerilmiş bir paradigmadır. Bununla beraber Anlamsal Ağ olgun bir paradigma değildir ve çözülmesi gereken sorunları vardır. Anlamsal Ağ'ın önemli zorluklarından biri sorguların çalıştırılma zamanını azaltmaktır. Sorguların çalışma zamanını azaltmaya yönelik bir yaklaşım üçlü desenlerini yeniden sıralamaktır.Bu çalışmada SPARQL sorgularını üçlü desenleri yeniden sıralayarak iyileştirmek için bir Karınca Kolonisi Eniyilemesi yaklaşımı sunulmuştur. Karınca Kolonisi Eniyilemesi algoritmaları olan Karınca Sistemi, Elitist Karınca Sistemi ve Max-Min Karınca Sistemi algoritmaları gerçekleştirilmiştir. Bu önerilen yeni yaklaşım ARQ sorgu motoru kullanılarak gerçekleştirilmiştir ve bellekteki ontoloji modellerini sorgulayan sorguları iyileştirmektedir.Sorgular, düğümleri üçlü desenleri temsil eden, kenarları ise birleştirme (join) maliyetini temsil eden tam çizge şeklinde soyutlanmıştır. KKE için kullanılan yapay karıncalar bu tam çizgeyi dolaşmaktadır. Karıncaların sonraki düğümü seçmesinde etkili olan geçiş kuralı, üçlü desenlerinin (sonraki düğüm adayları) seçiciliği göz önünde bulundurularak oluşturulmuştur. Üçlü desenlerinin seçiciliğini tahminlemek amacıyla; kesin boyut bilgisi sağlayan GSH, üçlü desen bileşenlerini derecelendirmeye dayanan ?Variable Counting? ve zincir, zincir-yıldız sorgularının başarımını arttırmak için değiştirilen ?Modified Variable Counting? kullanılmıştır.Önerilen yaklaşımlar LUBM (162.871 üçlü içerir.) ve Factbook (95.813 üçlü içerir.) olmak üzere iki farklı ontolojinin zincir, yıldız, döngüsel, zincir-döngüsel, vb. gibi çeşitli yapıdaki sorgularla sorgulanmasıyla sınanmıştır.Bu çalışmanın katkıları daha düşük bir çalışma zamanı için Karınca Kolonisi Eniyilemesi algoritmaları kullanılarak SPARQL sorgularındaki üçlü desenlerinin sıralamasının iyileştirilmesi ve önceden herhangi bir alan bilgisine ihtiyaç duymadan gerçek zamanlı eniyileştirmedir. Deneyler önerilen yaklaşımın eniyilenmiş sorguların çalışma zamanını önemli ölçüde azalttığını göstermektedir.
Özet (Çeviri)
Today, configuring and controlling the overwhelming volumes of information on the web is an important problem. Semantic web is a paradigm that is proposed for solving this important problem. Still, semantic web can't be counted as a mature paradigm and it contains some issues that must be dealt. One important challenge in semantic web is decreasing execution times of queries. An approach for decreasing execution times of queries is reordering triple patterns.In this study, an Ant Colony Optimization approach for optimizing SPARQL queries is proposed. Different Ant Colony Optimization Meta-heuristic algorithms - Ant System, Elitist Ant system and Max-Min Ant System - are implemented based on this approach. This proposed novel optimization method is implemented using ARQ query engine and it optimizes the queries for in-memory models of ontologies.Queries are abstracted as a complete graph whose nodes represent triple patterns and whose edges represent join costs. Artifical ants that are used in ACO algorithms traverse this graph. Transition rule which effects the decision of ants for choosing the next node is provided by considering selectivity of triple patterns (candidates of the next node). In order to estimate selectivity of triple patterns, GSH which provides accurate size information, Variable Counting which is based on ranking triple pattern components and Modified Variable Counting which modified to improve the performance of chain and chain-star queries, are used.Proposed approach is examined by querying two different ontologies LUBM (includes 162.871 triples) and Factbook (includes 95.813 triples) with various structures of queries like chain, star, cyclic, chain-star, chain-cyclic, etc.Contributions of the proposed approach are optimizing order of triple patterns in SPARQL queries using ant colony optimization for lesser and nearly optimal execution time and real time optimization without requiring any prior domain knowledge. Experiments show that proposed methods reduce execution time of queries considerable.
Benzer Tezler
- Dağıtık bağlı veri sorgulama motorlarında performans yönetimi
Performance management in federated linked data query engines
BURAK YÖNYÜL
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. RIZA CENK ERDUR
- Bağlı veri üzerinde dağıtık sorgulama optimizasyonu
Federated query optimization on linked data
ETHEM CEM ÖZKAN
Yüksek Lisans
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERDOĞAN DOĞDU
- Optimization methods for large-scale distributed query processing on linked data
Büyük ölçekli dağıtık bağlı veri üzerinde sorgu işleme için eniyileme yöntemleri
DAMLA OĞUZ
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BELGİN ERGENÇ BOSTANOĞLU
PROF. DR. ABDELKADER HAMEURLAIN
- Dağıtık bağlı verilerde sorgulama yönetimi
Querying management of distributed linked data
ZİYA AKAR
Yüksek Lisans
Türkçe
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. OĞUZ DİKENELLİ
- Optimization of hazelnut roasting process by using response surface methodology
Fındık kavurma işleminin yüzey tepki yöntemi kullanılarak optimizasyonu
SENA SAKLAR
Doktora
İngilizce
1999
Gıda MühendisliğiOrta Doğu Teknik ÜniversitesiGıda Mühendisliği Ana Bilim Dalı
PROF. DR. SUAT UNGAN