• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)SearchMenu

Development of an Algorithm for Optimizing N3 RDF Language Requests on Ontology-Based Graph Database in the Context of Comindware Business Application Platform

Student: Evgeniya Sukhodolskaya

Supervisor: Sergei Obiedkov

Faculty: Faculty of Computer Science

Educational Programme: Applied Mathematics and Information Science (Bachelor)

Final Grade: 10

Year of Graduation: 2019

In recent years there has been a steady growth in popularity of Business Process Management Systems (BPMs) using graph databases. Popularity increase leads to higher volumes of data being processed. Consequently, the query execution time increases. Thus, algorithms for optimizing queries that would lead to a faster execution time is vital. The goal of this paper was the development of an algorithm for optimizing Notation3 RDF queries to ontology graph database Comindware Elastic Data. The first task was to analyze current methods of graph database query optimization. Afterward, it was necessary to adapt those methods for the specificity of the Comindware Elastic data database. Then those methods must have been applied to a real-world database and a comparative analysis had to be conducted. Only 2 methods were chosen after the research was conducted. The first method is, in fact, a greedy algorithm, based on heuristics that minimize the selectivity of a base graph template. The second method is using a structure called “hierarchical characteristic” for calculating selectivity of a base graph template, which leads to minimization as well. After adapting those algorithms to the specificity of the database at hand and testing the methods against a real-world database the algorithm based on “hierarchical characteristics”, while calculating slower than the greedy algorithm, leads to significantly better results in terms of reducing the query execution time. This paper can lead to the development of a module in the Comindware Business Application Platform for query optimization.

Full text (added May 20, 2019)

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses