Browsing by Author "Kostylev, Egor V."

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Complexity of answering counting aggregate queries over DL-Lite
    (2015) Kostylev, Egor V.; Reutter de la Maza, Juan
  • No Thumbnail Available
    Item
    Construct queries in SPARQL
    (2015) Kostylev, Egor V.; Reutter, Juan L.; Ugarte, Martín
    SPARQL has become the most popular language for querying RDF datasets, the standard data model for representing information in the Web. This query language has received a good deal of attention in the last few years: two versions of W3C standards have been issued, several SPARQL query engines have been deployed, and important theoretical foundations have been laid. However, many fundamental aspects of SPARQL queries are not yet fully understood. To this end, it is crucial to understand the correspondence between SPARQL and well-developed frameworks like relational algebra or first order logic. But one of the main obstacles on the way to such understanding is the fact that the well-studied fragments of SPARQL do not produce RDF as output. In this paper we embark on the study of SPARQL CONSTRUCT queries, that is, queries which output RDF graphs. This class of queries takes rightful place in the standards and implementations, but contrary to SELECT queries, it has not yet attracted a worth-while theoretical research. Under this framework we are able to establish a strong connection between SPARQL and well-known logical and database formalisms. In particular, the fragment which does not allow for blank nodes in output templates corresponds to first order queries, its well-designed sub-fragment corresponds to positive first order queries, and the general language can be re-stated as a data exchange setting. These correspondences allow us to conclude that the general language is not composable, but the aforementioned blank-free fragments are. Finally, we enrich SPARQL with a recursion operator and establish fundamental properties of this extension
  • Thumbnail Image
    Item
    Containment of queries for graphs with data
    (2018) Kostylev, Egor V.; Reutter de la Maza, Juan; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    Static analysis of navigational XPath over graph databases
    (2016) Kostylev, Egor V.; Reutter de la Maza, Juan; Vrgoc, Domagoj
  • No Thumbnail Available
    Item
    Xpath for DL-Lite ontologies
    (2014) Kostylev, Egor V.; Reutter, Juan L.; Domagoj, Vrogc
    Applications of description logics (DLs) such as OWL 2 and ontologybased data access (OBDA) require understanding of how to pose database queries over DL knowledge bases. While there have been many studies regarding traditional relational query formalisms such as conjunctive queries and their extensions, little attention has been paid to graph database queries, despite the fact that graph databases share the structure of interpretations with DLs; that is they describe essentially the same objects. In particular, not much is known about the interplay between DLs and XPath. The last is a powerful formalism for querying semistructured data: it is in the core of most practical query languages for XML trees, and it is also gaining popularity in theory and practice of graph databases. In this paper we make a step towards coupling knowledge bases and graph databases by studying how to answer powerful XPath-style queries over DL-Lite.We start with adapting the definition of XPath to the DL context, and then proceed to study the complexity of evaluating XPath queries over knowledge bases. Results show that, while query answering is undecidable for the full XPath, by carefully tuning the amount of negation allowed in the queries we can arrive to XPath fragments that have a potential to be used in practical applications