Browsing by Author "Gutierrez, Claudio"

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    An extension of SPARQL for RDFS
    (SPRINGER-VERLAG BERLIN, 2008) Arenas, Marcelo; Gutierrez, Claudio; Perez, Jorge; Christophides, V.; Collard, M.; Gutierrez, C.
    RDF Schema (RDFS) extends RDF with a schema vocabulary with a predefined semantics. Evaluating queries which involve this vocabulary is challenging, and there is not yet consensus in the Semantic Web community on how to define a query language for RDFS. In this paper, we introduce a language for querying RDFS data. This language is obtained by extending SPARQL with nested regular expressions that allow to navigate through an RDF graph with RDFS vocabulary. This language is expressive enough to answer SPARQL queries involving RDFS vocabulary, by directly traversing the input graph.
  • No Thumbnail Available
    Item
    nSPARQL: A Navigational Language for RDF
    (SPRINGER-VERLAG BERLIN, 2008) Perez, Jorge; Arenas, Marcelo; Gutierrez, Claudio; Sheth, A.; Staab, S.; Paolucci, M.; Maynard, D.; Finin, T.; Krishnaprasad, T.
    Navigational features have been largely recognized as fundamental for graph database query languages. This fact has motivated several authors to propose RDF query languages with navigational capabilities. In particular, we have argued in a previous paper that nested regular expressions are appropriate to navigate RDF data, and we have proposed the nSPARQL query language for RDF, that uses nested regular expressions as building blocks. In this paper, we study some of the fundamental properties of nSPARQL concerning expressiveness and complexity of evaluation. Regarding expressiveness, we show that nSPARQL is expressive enough to answer queries considering the semantics of the RDFS vocabulary by directly traversing the input graph. We also show that nesting is necessary to obtain this last result, and we study the expressiveness of the combination of nested regular expressions and SPARQL operators. Regarding complexity of evaluation, we prove that the evaluation of a nested regular expression E over an RDF graph G can be computed in time O(vertical bar G vertical bar . vertical bar E vertical bar).
  • No Thumbnail Available
    Item
    On the semantics of SPARQL
    (2009) Arenas Saavedra, Marcelo Alejandro; Gutierrez, Claudio; Pérez Rojas, Jorge Adrián; Virgilio, Roberto de; Giunchiglia, Fausto; Tanca, Letizia
  • Thumbnail Image
    Item
    Querying in the Age of Graph Databases and Knowledge Graphs
    (ASSOC COMPUTING MACHINERY, 2021) Arenas, Marcelo; Gutierrez, Claudio; Sequeda, Juan F.
    Graphs have become the best way we know of representing knowledge. The computing community has investigated and developed the support for managing graphs by means of digital technology. Graph databases and knowledge graphs surface as the most successful solutions to this program. This tutorial will provide a conceptual map of the data management tasks underlying these developments, paying particular attention to data models and query languages for graphs.
  • No Thumbnail Available
    Item
    Querying Semantic Data on the Web
    (ASSOC COMPUTING MACHINERY, 2012) Arenas, Marcelo; Gutierrez, Claudio; Miranker, Daniel P.; Perez, Jorge; Sequeda, Juan F.
  • No Thumbnail Available
    Item
    Semantics and Complexity of SPARQL
    (2009) Perez, Jorge; Arenas, Marcelo; Gutierrez, Claudio
    SPARQL is the standard language for querying RDF data. In this article, we address systematically the formal study of the database aspects of SPARQL, concentrating in its graph pattern matching facility. We provide a compositional semantics for the core part of SPARQL, and study the complexity of the evaluation of several fragments of the language. Among other complexity results, we show that the evaluation of general SPARQL patterns is PSPACE-complete. We identify a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently. This restriction gives rise to the class of well-designed patterns. We show that the evaluation problem is coNP-complete for well-designed patterns. Moreover, we provide several rewriting rules for well-designed patterns whose application may have a considerable impact in the cost of evaluating SPARQL queries.
  • Thumbnail Image
    Item
    Simple and Efficient Minimal RDFS
    (ELSEVIER, 2009) Munoz, Sergio; Perez, Jorge; Gutierrez, Claudio
    The original RDFS language design includes several features that hinder the task of developers and theoreticians. This paper has two main contributions in the direction of simplifying the language. First, it introduces a small fragment which, preserving the normative semantics and the core functionalities, avoids the complexities of the original specification, and captures the main semantic functionalities of RDFS. Second, it introduces a minimalist deduction system over this fragment, which by avoiding certain rare cases, obtains a simple deductive system and a computationally efficient entailment checking. (C) 2009 Elsevier B.V. All rights reserved.