Optimization of SPARQL queries using artificial intelligence techniques

Abstract

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._x000B_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._x000B_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._x000B_Ö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._x000B_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. 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._x000B_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._x000B_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._x000B_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._x000B_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.