Data redundancy resides in most, if not all, information systems. Linked Data is no exception. Existing approaches try to avoid data redundancies by proposing compression techniques or succinct data structures. However, data redundancies in Linked Data are useful sometimes, e.g., ontology based data access can make use of A-Box redundancies to avoid unnecessary query rewritings. Either you want to avoid it or make use of it, a good understanding about data redundancies will facilitate your task, e.g., identify the exact redundant parts which could be utilised or choose most effective techniques to compress a particular dataset. Unfortunately, little effort has been put on making the data redundancy explicit to data users. In this paper, we introduce a systematic categorisation for Linked Data redundancy, and propose a graph pattern based approach for efficient analysis. Analysis results on representative datasets lead to a main conclusion, that is redundant-aware techniques are demanded.
Data redundancy has different meanings in different contexts. In database community, data redundancy means that the same piece of data is stored in multiple places in a database system, while in information theory it means the wasted space used to transmit certain data. In this paper, we focus on data redundancy in Linked Data, which means the wasted space used to represent certain meaning in either stand-alone data space or the Web of Data environment.
Depending on the scenarios, data redundancy in Linked Data might have different effects to data consumption tasks. In many cases, Linked Data redundancy might be unwelcome. For example, for storage or exchange purpose, the redundancy will cause unnecessary resource consumptions, e.g., more disk spaces or longer time to download a dump file from the Web. However, in other occasions, the redundancy of the data can be utilised to facilitate the task on hand. For example, in Ontology Based Data Access (OBDA) tasks, A-Box redundancy can be utilised to avoid unnecessary query rewritings so that the efficiency of the system can be improved.
Redundancies in Linked Data have effects on a wide range of applications
including data publishing, query answering (in SPARQL endpoints), OBDA, and ontology
reasoning. Existing work [
To sum up, a better understanding about data redundancies in linked data will help us know more and deeper about the Data Web, which will in turn facilitate more effective and efficient exploitations on the linked data. In this paper, we focus on revealing the redundancies in Linked Data by both a qualitative analysis of systematic redundancy categorisation and an quantitative analysis on various datasets covering different domains.
The rest of the paper is organised as follows. In section 2, we briefly introduce related work. Section 3 gives an discussion about the categorisation of redundancies in Linked Data. Section 4 proposes our redundancy analysis methodology which covers two different dimensions. Section 5 gives the detailed analysis results on real world datasets. Finally, we conclude the work in section 6. 2
RDF compression techniques have been proposed to eliminate data redundancies. Such
as RDF serialisations techniques, i.e., HDT serialisation [
Given the fact that most Linked Datasets are represented in RDF data model, in the first part of this section, we study RDF data redundancy and point out the main focuses of this paper. In addition to RDF representation, the other important characteristic of Linked Data is that it is linked. What are the aspects of being linked relevant to the data redundancy, and how can they be effecting it? In the second subsection we try to answer these questions. 3.1
From the data model level, an RDF dataset is essentially a set of RDF graphs that contain a set of triples. To share or consume an RDF dataset, e.g., for storage, transmission Jeff Z. Pan Concept andRoleForgettingin
ALC Ontologies ?y jeff-z-pan foaf:made ISWC09_423 g1
Jeff Z. Pan Concept andRoleForgettingin
ALC Ontologies jeff-z-pan foaf:made ISWC09_423
GP1
?x rdf:type Person
Rules(as graph patterns)
Semantic Compressed RDF Graph
g2
or query-answering, it needs to be represented in the second level, i.e., the
serialisation level, where it has to be serialised as a sequence of bits. In this level, an RDF
dataset usually takes the form of textual or binary files by using predefined syntaxes,
e.g., RDF/XML, N-Triples or even sophisticated compression format (e.g. HDT [
In the data model level, the size of data can be calculated by the number of triples. Hence, in this level, the data redundancy exists if less triples can be used to represent the same semantic meanings of the original data. In the serialisation level, the data is represented as a sequence of bits. Given a fix set of triples, one serialisation is said to be more redundant than the other if it uses more bits than its counterpart.
In [
Types Data Model Level Serialisation Level
Semantic Redundancy An RDF dataset is said to be semantically redundant if some triples can be removed without leading to any changes in its meaning. In most cases the removal of these triples requires additional rules to be added in the dataset so that it is possible to re-generate the removed triples when needed. The usual form of such rules is the T-Box, i.e., the concept level statements in an ontology. For example, in Fig. 1, we have an RDF graph of g1. In the FOAF ontology 3, there is a rule of <f oaf :name; rdf s:domain; f oaf :P erson>. Based on the rdf s2 rule in the RDF specification, the type assertion in g1, i.e. <jeff-z-pan; rdf :type; f oaf :P erson>, can be removed, given the presence of <jeff-z-pan; f oaf :name; J ef f Z:P an>.
In a more general perspective, the semantic redundancy can be identified by
cooccurrences of triple patterns (cf. the red part of g1 in Fig. 1). Hence, it is not necessary
to restrain the ability of semantic redundancy identification by the limitation of T-Box
rules in representing triple pattern co-occurrences. In this regard, Joshi et al. [
of redundancies, i.e., syntactic and symbolic ones, both resides in the serialisation level. Their volume can be evaluated using the number of bits used in the serialisation. To separate the two, we can use a simple formula jF j = n r, where F is the serialisation file, n is the number of resource occurrences and r is the average bits needed to represent a resource. The syntactic redundancies reside in the component of n, while the symbolic ones are in r.
Most existing serialisation approaches apply syntaxes to reduce n. The idea is to group triples by subjects or objects so that the multiple occurrences of the same resource only need to be serialised once. For example, the RDF/XML serialisation standard provides abbreviation and striping syntaxes. However, such syntaxes only work on concrete graph structures. Similar graph structures (i.e. graph patterns) which repeatedly occur in the data are not taken into account. In the following example, the graph pattern GP has two instances of Inst1 and Inst2. The structure of GP appears twice in both instances. This means that each of the two predicate resources of GP , i.e. f oaf :name and f oaf :made, has two occurrences in its instances, which is avoidable when GP structure (stored wherever) is referred instead of duplicated in both instances.
GP : <?U; foaf:name; ?Y >; <?U; foaf:made; ?Z > Inst1 : < jeff-z-pan; foaf:name; Jeff Z. Pan >; <?U; foaf:made; ISW C09_423 >
Inst2 : < jose; foaf:name; Jose Manuel Gomez Perez >; <?U; foaf:made; ISW C13_1xx > We use the term of intra-structural redundancy to denote the unnecessary resource occurrences in concrete graph structure, while the term of inter-structural redundancy is used for the unnecessary resource occurrences of graph patterns in its instances. Most of existing serialisation approaches do not provide facilities to identify graph patterns. Hence, they leave the inter-structural redundancy untouched.
3.2
One of the most important characteristics of Linked Data is its linking capability, which is to create connections from one information source to the other. The connection can be created in the concept level, where individuals of one dataset are described using concepts from another dataset or vocabulary. We denote this type of connections as T-Box Reuse. The second type of connections is the linkage in individual level, where individuals in one dataset are specified to be the same as their counterparts in the other, e.g., by using owl:sameAs assertions. This type of connections is called as A-Box Linkage in this paper. Both types of connections have implications in changing the semantics of the original dataset. These implications might change the redundancies of the dataset in question. In rest part of this subsection, we briefly discuss the possible changes on data redundancies caused by T-Box Reuse, and leave the A-Box Linkage for future work.
T-Box Reuse Essentially, T-Box Reuse will bring new rules to the original dataset. These rules are a subset of the materialised axioms of the reused T-Box, which are applicable to individuals. These new rules can infer a set of new triples 4 to the reusing RDF dataset.
g
g
Removable Derivable
Fig. 2. Data Redundancies affected by T-Box Reuse
Fig. 2 illustrates a typical case of such inference results. In Fig. 2, the original RDF dataset, labelled as g, is denoted by the green oval, and the new set of inferred triples is denoted by the pink oval with a label of g0. Depending on whether they are in the overlap with existing triples, new triples can be divided into two parts. The two parts will lead to two different consequences to the redundancies of the original data. The overlap part, labelled removable in Fig. 2, contains those triples in g, which can be inferred by new rules as well. This means that they are turned to be semantically redundant by the reused T-Box. As a consequence, the dataset turns to have more redundancies. On the contrary, the other part (g0 n removable), labelled as derivable in Fig. 2, will decrease the data redundancy according to the definition of data compression ratio 5. Specifically, in this scenario, data compression ratio can be calculated by jgj+jderivablej , in which the bigger jgj jderivablej component becomes, the larger the compression ratio will be. 4 Some triples inferred by new rules might be inferred by the dataset’s own T-Box as well. To make discussion easier, we use the term new triples to denote those triples which can NOT be inferred by the dataset’s own T-Box but the new rules. 5 http://en.wikipedia.org/wiki/Data_compression_ratio
To sum up, removable and derivable affect the data redundancies in opposite ways. Analyses on them will reveal the effects on data redundancy of concept-level connections between Linked Data. 4
According to above discussions, the redundancies in Linked Data can be analysed from two dimensions (cf. Fig. 3). The first dimension is that of the RDF data redundancy, where the focus is to reveal different categories of redundancies from data model level to serialisation level. The second dimension is from the linked semantic point of view, where the focus is to analyse the data redundancy based on different types of semantics. The A-Box semantics is to analyse the data redundancy only from data level without any T-Box axioms. The other three types are considering both data and T-Box information. The No Linkage semantics is to do the analysis based on the dataset’s main T-Box. The main T-Box is the one most used for describing individuals in the data, which is either defined by the data provider or reused from other sources. In our analysis, we manually identify such main T-Box for each dataset. It is not necessary that every dataset has a main T-Box. In such cases, this analysis is not applicable. The T-Box Reuse semantics is the type of analysis focusing on redundancy changes caused by concept level connections, i.e., reusing T-Box, while the A-Box Linkage is to reveal the changes of data redundancies caused by the individual level connections.
RDF Redundancy Dimension A-Box
No Linkage A-Box & T-Box T-Box Reuse
A-Box Linkage
Semantic Syntactic Symbolic ✔ ✔ ✔ - ✔ -
- Linked Semantic
Dimension
In the matrix of Fig. 3, there are total 6 valid types of analyses. In this paper, we focus on four of them, which are marked with ticks in the figure. For A-Box semantics, we propose a graph pattern based approach to reveal the semantic and syntactic (interstructure only) redundancies. Based on the graph pattern approach, we propose a virtual materialisation approach to analyse data redundancies in No Linkage and T-Box Reuse semantics. The other two types of analyses are left for future work. As discussed in section 3.1, we focus on semantic redundancy and the inter-structural syntactic redundancy, both of which will be benefited from the ability to identify frequent graph patterns. For semantic redundancy, identified graph patterns can be used to identify possible rules for removing redundant triples. Combined with the knowledge of instance numbers of these graph patterns, these rules can be used to calculate the volume of semantic redundancy as number of removable triples. Similarly, for inter-structural redundancy, the structure of graph patterns and their instances numbers can give us a way to calculate the volume of syntactic redundancy in the data. In this subsection, we describe an entity description pattern based approach for redundancy analysis.
In an RDF graph, we call its non-literal nodes as entities. For an entity e in an RDF graph G, we can get a data block for it by extracting triples in G each of which has e as its subject or object. We call such kind of data blocks as Entity Description Blocks (EDBs for short).
For an EDB, it can be summarised by a notion of entity description pattern which is defined in Definition 1. EDP, the short name for entity description pattern, is the building block of our analysis approach.
Definition 1. (Entity Description Pattern) Given an entity description block Be, its description pattern is a tuple Pe = (Ce; Ae; Re; Ve), where – Ce = fcij < e; rdf : type; ci >2 Gg is called as the class component; – Ae = fpij < e; pi; li >2 G and li is a literalg is called as the attribute component; – Re = frij < e; ri; oi >2 G and oi is a URI resource or blank nodeg is called as the relation component; – Ve = fvij < si; vi; e >2 Gg is called as the inverse relation component.
Taking the RDF graph g1 in Fig. 1 for example, the EDP of entity jeff-z-pan is ff oaf :P ersong; ff oaf :nameg; ff oaf :madeg; ; , and the one of ISWC09_423 is ;; frdf s:labelg; ;; ff oaf :madeg .
By generating EDPs for all entities in an RDF graph G, we can get a EDP representation of G, which is a set of EDPs. As we will show in later section, the number of EDPs in an RDF dataset is usually much less than the number of entities. This is because many entities are sharing same EDP. The more entities are sharing one EDP; the more frequent its structure is duplicated. Such duplications are the source of data redundancies, which we break down to semantic redundancy and syntactic redundancy. Semantic Redundancy Identified By EDP In the definition of EDP, the class component Ce is a set of constant class names. Hence, it is straightforward to generate a graph pattern based substitution rule for removing these type assertions from the original data. In particular, the substitution rule is defined as (;; Ae; Re; Ve) ! (Ce; Ae; Re; Ve). Let fPe be the instance number of Pe, the number of triples can be removed by the rule is jCej fPe . In jeff-z-pan’s example, the rule will be (;; ff oaf :nameg; ff oaf :madeg; ;) ! (ff oaf :P ersong; ff oaf :nameg; ff oaf :madeg; ;). In this particular case, this rule is equivalent to the rule of <f oaf :name; rdf s:domain; f oaf :P erson> from F OAF vocabulary.
dundancy denotes the unnecessary structure recurrences in EDP’s instances, i.e. EDBs. Given an EDP Pe, it is straightforward to calculate its recurrences as (jAej + jRej + jVej) fPe , the unit of which is resource occurrence.
where N = (CeM n Ce) [ (AeM n Ae) [ (ReM n Re) [ (VeM n Ve) and f is an auxiliary dictionary which stores the instantiated times of each concept in Pe [ PeM .
The number of removable triples can be calculated as follows.
jderivablej = fPe
X f (c); c2N jremovablej = fPe
X f (c); c2E Virtual A-Box Materialisation on EDP When considering T-Box of an RDF dataset, the data redundancy might be changed due to the above-mentioned removable and derivable triple sets. To compute the two triple sets, inferences need to be performed on A-Boxes, which might be too expensive for large scale data analyses. For redundancy analysis purpose, we only need to know the size of removable and derivable sets instead of getting the exact triples. Inspired by this observation, we propose a virtual materialisation approach based on EDP to compute the triple sizes for the two triple sets.
As supporting efficient query answering is the basis of many Linked Data
consumption tasks, our discussion in this paper is based on OWL2 QL profile [
where E = (CeM \ Ce) [ (AeM \ Ae) [ (ReM \ Re) [ (VeM \ Ve). 5 5.1
The datasets selected for analysis are identified from Linked Open Data cloud 6. There is a coloured version which categorises the datasets in different domains. We selected 5 datasets from the Linked Open Data Cloud, which cover 5 out 6 domains listed in the coloured version. The general information about datasets is listed in Table 2.
In addition to trying to have a diverse domain coverage in dataset selection, we tried to select datasets with different sizes (cf. the #T riples column). We also selected two different datasets from one particular dataset (the Ordnance Survey), which are quite different in topics and size. The main purpose is to have our sample as representative as possible, while keeping the number of datasets manageable.
One strategy we apply in our analyses it to focus on data instances of most popular EDPs instead of working on all data. The idea is to maintain an efficient analysis while capturing the most part of the data. The threshold chosen is 90%, which means that we analysis 90% of the data.
(1) (2)
In the table, there are other metrics related to EDP. #EDP is the total number of EDPs identified in the dataset, which is a quantitative measurement about the variety of how entities are described. #EDP @90% is the minimal number of top popular EDPs the sum of whose instance numbers is not less than 90% of the total number of entities in the dataset. From Table 2, although the total number of EDPs are large in some cases, e.g., LinkedMDB has more than 10 thousand EDPs, the major part of the data (90%) resides in a very small number of EDPs in all cases. The more popular one EDP is; the more redundancy there will be. Hence, having a small number of very popular EDPs indicates a large volume of data redundancies. 5.2
A-Box only results Table 3 gives the analysis results by only considering A-Box level information. Both syntactic and semantic redundancies are analysed by EDP based approach. In the table, #RRes is the redundant resource occurrences of inter-structural redundancies; RRatiosyn is the syntactic redundancy ratio, i.e. ##RTRriepsl=es3 ; #RT riple is the redundant triples (i.e. semantic redundancy); RRatiosem is the semantic redundancy ratio, i.e. ##RTTrirpilpelse ; and #GP Rules is the number of graph pattern substitution rules needed to remove semantic redundant triples.
As for syntactic redundancies, in all datasets, they are considerably large. The redundant ratio is more than 20% in all cases except DBLP where the ratio is still near 6.5%. The biggest ratio was obtained from 50K Gazetteer, which is more than 32%. Furthermore, it is notable that we only consider inter-structural redundancy and the ratio is calculated from redundancies in 90% data over the whole data. This means that the overall syntactic redundancy ratio should be even more.
Syntactic Redundancy Semantic Redundancy #RRes RRatiosyn #RT riple RRatiosem #GP Rules 4,475,952 24.27% 610,463 9.93% 21
36,718 22.40% 8,845 16.19% 8 18,283,964 6.45% 2,901,347 3.07% 3 2,331,720 32.81% 259,080 10.94% 1
The right part of Table 3 shows that the EDP approach can identify substantial semantic redundancies as well. More than 3% of triples are redundant in all analysed datasets. The most semantically redundant one is LOV dataset, which has more than 16% redundant triples. The #GP Rules column shows an interesting phenomenon, i.e. these semantic redundancies can be removed by very small number of rules. The most efficient rule set comes from 50K Gazetteer, where one single rule can remove more than 10% triples.
Linked Semantics Table 4 shows the data redundancies under different explicit semantics. Two types of semantics of No Linkage and T-Box Reuse are analysed. #DT erm is the number of terms from reused T-Box, which are directly used by current dataset; and #RAxioms is the number of axioms from (materialised) reused T-Box, which are applicable in the dataset materialisation.
No Linkage analyses are done by considering the datasets’ main T-Boxes. As shown in left part of Table 4, LinkedMDB and LOV do not have a main T-Box. They are using concepts defined in their own name spaces but without specifications about the semantics of these concepts. Such situations are very common in Linked Data Cloud. For DBLP dataset, we identified its main T-Box as SWRC ontology 7. Considering this TBox, around 1.6 million triples can be further derived but no triples in the dataset are removable. This means that the current data is semantically less redundant when T-Box axioms are taken into account. The case of 50K Gazetteer is similar, where main ontology of the dataset is officially published 8. An interesting finding is that the derivable triples of 50K Gazetteer are even more than its original triples. This indicates that the dataset is published in a quite concise way. In Code-Point’s case, the T-Box can help remove around 1.6 million triples. This means that these triples turn to be redundant.
The right part of Table 4 gives the analysis result of considering reused T-Box axioms. 3 out of 5 datasets are reusing one popular T-Box, i.e. FOAF ontology. In LOV dataset, about 4% new triples can be inferred by the reusing FOAF ontology. In other two cases, LinkedMDB and DBLP, a surprisingly large number of triples can be derived. Note that in all cases, the datasets are only using two terms from FOAF. Even the total number of axioms applicable for the inference is quite small (cf. #RAxioms in the table). This indicates that T-Box Reuse might lead to substantial derivable triples even when the number of reused terms is very small. 7 http://ontoware.org/swrc/ 8 http://data.ordnancesurvey.co.uk/datasets/os-linked-data 10,000,000 1,000,000 100,000 10,000 1,000 100 10 1 LinkedMDB LOV
DBLP Ga5ze0tKeer Code-Point
Fig. 4. Comparisons: A. EDP VS. T-Box; B. Semantic VS. Syntactic; C. No Linkage VS. T-Box Reuse. Comparisons The top-left figure in Fig. 4 compares the volumes of semantic redundancies identified by EDP approach (#RT riples) and T-Box axioms (Removable). The Removable in the figure is the sum of Removables of both No Linkage and TBox Reuse. In Cod-Point dataset, the two approaches identified the same number of redundant triples. In all other cases, EDP approach is much better. This indicates that there exist a large volume of semantic redundancies which are only identifiable to more generalised rule systems than the T-Box axiom.
The top-right figure illustrates the comparison between semantic redundancy and syntactic redundancy. In all cases, the semantic one is less. The Sum of the two gives an idea about the overall data redundancies in these datasets. In 4 out of 5 datasets, the redundancy is more than 30%. The largest one is in 50K Gazetteer, which has 44% redundant data, and DBLP is least redundant dataset with about 15% redundancy.
The bottom figure in Fig. 4 shows the differences in the size of A-Box serialisation with and without Reused T-Box semantics. In the figure, the size of serialisation is illustrated using the percentage: P ercentage = jA-Box Materialisationj . In all cases, the jOriginal A-Boxj materialisations are increased by T-Box Reuse significantly. Notably, there are more than 26% increment for LinkedMDB and nearly 70% for DBLP. 6
In this paper, we introduced a systematic approach for analysing Linked Data redundancy. The most straightforward conclusion is that data redundancies in Linked Datasets are not only huge but also diverse. This leads to our main conclusion: redundancy-aware techniques are demanded for both data consumption and data publishing. The conclusion is supported by several observations as follows.
– For Data Compression The compression tools or techniques should be aware that different types of redundancies exist. Different redundancies might need different techniques. Moreover, the knowledge of redundancy distribution is crucial to tools which want to make a trade-off between efficiency and compression ratio. – For Data Access As shown in the results (cf. Table 2), data entities are described via different data patterns (EDPs). In most cases, the data distribution among EDPs is skewed, i.e. a small number of EDPs have a large number of data instances. For efficient data access purpose, the knowledge of such distribution and how to make use of it are critical. – For OBDA and reasoning Existing wok has shown that A-Box redundancy can be utilised to avoid unnecessary rewritings. Results in this paper suggests that moving a step forward from using rules equivalent to T-Box axiom to more general rule systems might improve the effectiveness of existing approaches significantly. – For Data Publisher Being encouraged to link their data to other datasets, the publisher should be aware of the consequences of such linking in terms of bringing in removable and derivable triples. We have shown that a very small number of reuses can lead to a very large number of derivable. Publishers should be alarmed before creating links, and tools are needed to estimate such consequences and prompt them to the publisher.