Path index selection for XML

Abstract

VI ÖZET XML İÇİN PATH INDEX SEÇİMİ XML (extensible Markup Language) teknolojisi, yarı yapısal doküman temsili ve veri alışverişinde standart haline gelmiştir. XML dokümanları veri saklama ve sorgulama için çok yaygın bir şekilde kullanılmaktadır. XML dokümanlarına erişimde indexleme performansı arttırır. Bu yüzden XML için indexleme konusunda çok derin araştırmalar yapılmış ve bir çok index tipi önerilmiştir. XML dokümanları graf yapısıyla ifade edilebilirler ve grafın üzerindeki yollar için de path index en uygun index yapılarından birisidir. Path index XML dokümanları için çok önemli ve çok yaygın bir index tipidir. Hard disk yeri limiti nedeniyle graf üzerindeki her yol için path index tutamayiz. Bu yüzden elimizdeki hard disk kısırına uygun ve veriye erişim maliyetini en düşük seviyeye indirecek şekilde olası path index kümesinin en uygun alt kümesini seçmek zorundayız. Hard disk kısıtı hesaba katıldığında kullanılacak indexleri sadece bir sorguyu düşünerek belirlemek yanlış olacaktır. Bu yüzden hard disk kısıtı sınırlarında maliyeti en düşük seviyeye getirecek index alt kümesini tüm sorguları hesaba katarak bulacak genel bir optimizasyon algoritmasına ihtiyaç duyulmaktadir. Bu probleme path index seçimi problemi denmektedir ve bu problem NP zorluğunda bir problemdir. Bu tez çalışmasında logaritmik zamanda, kullanıcının belirleyeceği bir hata payıyla, bu problem için yaklaşık optimal sonuç bulan bir metod sunacağız.

ABSTRACT PATH INDEX SELECTION FOR XML XML (extensible Markup Language) has become a standard for semi-structured document representation and data exchange. There is a large amount of XML documents being used for data storage and retrieval. In accessing XML documents indexing increases the p erformance. T hus i ndexing X ML d ocuments h ave b een e xtensively r esearched a nd various index types have been proposed. The elements of an XML document can be represented by a graph and path indexes are created on the paths of the graph. Path index is an important and commonly used index type for XML documents. It has been used in important projects. Because of the secondary storage space constraint, we cannot create a path index for every path. Thus we need to select a subset of the possible set of the indexes which will fit into the allocated secondary space and which will minimize the cost of processing access operations on the XML document. Because of the storage space constraint, it may not be possible to select locally the subset of indexes, which will minimize the cost of processing. That's why there is a need for a global optimization algorithm, which will specify the indexes that will minimize the cost within the storage space constraint. This problem is called the path index selection problem. It is a NP hard problem. In this dissertation, we will present a method which gives an approximately optimal solution within a user specified error bound in a logarithmic time order.