Federations of RDF data sources provide great potential when queried for answers and insights that cannot be obtained from one data source alone. A challenge for planning the execution of queries over such a federation is that the federation may be heterogeneous in terms of the types of data access interfaces provided by the federation members. This challenge has not received much attention in the literature. This paper provides a solid formal foundation for future approaches that aim to address this challenge. Our main conceptual contribution is a formal language for representing query execution plans; additionally, we identify a fragment of this language that can be used to capture the result of selecting relevant data sources for different parts of a given query. As technical contributions, we show that this fragment is more expressive than what is supported by existing source selection approaches, which effectively highlights an inherent limitation of these approaches. Moreover, we show that the source selection problem is NP-hard and in σP2, and we provide an extensive set of rewriting rules that can be used as a basis for query optimization.

Due to the OPTIONAL operator, the core fragment of the SPARQL query language is non-monotonic.That is, some solutions of a query result can be returned to the user only after having consulted all relevant parts of the queried dataset(s).This property presents an obstacle when developing query execution approaches that aim to reduce responses times rather than the overall query execution times.Reducing the response times-i.e., returning as many solutions as early as possibleis important in particular in Web-based client-server query processing scenarios in which network latencies dominate query execution times.Such scenarios are typical in the context of integration of Web data sources where a data integration component executes queries over a decentralized federation of such data sources.In this paper we introduce an alternative operator that is similar in spirit to OPTIONAL but without causing non-monotonicity.We show fundamental properties of this operator and observe that the downside of achieving the desired monotonicity property is a potentially significant increase in query result sizes.We study the extend of this trade-off in practice.Thereafter,

This paper provides an overview of a model for capturing properties of client-server-based query computation setups. This model can be used to formally analyze different combinations of client and server capabilities, and compare them in terms of various fine-grain complexity measures. While the motivations and the focus of the presented work are related to querying the Semantic Web, the main concepts of the model are general enough to be applied in other contexts as well.

GraphQL is a recently proposed, and increasingly adopted, conceptual framework for providing a new type of data access interface on the Web. The framework includes a new graph query language whose semantics has been specified informally only. This has prevented the formal study of the main properties of the language. We embark on the formalization and study of GraphQL. To this end, we first formalize the semantics of GraphQL queries based on a labeled-graph data model. Thereafter, we analyze the language and show that it admits really efficient evaluation methods. In particular, we prove that the complexity of the GraphQL evaluation problem is NL-complete. Moreover, we show that the enumeration problem can be solved with constant delay. This implies that a server can answer a GraphQL query and send the response byte-by-byte while spending just a constant amount of time between every byte sent. Despite these positive results, we prove that the size of a GraphQL response might be prohibitively large for an internet scenario. We present experiments showing that current practical implementations suffer from this issue. We provide a solution to cope with this problem by showing that the total size of a GraphQL response can be computed in polynomial time. Our results on polynomial-time size computation plus the constant-delay enumeration can help developers to provide more robust GraphQL interfaces on the Web.

Recent advances in Linked Data Management and the Semantic Web have led to a rapid increase in both the quantity as well as the variety of Web applications that rely on the SPARQL interface to query RDF data. Thus, RDF data management systems are increasingly exposed to workloads that are far more diverse and dynamic than what these systems were designed to handle. The problem is that existing systems rely on a workload-oblivious physical representation that has a fixed schema, which is not suitable for diverse and dynamic workloads. To address these issues, we propose a physical representation that is schemaless. The resulting flexibility enables an RDF dataset to be clustered based purely on the workload, which is key to achieving good performance through optimized I/O and cache utilization. Consequently, given a workload, we develop techniques to compute a good clustering of the database. We also design a new query evaluation model, namely, schemaless-evaluation that leverages this workload-aware clustering of the database whereby, with high probability, each tuple in the result set of a query is expected to be contained in at most one cluster. Our query evaluation model exploits this property to achieve better performance while ensuring fast generation of query plans without being hindered by the lack of a fixed physical schema.

The publication of Linked Open Data on the Web has gained tremendous momentum over the last six years. As a consequence, we currently witness the emergence of a new research area that focuses on an online execution of Linked Data queries; i.e., declarative queries that range over Web data that is made available using the Linked Data publishing principles. These principles only require Web servers that respond to simple requests for data about given entities. Therefore, in contrast to approaches for querying a more traditional distributed database, Linked Data query processing approaches cannot assume that data sources provide query processing functionality. Additional challenges are the unbounded nature of the Web and the lack of a complete, up-to-date database catalog that lists all data sources. Our tutorial provides an overview of the new area of Linked Data query processing. We introduce the foundations of Linked Data queries, discuss the specific challenges that need to be addressed, and review techniques for executing such queries.

The World Wide Web (WWW) currently evolves into a Web of Linked Data where content providers publish and link their data as they have done with hypertext for the last 20 years. We understand this emerging dataspace as a huge, distributed database which is -at best- partially known to query execution systems. To tap the full potential of the Web, such a system must be able to answer a query using data from initially unknown data sources. For this purpose, traditional query execution paradigms are unsuitable because those assume a fixed set of potentially relevant data sources beforehand.

In the past two years, the amount of data published in RDF and following the Linked Data principles has increased dramatically. Everyday people are publishing datasets as Linked Data. However, applications that consume Linked Data are not mainstream yet. To overcome this issue, we present a beginners tutorial on consuming Linked Data. We will discuss existing techniques how users can currently consume Linked Data and use it in their current applications.