The concept of Linked Data has appeared recently in order to allow publishing data on the Web in a more suitable form enabling automated processing by programs and not only by human users. Linked Data are based primarily on RDF triples, which are also modeled as graph data. Despite the research effort in recent years, several questions in the area of Linked Data indexing and querying remain open, not only since the amount of Linked Data globally available significantly increases each year. Our ongoing research effort should result in a proposal of a new querying system dealing with several disadvantages of the existing approaches identified in our previous work. They are especially related to data scaling, dynamicity and distribution.
⋆ This work was supported by the Charles University Grant Agency grant 4105/2011
and the Czech Science Foundation grant P202/10/0573.
along the data we can also publish RDFS [
In recent years, a significant effort appeared not only in a theoretical research,
but also in the amount of Linked Data globally available. However, we can still
identify several open problems to which attention should be paid. The goal of our
ongoing research effort is to propose a new querying system for Linked Data. In
particular, we want to focus on indexing structures and techniques with respect
to SPARQL [
The aim of this paper is to provide a description of the system we are
attempting to propose. However, in order to understand our motivation, we also
need to discuss the existing approaches from the area of Linked Data indexing
and querying. Their thorough overview was presented in our previous work [
Preliminary ideas of our querying system were first introduced in [
Outline. In Section 2 we present a basic overview of the existing approaches. Section 3 provides the description of the architecture of system we are working on. Finally, Section 4 concludes. 2
The existing approaches can probably be divided into three main categories: local querying systems, distributed querying systems and global searching engines. It is worth noting that even though we want to focus on distributed querying, its models and algorithms, wide range of relevant ideas can be found between approaches for local querying. For simplification, we will use abbreviations S, P , O and C for subject, predicate, object and context respectively.
We start our overview of existing approaches by local querying systems. Index
structures proposed by Harth and Decker [
The core of the stream processor RDF-X by Neumann and Weikum [
BitMat is an approach proposed by Atre et al. [
Udrea et al. [
The last presented local approach is a parameterized index introduced by
Tran and Ladwig [
Now, we move to distributed approaches. Quilitz and Leser [
The purpose of a data summary index by Harth et al. [
The system should provide transparent querying of distributed data – not in the context of the entire Web of Data, but only within a distributed database over which we have a full control. Linked Data are the subject of nontrivial changes in time and, thus, the aspect of the data volatility cannot be ignored in the framework architecture and index structures especially. Many existing approaches bring interesting ideas, but their indexing models only assume environments with static data. Therefore, the core part of our work is to propose an appropriate dynamic index structure. 3.1
The nature of Linked Data assumes that data are distributed within the entire global cloud of the Web of Data. Since completely centralized solutions seem not to precisely follow this idea, we want to find a suitable compromise between centralized and totally distributed approaches. For this purpose we can accept an idea that a distributed database is spread across a set of sources, as we can see in Figure 1 with a sample distributed infrastructure. Each source provides two main features – it is able to store data triples inside its local storages and provides interfaces for querying.
These sources can be viewed only as ordinary services, but we have the full control over sources we want to use in our database – either we own them completely (and decide what data they should store), or, at least, we can decide what independent sources we would like to use (and we accept data they provide). Anyway, submitting a query to a public interface of a particular source, it should transparently decompose the query into its elementary parts, decide which sources should be contacted to obtain relevant data, and, finally, to compose the entire query result. In other words, the user should define data to be used (by building its distributed database), but the query itself should be evaluated automatically without his or her explicit help.
For this purpose, we first need to have a technique for describing capabilities
of individual sources. A promising concept was already introduced by Quilitz
and Leser [
Having defined the way how sources publish information about data they contain, we need to manage sources themselves. So, assume that we have the knowledge of sources we want to use, their locations or other technical details. Now, we must define, which sources (and, in particular, which data) constitute our database. This management seems to be easy, but cannot be omitted. 3.2
Data triples are stored in physical storages. Their role, however, might be a bit different comparing to traditional relational databases or others. The model of RDF triples is so simple that we can store data directly in indices, but as we will see, this still does not mean that physical storages should not be included in the architecture of querying systems. Although triples really are easy to grab, it would be misleading to think that we do not need to handle different data differently. Relational databases allow users to create schemata and explicitly declare how their data should be stored in relational tables. However, we are not offered similar features in existing native approaches for RDF data.
Therefore, we assume that a storage is a component for storing RDF triples, but we do not have any further assumptions on their internal structure or characteristics. The only important is to comply with an agreed public interface. As a consequence, we can work with native storages, we can create wrappers around relational databases, or even to access remote storages via network. In other words, it would be interesting to access local storages within a particular source with the same (or at least very similar) interfaces as we would use between distributed sources during the query evaluation phase. In fact, we indeed need to achieve this behavior, since if we formulate a query on a given source against a particular database, apparently, some data may be available locally and other not – but from the point of the query evaluation process, both these data play the same role. A sample storages configuration can be seen in Figure 2.
The shared idea by the majority of indexing methods is the way of storing string values of URIs and literals, because there is a high probability that strings (or substrings) may have multiple occurrences in the database. Therefore, it is very effective to store these strings only once in a special storage, assign them unique integer identifiers, and use them in RDF triples instead of the original terms. As a consequence, frequently executed value equality tests during the query evaluation may then be executed much faster and the space required for storages decreases as well.
Having a particular domain of our problem, we should know at least something about data and even queries, and, thus, to design our database effectively. We do the same years and years in relational databases, so we should be able to select appropriate storages and indexing structures directly for our situation in RDF approaches, too. This functionality should be one of the core parts of our system. When storing data in a local storage of a source within a given database, users should be encouraged to choose from a palette of implemented approaches, best conforming to their situation.
The main disadvantage of the majority of interesting models for indexing
RDF data is the static nature of indexing structures themselves. We do not
enable working with extremely volatile data, but it is not a good idea to strictly
assume only a static database. Therefore, one of our main goals is to extended
some existing approach [
We have chosen SPARQL as a querying language. Having a query statement, we first need to parse it into an internal representation of a graph pattern. For simplicity, we can assume that this pattern is built from a set of triples, where we can use variables instead of only fixed terms. They may serve for joining individual patterns together, or may only state that we do not care about values of a corresponding triple particle. The latter purpose in fact corresponds to the idea of joining – if we first evaluate each pattern separately, then we need to join intermediate results together – joining only those pairs of triples that have equal values at positions of corresponding variables.
The problem is that our database is distributed between several sources. We
have descriptions of data these sources provide, thus, we need to decide for each
pattern (or even more complicated subqueries), where relevant data are located.
This problem is referred as a source selection. Whereas data summary index by
Harth et al. [
When we have decided which sources contain relevant data, we are still not finished with preparing the query evaluation plan. Data in sources are physically maintained in storages and these storages may have different capabilities to return required data. Thus, during the source selection, we also need to consider these capabilities. And moreover, different indices may be available, too.
If we want to find a suitable query evaluation plan, which is a must, since the complexity of different plans may be significantly different, we have to consider all the following aspects: different sources, storages, indices and different algorithms available for executing operations. The theoretical goal could be to find the optimal plan, but in practice we must settle only for approximations. Usually, we cannot inspect all possible plans, so we have to use only suitable heuristics. Another problem is that we are often forced to use incomplete and only approximate statistics.
The general idea of all optimizations is to avoid processing of irrelevant data wherever possible and to perform all computations effectively. If the existing approaches are not able to directly access only the required data, they at least attempt to prune data using other methods or ideas. For example, we can move data filtering selections as close as possible to their fetching, or we can perform data pruning before the phase of joining. Probably the most important position in query optimization techniques has the join ordering. It is quite interesting that we can use similar ideas to the nested loop algorithm from relational databases. However, there are other aspects that need to be considered, too. 4
In this paper we described the architecture of the querying system we are proposing. Issues related to this architecture can be divided into two groups: data and queries. First, we discussed observations and ideas related to the model of a distributed database spread across a set of selected sources, motivation and features of physical storages for RDF triples and indexing structures supporting the query evaluation process. Finally, this process must discuss methods for finding optimal query evaluation plans, selection of relevant distributed sources and a set of optimization techniques, too.
Although the existing solutions already focus on the same area, these approaches do not target at all three main open challenges concurrently – data scaling, distribution and dynamicity.