Synthetic data are widely used for evaluation, testing, and experimentation. However, there is a lack of systems, tools and datasets that can be used for benchmarking in the context of evolution. In the case of RDF, generation of synthetic data that change through time must take into account evolving paradigms and characteristics that make sense, rather than arbitrary insertions and deletions of triples. In this paper, we discuss requirements for generation of synthetic evolving datasets by abstracting several characteristics of the process, and present EvoGen, a tool for evolving dataset generation that is based on the widely used Lehigh University Benchmark (LUBM) generator.
The Resource Description Framework1 (RDF) is a W3C
recommendation for modelling and publishing data in Linked
Data and Semantic Web contexts. Due to the wide
adoption of RDF, as well as the dynamicity of data published
in the Data Web, the need for handling evolution in such
datasets becomes increasingly relevant. The importance of
evolution management in the context of the Data Web has
been stressed out in the literature as a means of addressing
issues such as provenance tracking, longitudinal querying,
semantic change detection and representation, dealing with
broken URIs and so on [
For instance, versioning can take place on either the resource level, or the dataset level, and at the same time, changes can be detected and represented as simple (e.g. triple additions/deletions), or more complex (e.g. schema changes, groupings of triple additions that result in higher level changes). Moreover, other requirements that are often present in evolving RDF have to do with metadata, such as provenance and temporal annotations. There exist several tools for storage and archiving that come with varying functionalities, however, there is a lack of support when it comes to benchmarking them. Two main aspects must be considered towards this goal. First, the existence of real and synthetic datasets of varying size and complexity that represent several cases of evolution is an important element of such a benchmark. Then, the performance evaluation of these tools require the existence of appropriate query workloads and representative evolving operations. In this paper, we intend to address the former, i.e. generation of synthetic datasets in evolving contexts.
Contributions. The contributions of this paper can be summarized as follows: we discuss the requirements and characteristics of the process of creating synthetic versioned RDF data, we describe EvoGen, a prototype implementation for con gurable synthetic dataset generation in evolving contexts that extends the Lehigh University Benchmark (LUBM) generator with support for the de ned characteristics.
This paper is outlined as follows. Section 1 introduces the subject. Section 2 provides an overview of related work. Section 3 discusses conceptual aspects of di erent evolution paradigms in RDF. Section 4 describes the implemented system, and Section 5 concludes the paper. 2.
The Lehigh University Benchmark (LUBM) [
Our approach aims at lling the gap of synthetic data generation in evolving contexts. For this purpose, we have chosen to extend LUBM in order to provide capabilities of versioned data, because it is a widely adopted and established benchmark, and can be used in storage, querying, as well as reasoning scenarios.
Generation processes for evolving datasets have to meet several functional, as well as non-functional requirements regarding the data creation. These include parameterization and con gurability, as well as scalability and e ciency. The generation of evolving datasets must be abstracted from the generation of synthetic data in general, in order to identify, and consequently quantify, the inherent characteristics that are speci c to evolving contexts.
In order to de ne and quantify input parameters, we go
on to outline high-level, dataset-independent characteristics
that will enable parameterization in the generation process.
We consider D as a diachronic RDF dataset as de ned in
[
1. Shift: the shift of an evolving dataset captures the modi cation of its size through di erent versions. In essence, it represents the direction towards which its size leans through the passing of time. The shift of a dataset is given with respect to a time period [ti; ti+n], and depending on its value, it can lead to incremental, decremental or unchanged data. For example, when comparing two versions of an RDF dataset D, at times ti and tj, the shift of D will be incremental if the dataset size increased (i.e. more insertions than deletions), decremental if it decreased (i.e. more deletions than insertions) and unchanged if it remained the same (i.e. equal number of insertions and deletions). In order to quantify the shift h of D between ti and ti+n, we regard it as a function h(D)jttii+n of low-level changes (triple insertions/deletions) in D between ti and ti+n with respect to ti: h(D)jttii+n = jDi+nj jDij jDij (1) When de ning h in a given time period, the changes are distributed across all versions that exist within that period. 2. Monotonicity: the monotonicity of a dataset captures whether or not a dataset with an incremental or decremental shift changes monotonically in a given time period [ti; tj]. A shift is monotonic when only additions or deletions of triples occur in all consecutive versions of a dataset between ti and tj. For example, the evolution of a dataset between ti and tj with incremental (decremental) shift is monotonic i between ti and tj only triple additions (deletions) take place. More formally, an RDF dataset D is monotonically incremental if it has an incremental shift, and the following holds for any arbitrary time points tk and tl: and decremental when
tk < tl
tk < tl
tj
tj
(2)
(3)
Monotonicity is an important characteristic that can
be used for supporting use cases where datasets are
only changing in one direction. In real-world scenarios,
this is especially useful for creating datasets that are
only increasing (e.g. log les, publication databases
etc.).
3. Strictness: strictness is a boolean property that a dataset
exhibits when it follows predictable schema patterns
through time. Because of the schema looseness
typically associated with RDF, an abstraction of schema
in RDF datasets is needed in order to de ne strictness.
We recall the notion of Characteristic Sets [
Sc(s) = fp j 9o : (s; p; o) 2 Dg and the set of all Sc for a dataset D at time ti is:
Sc(D) = fSc(s) j 9p; o : (s; p; o) 2 Dg A dataset D is strict in a given time period [ti; tj] if the set of all Characteristic Sets Sc(D) remains the same within this time period: @tk; tl : Sc(Dtk ) 6= Sc(Dtl ); ti tk < tl tj (4) Whether the actual subject and object nodes change is not relevant unless it causes a change in SC (D), as we are essentially interested in structural changes, rather than instancelevel changes. In essence, (4) holds when there are no inherent structural changes between versions of D within a given time period.
For our purposes, we implemented EvoGen2, a generator of RDF datasets with con gurable parameters according to the characteristics discussed in Section 3. The system is an extension of the existing Lehigh University Benchmark (LUBM) generator, which is written in Java and is a pure write-only solution that does not contain any abstractions and models for RDF datasets. While the original LUBM provides support for generation of OWL as well as DAML les, our implementation is only aimed at RDF/XML les, mainly because, unlike the original LUBM generator, EvoGen is not meant to be a benchmark for reasoning systems. The high-level architecture of EvoGen can be seen in Figure 1.
In this rst version of EvoGen, the requirement for congurable strictness has not been implemented and is left as future work. Thus, the implemented functionality only concerns changes on the instance level, with a strict structure. In fact, the strictness of the structure is inherited from the schema used by LUBM in its original implementation.
Along with LUBM's original system, which requires parameters concerning the size of the dataset (in number of universities), EvoGen's generation process requires the following parameters: 1. number of versions: an integer denoting the total number of distinct versions (dataset materializations at different time points). The number of versions needs to be larger than 1 in order for EvoGen to generate datasets, else the original LUBM generator is invoked. 2. shift: this is the value h(D)jttij de ned in equation (1) for a time period [ti; tj], i.e. a percentage of changes between versions Di and Dj with respect to the size of Di. In this version of EvoGen, only strictly incremental and decremental shifts between consecutive versions have been implemented. This means that every version will be shifted with respect to its previous version, instead of generating an aggregated shift between the rst and the last version, which would require distributing the required changes along a number of versions and maintaining the h(D) value only between the rst and the last version in the given period. Instead, this is left as future work. 3. monotonicity: A boolean denoting the existence of monotonicity in the shift, or lack thereof.
The above parameters instantiate the generation process with the use of two basic components, namely the Version Management component and the Change Creation component. These are responsible for translating input parameters dynamically and mapping them to appropriate structures, holding information on the types of entities to create, the size and quantity of the created entities, as well as the decisions on which existing entities to evolve. These sit on top of an extended LUBM generator, which in essence is the core LUBM generator modi ed to accommodate serializations of di erent versions in the le system. The functionality is exposed through a Java API that can be invoked by importing the system's jar le and accessing its methods directly.
The Change Creation component is responsible for creating the elements to be added, or determining the elements
https://github.com/mmeimaris/EvoGen at: to be deleted, calculating the actual number of insertions/deletions for each class, based on dynamic weighting of the instances of each class with respect to the total dataset size, randomizing parts of the process with respect to actual created/removed instances and so on. This component is responsible for communicating with the Extended LUBM Generator component, which performs the actual serialization of dataset versions in the le system. The core LUBM implementation generates data based on a xed schema, by iterating through each class and creating elements in each respective schema-imposed sub-structure. It performs some degree of randomization on URIs, mappings of elements to other elements (e.g. Professor32 teaches at University21 ). In order to distribute the required changes so that the generation process outputs versions with the desired shift, we assign weights to each class-based sub-structure and dictate the cardinality of the instances of each class to the generator. This weighting is done in the Weight Assignment Module, which uses hard coded, normalized weights in the range of 0 : : : 1 for each class, based on ranges acquired by observing the output of the original, non-versioned LUBM datasets for varying sizes. By multiplying these weights with the desired shift value h(D)jttij , we can get an approximate number of instances that need to be created for each class.
The Version Management component holds and updates session information on each version during runtime, the schema of the dataset, the mapping of versions to descriptive metadata and les in the le system and so on.
In order to preliminarily evaluate and validate the output of EvoGen, we perform a series of generation tasks for different combinations of numbers of universities and changes, and a xed number of 10 versions, and we measure the achieved shift with respect to the required one. Speci cally, we perform 10 runs of generations for three di erent values of h, namely h(D) = 0:2, h(D) = 0:4, and h(D) = 0:6 and we report the percentage di erence between the mean of the achieved h and the required one. The results can be seen in Figure 2. With a small number of universities, the achieved shift di ers signi cantly with respect to the required one, but as the number of universities, i.e. the dataset size, increases, the error decreases. Therefore, for a reasonably large number of dataset size, (e.g. > 5 universities), EvoGen performs as expected. Note, however, that this preliminary evaluation does not take into account scalability and e ciency issues, which is left as future work.
In this paper, we discuss several characteristics of generating synthetic versioned RDF datasets, and we describe EvoGen, an implementation that addresses a subset of these characteristics. Furthermore, we perform a preliminary evaluation of the system in order to measure how well the desired shift is achieved.
As future work, we intend to fully address the discussed characteristics, enable the insertion and deletion of schema elements as well, and address issues of scalability and e ciency when creating very large datasets. Finally, we intend to design query workloads based on the created data, in order to further support benchmarking versioning and evolution management systems for RDF datasets.
Acknowledgements. This work is supported by the EUfunded ICT project "DIACHRON" (agreement no 601043).