CLASSIFICATION OF SPARQL QUERIES INTO EQUIVALENCE CLASSES OF RELEVANT QUERIES.

This paper is inspired by ideas from the field of theoretical Mathematics, used for the partitioning of abstract spaces into equivalence classes, and applies analogous concepts in order to propose a classification of SPARQL queries into equivalence classes. The novel concepts of relevant queries and covering query are introduced in a manner appropriate for the study of SPARQL queries. These new definitions shed new light on the relations among SPARQL queries. They enable the formal identification of similar queries and this leads to the partition of SPARQL queries into equivalence classes of relevant queries. This work also discusses how the covering query relating two or more relevant queries can be useful from the perspective of computational cost when evaluating composite queries composed of simpler relevant queries. Hence, the introduction of the concept of relevance between queries provides not only obvious theoretical advantages, but also concrete practical ones, which in many cases have the potential to lower the computational cost of query evaluation. [ABSTRACT FROM AUTHOR]