A novel approach for handling semantic trajectories on data warehouses

Abstract

A trajectory is a set of traces left by a moving object. It contains spatio-temporal information about where and when that object was, as well as other semantical relevant information. It is described by a continuation of movement. Data concerning moving objects and their trajectories can be stored in a Trajectory Data Warehouses for organization, managing, and analysis purposes. This work is dedicated to semantic trajectory data warehouses. A logical schema is proposed, called S-TrODW, where an object relational framework is used. The main novelty of the S-TrODW model is the integration of trajectories and their segments in the fact table by means of a nested relation. An algorithm is presented for transforming the flat star schema (with non-nested trajectory segments) to the S-TrODW schema. The proposal is validated through a case study dealing with freight transportation. A more natural modelling and queries formulation, as well as the improvement of query execution time are among the contributions of this paper compared to other works.

Keywords

trajectory data warehouse moving object semantic modelling trajectory trajectory segment

1. Introduction

New technologies such as cloud computing, GPS, and social media provide vast amounts of data which can be collected from the internet and may provide a powerful tool to businesses. The ability to manage and analyze these data is a key element of the companies for gaining competitive advantages, enhancing their customer satisfaction and their profit over time.

Business analysis and decision makers are usually assisted by data warehousing systems, since they are especially designed to help companies analyze their data. A data warehouse (DW) is a collection of large amounts of data with the main purpose being to support knowledge workers, i.e., a specialized database for decision making. Therefore, it is an essential component of business intelligence environments. Data in a DW is subject-oriented, integrated, consistent, time-variant, and non-volatile [1]. Data is usually consolidated from several different external sources. A DW is designed primarily for query and analysis of historical data rather than for daily transaction processing.

A DW especially designed and implemented for managing and analyzing data related to trajectories of moving objects is called a trajectory DW (TDW). A TDW stores trajectories, i.e., movements of spatio-temporal objects as well as aggregate measures concerning these trajectories. The applications of TDW are numerous, such as tourism, agriculture, transport, and ecology, to name just a few.

A TDW differs from a spatio-temporal DW (STDW) since the later intends to represent discreetly space and time dimensions, while the former focuses on the continuity of location changes as time progresses [2].

On the other hand, a semantic TDW provides crucial semantic insights to a TDW, such as the behavior, the characteristics, the activity, and the movement purpose of the moving object which enrich our understanding about it. For example, a truck that transports goods has a movement purpose, to deliver the goods. Typical online analytical processing (OLAP) operations together with other statistical operations may assist viewing trajectory data from different perspectives.

The design of a TDW varies significantly amongst different research proposals. One of the main dilemmas of researchers is the way trajectories are represented which is proved by the plethora of TDW models presented so far.

A trajectory is partitioned into a sequence of segments and segments are represented as spatio-temporal intervals, each one defined by two spatio-temporal points, for start and end.

In the literature, a trajectory is represented either as a set of points, cell of grids [3] or set of segments. Two main approaches are distinguished concerning the schema of the TDW, i.e., each tuple of the fact table refers either to the whole trajectory [4] or to a segment of a trajectory [5].

In this paper, we introduce a novel design of a TDW where a trajectory of a moving object is represented as a relational composed object (a nested relation of trajectory segments) in the fact table. The proposed model is called S-TrODW (Semantic Trajectory Object Data Warehouse) model. We formally define our model and present an algorithm for the transformation of the flat star schema, where the facts are composed of segments of a trajectory, to the S-TrODW schema. We present a case study where the S-TrODW model is evaluated against the corresponding flat star schema model. The results show that, when implemented, the S-TrODW model is faster and more efficient compared to the flat star schema approach.

The remainder of this paper is organized as follows. Various TDWs are briefly discussed in the next section. The motivation of the research work presented in this paper is discussed in Section 3. The generic semantic TDW design approach is defined in Section 4. The transformation of the flat star schema to the S-TrODW schema is given in Section 5. Section 6 deals with a case study for a transportation company and the experimental results are presented in Section 7, followed by a discussion in Section 8. In the last section, conclusions and possible directions for future research are outlined.

2. Related work

An early study on the field of TDW is presented in Orlando et al. [6]. The proposed TDW adopts the star schema where the fact table stores trajectories as well as measures about these trajectories. The measure ‘presence’ is discussed, which is an aggregate function calculating the number of individual trajectories belonging to a spatial area over a specific temporal interval. A prototype implementation is also conducted for the verification of their model.

In Marketos et al. [3] design issues for trajectory data warehousing are discussed. The study is concentrated in three domains which are essential for building a TDW: i) a trajectory reconstruction procedure for transforming spatio-temporal data into trajectories, ii) ETL phase for TDW feeding, and iii) aggregation of measures for OLAP analysis. The effectiveness of the approach was validated by experiments with real data sets.

The object-relational model is adopted in Leal et al. [7] where trajectories are treated as first class objects. Trajectories are enriched with semantics for including application domain meanings to data. They propose two algorithms for creating and loading the DW. They also define aggregation functions on trajectory data. A case study is presented with real data about truck travels.

A TDW is designed in Arfaoui and Akaichi [8] for studying the behavior of animal herds as a tool for assisting decision making based on the star schema. The whole trajectories are represented in the fact table and segments of trajectories are not distinguished.

Trajectory data are included in the set of data types for storing and querying spatio-temporal DWs in Zimányi [9]. These include time and spatial types, such as instant, periods, point, line, and region.

Fileto et al. [10] propose a semantic multidimensional model for a Movement DW (MDW) based on a framework for general hierarchies of movement segments. For this reason, definitions for movement segments, patterns, and related categories and objects are given. A case study demonstrates the expressiveness of the model by a number of queries semantically enriched with Linked Open Data (LOD, https://www.w3.org/egov/wiki/Linked_Open_Data).

Leonardi et al. [11] introduce a TDW framework where the activity of moving objects can be recorded and examined. Two types of facts are distinguished in their conceptual model, intra-granule and inter-granule, associated either to a single granule or pairs of granules respectively, where a granule is a contiguous spatial area during a given period of time. Two measures, V and P, are introduced. V (Visits) represents how many times some trajectories visit a specific spatio-temporal region and P (Presence) the number of trajectories occurring in a spatio-temporal region. Aggregate functions for these measures are also studied and methods for spatio-temporal visualization are proposed for OLAP analysis.

Nardini et al. [5] present a conceptual TDW model containing spatio-temporal dimensions and hierarchies. A geographic visual interface is provided for supporting OLAP analysis of mobility data. The Mob-Warehouse semantic model is also discussed which is based on the 5W1H (Who, Where, When, What, Why, How) framework. The fact table stores the detailed mobility information, and trajectories are represented in a dimension table.

A Semantic Trajectory Data Warehouse (STrDW) conceptual multidimensional model is proposed in Manaa, Sakouhi and Akaichi [12] originated from the Trajectory Ontology Design Pattern (TrODP) for Trajectory Data Warehouses (TrDWs). Experimental results on real data from seal animals verify the approach, where their behavior is analyzed during their dives. The dive state is the core activity of the multidimensional analysis based on structured trajectories as sets of sub-trajectories.

Vaisman and Zimányi [4] incorporate spatio-temporal data for developing a conceptual trajectory DW model. The proposed DW is called Mobility DW. Moving Objects (MOs) are represented by temporal types and the model is implemented with measures as MO data rather than segmented trajectories.

Alsahfi et al. [13] present a review of proposed TDWs approaches as well as various applications categories where TDWs may be beneficial. A framework is discussed consisting of five main components, as prerequisites for building a TDW: data sources, ETL, TDW, analysis tools, and TDW applications.

A semantic TDW is proposed in Garani and Adam [14] designed for enhancing nursing productivity. The model uses the constellation schema and extends the 5W1H model to several other sematic dimensions, e.g., Whom. The fact table represents trajectory segments where trajectories are stored in a dimension table with relevant semantics.

3. Motivation

Logical modeling is the process of translating business necessities to data requirements. Logical design of DWs refers to defining schemas to model facts and dimensions. In this phase, specific data are chosen, grouped together according to their characteristics, and relationships between them are defined. The schema helps the understanding of the structure complexity of a DW.

Over the years, different logical design methods and patterns have been defined, i.e., star, snowflake and constellation schemas. They differentiate by the number of dimension tables each dimension has and the number of facts they comprise. Each approach has advantages and disadvantages compared to the others. For example, in the star model, dimensions are not normalized in order to avoid joins while in the snowflake model, dimensions are normalized in order to avoid redundancy. Other schemas have also been proposed, i.e., StarNest schema as an integration of the star and snowflake schemas [15].

One of the most challenging aspects in the field of TDWs is the logical modeling of trajectories. A trajectory is a set of segments, where a segment is formed by two consecutive trajectory points. In the general case, the number of segments varies in different trajectories. Therefore, the number of segments that refers to a trajectory is not fixed and in general, not known in advance.

There are several different TDW approaches proposed so far, with the most dominant ones either the storage of segments in the fact table or in a dimension table. Both ways require a join operation to associate segments to trajectories, i.e., to reconstruct a trajectory.

Since a trajectory is a set of segments, the concept of nesting can be used for expressing this feature. The main advantage of this approach is the avoidance of separating trajectory from its segments physically as well as semantically, and the execution of less joins between fact and dimension tables. Join is an expensive operation and minimizing its use is an important optimization benefit, especially in the context of DWs. By adopting this approach, the storage and retrieval of complex sets of data such as trajectories, is facilitated.

Therefore, in this work, for the first time TDWs are studied by including trajectories and their corresponding sets of segments in the fact table by means of nested relations. Nesting ensures that segments belonging to the same trajectory are grouped together. To show the expediency of our proposal, we evaluated it on a case study, where several queries are executed, and their execution times are compared to an equivalent star model with non-nested segments.

4. Generic semantic trajectory DW design approach

As we outlined in the previous section, expressing each trajectory along with its segments as a single entity is a promising research direction. The model we propose, called S-TrODW, represents a semantic trajectory object-relational DW where trajectories of moving objects are modeled in the fact table and their corresponding sets of segments are included in each trajectory as a nested object. Dimensions are, as usual, application domain related to the field of interest.

The trajectory object, TrO, contains the trajectory data of a moving object, i.e., trajectory segments. Its definition is given next.

Figure 1.

UML abstract trajectory flat star model.

Definition 1. TrajectoryObject, TrO

TrO (*Segment(SegmentID, TimeID, SpaceID, Dim-ension ${}_{\text{S}}$ ID1, Dimension ${}_{\text{S}}$ ID2, …, Measure ${}_{\text{S}}$ 1, Measu-re ${}_{\text{S}}$ 2, …)), where:

•

SegmentID is the segment identifier.

•

TimeID and SpaceID are the IDs of the Time and Space dimensions respectively. They represent when and where the trajectory segment begins.

•

DimensionSID1, DimensionSID2, …are the IDs of semantic dimensions related with each segment.

•

MeasureS1, MeasureS2, …are business metrics of each segment used for analysis, such as duration and distance of the segment.

The prefix * is used as a symbol implying that the attribute is a set of segments (a nested relation).

The scheme of the trajectory fact table consists of TrOs and other attributes and is defined as follows.

Figure 2.

UML abstract S-TrODW model.

Definition 2. Scheme of Trajectory Fact table, TrF

TrF (TrajectoryID, TrO, DimensionTID1, DimensionTID2, …, MeasureT1, MeasureT2, …), where:

•

Trajectory ID is the trajectory identifier.

•

TrO is a trajectory object.

•

DimensionTID1, DimensionTID2, …are the IDs of semantic dimensions related with each trajectory.

•

MeasureT1, MeasureT2, …are business metrics of each TrO used for numerical analysis.

As can be observed from Definitions 1 and 2, two kinds of dimension identities are distinguished, those referring to the trajectories, Dimension ${}_{\text{T}}$ ID1, Dimension ${}_{\text{T}}$ ID2, … and those referring to the segments of the trajectories, Dimension ${}_{\text{S}}$ ID1, Dimension ${}_{\text{S}}$ ID2, ….

UML abstract representations of a trajectory flat star model and the corresponding S-TrODW model are shown in Figs 1 and 2 respectively.

5. Transformation of the flat star schema to the S-TrODW schema

Table 1
Changes from flat star to S-TrODW schema

Flat star schema	S-TrODW schema
Segment Fact	Trajectory Fact
Trajectory Dimension	Removed
Trajectory Dimension Attribute	Measure ${}_{\text{T}}$
Segment ID, Time Dimension ID, Space Dimension ID, Semantic Dimension IDs, Measure ${}_{\text{S}}$	TrO

The flat star schema remains the simplest and most popular one amongst all the proposed DW logical schemas. For this reason, we compare and transform it to the S-TrODW schema for evaluation.

In order to transform the flat star schema to the S-TrODW schema, a restructuring process is required.

In Table 1 the changes that need to be applied when converting the flat star schema to the S-TrODW schema are listed.

Next, we present the transformation of the flat star schema to the S-TrODW schema.

Algorithm for transforming the flat star schema to the S-TrODW schema

$\forall$ distinct Trajectory ID in Segment Fact table //construct *Segment

*Segment ${}_{\text{TrajectoryID}}=$ { $\cup$ tuple ${}_{\text{TrajectoryID}}$ [SegmentID, TimeID, SpaceID, Dimension ${}_{\text{S}}$ ID, Measure ${}_{\text{S}}$ 1, Measure ${}_{\text{S}}$ 2 …] }

Trajectory Fact $:=$ Segment Fact //rename Segment Fact to Trajectory Fact

Relocate Trajectory Dimension attributes: {TrAttr1, TrAttr2, …} to Trajectory Fact as {Measure ${}_{\text{T}}$ 1, Measure ${}_{\text{T}}$ 2, …} respectively.

Remove Trajectory Dimension

Figure 3.

Trajectory flat star conceptual model.

The conceptual trajectory flat star and S-TrODW models are shown in Figs 3 and 4 respectively. Trajectory Sem Dimension and Segment Sem Dimension correspond to trajectory and segment semantic dimensions respectively. It is noted that several semantic dimensions (either trajectory or segment) may appear in the model, however only one of each type is represented in Figs 3 and 4. Therefore, apart from Time and Space Dimensions, all other dimensions store data related to the semantic concepts of the modeled domain.

Semantic dimensions are considered according to the 5W1H (Who, Where, When, What, Why, How) model [16]. Nevertheless, other semantics may also be included [14], in addition to the 5W1H model, to enhance the knowledge related to the behavior and movement of a TrO, by answering to more interrogative pronouns, such as which, whom and whose. In the next section, a case study is introduced where these concepts are revealed and validated.

Figure 4.

S-TrODW conceptual model.

6. Case study

The case study presented in this section concerns a transport company. Freight transportation is an important multifaceted service worldwide for many reasons, i.e., energy consumption, pollution, truck fleet technology, road infrastructures, customer satisfaction, logistics management, information technology, among others. Transportation companies invest a lot of money for transporting and delivering goods from one place to another in a fast, efficiently, safely, and reliable way at competitive prices. Nowadays, the web offers to each individual the possibility of ordering products remotely, literally from anywhere in the world which increases the demand for transportation services.

The company used in this work owns many different vehicles for transporting goods to customers. Every day each vehicle makes a trajectory route for delivering merchandises to specific locations. A daily trajectory is composed of a number of segments, which have been selected in such a way as to reduce the total daily time, traveled distance, and fuel consuming. For simplicity reasons, each trajectory route is driven by the same driver, i.e., a change of driver is not considered during a single trajectory.

Every trajectory has a set of segments. For the sake of simplicity, we assumed that the average number of trajectory segments is 10. Each segment has a timestamp which represents the delivery date and time. Therefore, in the same trajectory the different segments should have a continuation in time, in the same day. For example, TrajectoryID $=$ 001 has 10 segments with timestamps 8:20, 9:00, 10:13, 10:33, 11:45, 11:58, 12:27, 13:07, 14:02, and 14:52 for the 27 ${}^{\text{th}}$ of October 2020.

Table 2
Flat star model tables size

Table name	Number of rows
TruckSegment	10 ${}^{9}$
Trajectory	10 ${}^{8}$
Truck	50
Driver	250
Time	2*10 ${}^{6}$
Space	10 ${}^{6}$
TransferObject	10 ${}^{3}$
DeliveryPurpose	20

Figure 5.

Transport company logical semantic TDW flat star schema.

Two different approaches were tested and compared, a flat star model with non-nested segments and the proposed S-TrODW model. The flat star schema for the TDW is given in Fig. 5 and the corresponding S-TrODW schema is given in Fig. 6.

The main difference between the two models is the fact table, whereas in the flat star schema it refers to segments, while in the S-TrODW schema it refers to trajectories. In addition, the flat star schema TDW model contains one more dimension, the Trajectory dimension. Thus, the flat star schema TDW model has one fact table (TruckSegment) and seven dimension tables, while S-TrODW has one fact table (TruckTrajectory) and six dimension tables. Note that the dimension tables Truck, Driver, Time, Space, TransferObject, DeliveryPurpose are the same in both schemas.

The schema of the fact table for the flat star model is as follows: TruckSegment(SegmentID, TrajectoryID, TruckID, DriverID, TimeID, SpaceID, TransferObjectID, DeliveryPurposeID, Duration, Distance)

The schema of the S-TrODW fact table is as follows: TruckTrajectory (TrajectoryID, TruckID, DriverID, *Segment (SegmentID, TimeID, SpaceID, TransferObjectID, DeliveryPurposeID, Duration, Distance), FuelConsumed, Kilometers)

Table 3

S-TrODW model tables size

Table name	Number of rows
TruckTrajectory	10 ${}^{8}$
Segment (Nested)	10 ${}^{9}$ (i.e., 10 for each trajectory)
Truck	50
Driver	250
Time	2*10 ${}^{6}$
Space	10 ${}^{6}$
TransferObject	10 ${}^{3}$
DeliveryPurpose	20

Figure 6.

Transport company logical semantic TDW S-TrODW schema.

Semantic dimensions are included in the model according to the 5W1H approach. The 5Ws are When, What, Who, Where, and Why and the corresponding dimensions are Time, TransferObject, Driver, Space, and DeliveryPurpose, respectively.

7. Experimental results

An Intel(R) Core(TM) i5-3210M processor CPU @ 2.5 GHz with 16 GB ram memory was used for the implementation running Windows 10 (64 bits). The DW was developed with Oracle Database 19c Enterprise Edition Release 19.0.0.0.0-Production and Oracle SQL Developer 20.2.0.175. The size of both DWs, i.e., the space that files physically consume on disk was 289.92 GB.

Data were randomly generated; however, logical constraints have been applied to them, e.g., Time: values from 8:00 to 18:00 (business hours), Year: values from 2011 to 2021, Kilometers: values from 10 to 500, Experience: values from 1 to 25.

In Tables 2 and 3 the number of tuples in both models are shown.

Space dimension X coordinate is ranged from 37.5000000 to 38.1000000 and Y coordinate from 23.4000000 to 23.9000000.

Twelve OLAP queries were executed. They varied in the number of selection conditions employed, the dimension tables accessed, the number of join operations performed, the number of group-by clauses used, the number of subqueries required, and the sort of aggregate functions supported. They are presented below, where they are expressed in both models, the flat star and the S-TrODW. The sequence of listed queries is in increased complexity.

Queries

Query 1. How many different trajectories were made by the truck with id 27?

Flat Star model

SELECT COUNT(DISTINCT TrajectoryID) FROM TruckSegment WHERE TruckID $=$ 27;

S-TrODW model

SELECT COUNT(*) FROM TruckTrajectory WHERE TruckID $=$ 27;

Query 2. Find pairs of trajectory ids that delivered at the same location in the same month of a year.

Flat Star model

SELECT TSa.TrajectoryID, TSb.TrajectoryID FROM TruckSegment TSa, TruckSegment TSb, Space Spa, Space Spb, Time Ta, Time Tb WHERE Ta.Month $=$ Tb.Month AND Ta.Year $=$ Tb.Year AND Spa.XCoordinate $=$ Spb.XCoordinate AND Spa.YCoordinate $=$ Spb.YCoordinate AND Ta.TimeID $=$ TSa.TimeID AND Tb.TimeID $=$ TSb.TimeID AND Spa.SpaceID $=$ TSa.SpaceID AND Spb. SpaceID $=$ TSb.SpaceID AND TSa.TrajectoryID $>$ TSb.TrajectoryID

S-TrODW model

SELECT TTa.TrajectoryID, TTb.TrajectoryID FROM TruckTrajectory TTa, TruckTrajectory TTb, Space Spa, Space Spb, Time Ta, Time Tb WHERE Ta.Month $=$ Tb.Month AND Ta.Year $=$ Tb.Year AND Spa.XCoordinate $=$ Spb.XCoordinate AND Spa.YCoordinate $=$ Spb.YCoordinate AND Ta.TimeID $=$ TTa.*Segment.TimeID AND Tb.TimeID $=$ TTb.*Segment.TimeID AND Spa.SpaceID $=$ TTa.*Segment.SpaceID AND Spb.SpaceID $=$ TTb.*Segment.SpaceID AND TTa.TrajectoryID > TTb.TrajectoryID

Although the wildcard “*” is a reserved character in SQL, it is used here as a symbol representing that “*Segment” is a nested table.

Query 3. Find the minimum kilometers traveled by the truck with ID $=$ 27 and consumed fuel more than 50 lt.

Flat Star model

SELECT MIN(Tra.Kilometers) FROM TruckSegment TS, Trajectory Tra WHERE TS.TrajectoryID $=$ Tra.TrajectoryID AND TS.TruckID $=$ 27 AND Tra.FuelConsumed $>$ 50;

S-TrODW model

SELECT MIN(TT.Kilometers) FROM TruckTrajectory TT WHERE TT.TruckID $=$ 27 AND TT.FuelConsumed $>$ 50;

Query 4. Find total kilometers traveled by all trucks on the 14th of February 2021?

Flat Star model

SELECT SUM(Tra.Kilometers) FROM TruckSegment TS, Trajectory Tra, Time T WHERE TS.TrajectoryID $=$ Tra.TrajectoryID AND TS.TimeID $=$ T.TimeID AND T.Day $=$ 14 AND T.Month $=$ ‘February’ AND T.Year $=$ 2021

S-TrODW model

SELECT SUM(TT.Kilometers) FROM TruckTrajectory TT, Time T WHERE TT.*Segment.TimeID $=$ T.TimeID AND T.Day $=$ 14 AND T.Month $=$ ‘February’ AND T.Year $=$ 2021

Query 5. How many kilometers drove driver with ID $=$ 1 in April 2021?

Flat Star model

SELECT SUM(Tra.Kilometers) FROM TruckSegment TS, Trajectory Tra, Time T WHERE TS.TrajectoryID $=$ Tra.TrajectoryID AND TS.TimeID $=$ T.TimeID AND TS.DriverID $=$ 1 AND T.Month $=$ ‘April’ AND T.Year $=$ 2021

S-TrODW model

SELECT SUM(TT.Kilometers) FROM TruckTrajectory TT, Time T WHERE TT.*Segment.TimeID $=$ T.TimeID AND TT.DriverID $=$ 1 AND T.Month $=$ ‘April’ AND T.Year $=$ 2021

Query 6. How many times the truck with ID $=$ 27 transferred objects for ‘move house’ reason on June 2020?

Flat Star model

SELECT COUNT(*) FROM TruckSegment TS, DeliveryPurpose DP, Time T WHERE TS.DeliveryPurposeID $=$ DP.DeliveryPur- poseID AND TS.TimeID $=$ T.TimeID AND TS.TruckID $=$ 27 AND DP.Reason $=$ ’move house’ AND T.Month $=$ ‘June’ AND T.Year $=$ 2020;

S-TrODW model

SELECT COUNT(*) FROM TruckTrajectory TT, DeliveryPurpose DP, Time T WHERE TT.*Segment.DeliveryPurposeID $=$ DP.DeliveryPurposeID AND TT.*Segment.TimeID $=$ T.TimeID AND TT.TruckID $=$ 27 AND DP.Reason $=$ ’move house’ AND T.Month $=$ ‘June’ AND T.Year $=$ 2020;

Query 7. How many deliveries were made at (38.0000000, 23.5000000) address during January 2021?

Flat Star model

SELECT COUNT(*) FROM TruckSegment TS, Space Sp, Time T WHERE Sp.X $=$ 38.0000000 AND Sp.Y $=$ 23.5000000 AND T.Month $=$ ‘January’ AND T.Year $=$ 2021 AND TS.SpaceID $=$ Sp.SpaceID AND TS.TimeID $=$ T.TimeID

S-TrODW model

SELECT COUNT(*) FROM TruckTrajectory TT, Space Sp, Time T WHERE Sp.X $=$ 38.0000000 AND Sp.Y $=$ 23.5000000 AND T.Month $=$ ‘January’ AND T.Year $=$ 2021 AND TT.*SegmentID.SpaceID $=$ Sp.SpaceID AND TT.*SegmentID.TimeID $=$ T.TimeID

Query 8. Average fuel consumed per month.

Flat Star model

SELECT T.Month, AVG(FuelConsumed) FROM TruckSegment TS, Trajectory Tra, Time T WHERE TS.TimeID $=$ T.TimeID AND TS.TrajectoryID $=$ Tra.TrajectoryID GROUP BY Month

S-TrODW model

SELECT T.Month, AVG(TT.FuelConsumed) FROM TruckTrajectory TT, Time T WHERE TT.*Segment.TimeID $=$ T.TimeID GROUP BY T.Month

Query 9. How many kilometers traveled each truck during 2020?

Flat Star model

SELECT TS.TruckID, SUM(Tra.Kilometers), FROM TruckSegment TS, Trajectory Tra, Time T WHERE TS.TrajecoryID $=$ Tra.TrajectoryID AND TS.TimeID $=$ T.TimeID AND T.Year $=$ 2020 GROUP BY TS.TruckID

S-TrODW model

SELECT TT.TruckID, SUM(TT.Kilometers), FROM TruckTrajectory TT, Time T WHERE T.TimeID $=$ TT.*Segment.TimeID AND T.Year $=$ 2020 GROUP BY TT.TruckID

Query 10. What was the maximum total weight carried in a single trajectory, when was it and by which truck?

Flat Star model

SELECT TS.TrajectoryID, TS.TruckID, T.Day, T.Month, T.Year, SUM(TO.Weight) FROM TransferObject TO, TruckSegment TS, Time T WHERE TO.TransferObjectID $=$ TS.TransferObjectID AND T.TimeID $=$ TS.TimeID GROUP BY TS.TrajectoryID, TS.TruckID, T.Day, T.Month, T.Year ORDER BY SUM(TO.Weight) DESC FETCH NEXT 1 ROWS WITH TIES;

Note that in case of ties in the maximum total weight, we include in the result all the ties, by means of the Oracle clause FETCH NEXT 1 ROWS WITH TIES.

S-TrODW model

SELECT TT.TrajectoryID, TT.TruckID, T.Day, T.Month, T.Year, SUM(TO.Weight) FROM TransferObject TO, TruckTrajectory TT, Time T WHERE TO.TransferObjectID $=$ TT.*Segment. TransferObjectID AND T.TimeID $=$ TT.Segment.TimeID GROUP BY TT.TrajectoryID, TT.TruckID, T.Day, T.Month, T.Year ORDER BY SUM(TO.Weight) DESC FETCH NEXT 1 ROWS WITH TIES;

Query 11. What is the maximum weight of a single delivery and which driver delivered it?

Table 4
Queries features

Query	Flat star tables	S-TrODW tables	No. of conditions	Aggregate functions	Group-by clause	No. of subqueries
1	TruckSegment	TruckTrajectory	1	COUNT	–	–
2	TruckSegment, Space, Time	TruckTrajectory, Space, Time	5	–	–	–
3	TruckSegment, Trajectory	TruckTrajectory	2	MIN	–	–
4	TruckSegment, Trajectory, Time	TruckTrajectory, Time	3	SUM	–	–
5	TruckSegment, Trajectory, Time	TruckTrajectory, Time	3	SUM	–	–
6	TruckSegment, DeliveryPurpose, Time	TruckTrajectory, DeliveryPurpose, Time	4	COUNT	–	–
7	TruckSegment, Space, Time	TruckTrajectory, Space, Time	4	COUNT	–	–
8	TruckSegment, Trajectory, Time	TruckTrajectory, Time	–	AVG	1	–
9	TruckSegment, Trajectory, Time	TruckTrajectory, Time	1	SUM	1	–
10	TruckSegment, TransferObject, Time	TransferObject, TruckTrajectory, Time	–	SUM	5	–
11	TruckSegment, TransferObject, Driver	TruckTrajectory, TransferObject, Driver	1	MAX	1	1
12	TruckSegment, Truck, Trajectory	TruckTrajectory, Truck	1	MIN	2	1

Flat Star model

SELECT D.DriverID, TO.Weight FROM TruckSegment TS, TransferObject TO, Driver D WHERE TS.DriverID $=$ D.DriverID AND TS.TransferObjectID $=$ TO.TransferObjectID AND TO.Weight $=$ (SELECT MAX(TO.Weight) FROM TruckSegment TS, TransferObject TO WHERE TS.TransferObjectID $=$ TO.TransferObjectID)

Table 5

Queries average execution times for the flat star and the S-TrODW approaches

Query	Average (ms)
	Flat star	S-TrODW
1	415	351
2	374	354
3	387	363
4	389	361
5	394	360
6	394	353
7	403	375
8	383	369
9	405	357
10	414	377
11	409	367
12	387	352
Average (ms)	396.2	361.6

S-TrODW model

SELECT TO.Weight, D.DriverID FROM TruckTrajectory TT, TransferObject TO, Driver D WHERE TT.DriverID $=$ D.DriverID AND TT.*Segment.TransferObjectID $=$ TO.Transfer ObjectID WHERE TO.Weight $=$ (SELECT MAX(TO. Weight) FROM TruckTrajectory TT, TransferObject TO WHERE TT.*Segment.TransferObjectID $=$ TO.Transfer ObjectID)

Query 12. Find the minimum trajectory and the truck model of the truck that made it.

Flat Star model

SELECT Tra.Kilometers, Tru.Model FROM TruckSegment TS, Truck Tru, Trajectory Tra WHERE TS.TruckID $=$ Tru.TruckID AND Tra.TrajectoryID $=$ TS.TrajectoryID AND Tra.Kilometers $=$ (SELECT MIN(Tra.Kilometers) FROM Trajectory Tra)

S-TrODW model

SELECT TT.Kilometers, Tru.Model FROM TruckTrajectory TT, Truck Tru WHERE TT.TruckID $=$ Tru.TruckID AND TT.Kilometers $=$ (SELECT MIN(TT.Kilometers) FROM TruckTrajectory TT)

We gathered queries’ characteristics in Table 4.

In the S-TrODW approach the *Segment subtable (an Oracle nested table) is used in queries 2, 4, 5, 6, 7, 8, 9, 10, and 11. All main OLAP operations are used, i.e., roll-up, drill-down, slice and dice. Selectivity is also varied from low and medium to high.

The average of queries’ execution times with the flat star approach was 396.2 ms and with the S-TrODW approach was 361.6 ms, as shown in Table 5. The improvement in performance of the S-TrODW approach versus the traditional flat star approach, i.e., the percentage decrease, is about 10%. This is due especially because a join is avoided in the S-TrODW approach by means of a nested table. It is expected that by increasing the number of segments in each trajectory, the percentage decrease would increase proportionally. However, due to time and disk space capacity constraints (about 150 hours for the creation of the two DW approaches and 300GB of data occupation), the implementation is not feasible at least in a serial processing system using a conventional computer. The solution is parallel processing in a cloud environment which is left as a future work of this research study. Additionally, the inclusion of appropriate indexes may increase considerably system performance [17].

8. Discussion

TDWs are developed especially for analyzing data related to mobile objects. They store heterogeneous spatio-temporal data, enrich with semantics related to several aspects in order to explore trajectories from different perspectives.

S-TrODW model aims to get ahead the problem of disintegrating trajectories and their segments. In the proposed model, the fact table stores the whole information of each trajectory as well as of all the segments that the trajectory is partitioned.

The advantages of the S-TrODW model are significant and they are summarized as follows:

•
A trajectory is considered as an object with a set of spatio-temporal segments and semantical characteristics. Therefore, the entire trajectory together with its segments is modelled in a single tuple and consequently, this provides a more natural view of data from a conceptual point of view.
•
The schema contains one less dimension table since trajectories and segments are both stored in the fact table.
•
The number of join operations between the fact and the dimension tables are reduced as a direct consequence of the former.
•
Queries are expressed more straightforwardly and natural and thus, it is easier for users to understand when querying the data since they are closer to how reality is perceived.
•
Better execution time is achieved.
•
No extra operations are required for splitting trajectories to segments.
•
No need to define new data types for the treatment of the trajectories and their segments.

The experimental study refers to freight transportation framework which has an impact to various aspects of society, such as logistics, economy, environment, customer satisfaction, and politics, among others. The effective management of transport companies’ goods delivery is essential equally to every single individual and to society as a whole. A TDW developed for a transportation firm offers a considerable support for the efficient organization of business in a number of different domains. Analysis of data derived from such a TDW, aims at confronting several dilemmas, such as fuel economy versus fast and safe delivery, serviceability versus reduction of transportation costs, optimization of product distribution time and minimization of distance traveled. The vehicle routing problem as it is called [18], might be assisted by data analysis provided from TDWs which is one of the best means for the modelling and analysis of trajectory data. The queries presented in the previous section give a perspective of the kinds of analysis that could be performed on data of this type. Other aspects may also be considered for trajectories, such as security and privacy for personal location data [19].
9. Conclusion

The main role of DWs is to extract useful information from several heterogenous sources in a suitable format for decision-making processes. In DWs what really matters is the ‘big picture’ of data and the prospect of accessing, integrating, querying operational data for analysis, and assessment. Thus, data are manipulated, selected, grouped, and queried for subject-based knowledge enhancement. In this paper, TDWs are modeled in a nested oriented approach. The proposed model, S-TrODW, stores trajectories and segments of trajectories in the fact table. The advantages of S-TrODW are numerous, mainly the representation of each trajectory and its segments as an object, where segments are in subtuples of the trajectory tuple. A case study is presented for freight and vehicle management in transport industry. The results are very promising, since segments and trajectories are stored together in the fact table, less joins are required, and query execution time is faster.

Future research directions include the parallel processing of such data expressed by the S-TrODW approach in a cloud environment. Comparing the S-TrODW approach with other approaches such as the StarNest approach, is also an interesting future work. The use of optimization techniques for further improvement of query execution time is a significant research challenge. It would also be interesting to implement the S-TrODW, e.g., in a document-oriented DBMS such as MongoDB where collection management through arrays in JSON documents is facilitated, and to compare its performance against our implementation in Oracle.

Footnotes

Acknowledgments

The authors would like to thank Dr. Sandro Bimonte for useful comments and suggestions that helped to improve the quality of this work.

Appendix

The SQL code in Oracle for defining the Truck Trajectory fact table having the *Segment column as a nested table is given below, where the SEGMENT TABLE is a NESTED TABLE inside TRUCK TRAJECTORY TABLE.

CREATION OF SEGMENT OBJECT

DECLARATION OF SEGMENT TYPE AS PART OF SEGMENT OBJECT

CREATION OF TRUCK TRAJECTORY FACT TABLE

References

Inmon

. Building the Data Warehouse. 4th ed. Indianapolis (IND): Wiley Publishing; 2005.

Oueslati

Akaichi

. Mobile Information Collectors’ Trajectory Data Warehouse Design. Int J Manag Inf Technol. 2010; 2(3): 1-20. doi: 10.5121/ijmit.2010.2301.

Marketos

Frentzos

Giatrakos

Ntoutsi

Pelekis

Raffaetà

Theodoridis

. A Framework for Trajectory Data Warehousing. In: 7th ACM International Workshop on Data Engineering for Wireless and Mobile Access 2008; 2008 Jun 13; Vancouver, Canada. New York (NY): ACM, 2008. pp. 8-15.

Vaisman

Zimányi

. Mobility Data Warehouses. ISPRS Int J Geo-Inf. 2019; 8(170): 1-22. doi: 10.3390/ijgi8040170.

Nardini

Orlando

Perego

Raffaetà

Renso

Silvestri

. Analysing trajectories of mobile users: from data warehouses to recommender systems. In: Flesca

Greco

Masciari

Saccà

, eds. A Comprehensive Guide Through the Italian Database Research Over the Last 25 Years. Studies in Big Data. vol. 31. Cham (Switzerland): Springer, 2018. pp. 407-421.

Orlando

Orsini

Raffaeta

Roncato

Silvestri

. Trajectory data warehouses: design and implementation issues. J Comput Sci Eng. 2007; 1(2): 240-61. doi: 10.5626/JCSE.2007.1.2.211.

Leal

Macedo

Times

Casanova

Vidal

Carvalho

. From Conceptual Modeling to Logical Representation of Trajectories in DBMS-OR and DW Systems. J Inf Data Manag. 2011; 2(3): 1-16. doi: 10.5753/jidm.2011.1421.

Arfaoui

Akaichi

. Modeling Herd Trajectory Data Warehouse. SSRG Int J Eng Trends Technol. 2011; May to June Issue: 57-71.

Zimányi

. Spatio-temporal Data Warehouses and Mobility Data: Current Status and Research Issues. In: Proceedings of 19th International Symposium on Temporal Representation and Reasoning 2012; 2012 Sep 12-14; Leicester, UK. Los Alamitos, (CA): IEEE Computer Society, 2012. pp. 6-9. doi: 10.1109/TIME.2012.29.

10.

Fileto

Raffaetà

Roncato

Sacenti

JAP

May

Klein

. A Semantic Model for Movement Data Warehouses. In: Song

Simitsis

Cuzzocrea

, eds. Proceedings of 17th International Workshop on Data Warehousing and OLAP 2014; 2014 Nov 7; Shanghai (China). New York (NY): ACM, 2014. pp. 47-56.

11.

Leonardi

Orlando

Raffaetà

Roncato

Silvestri

Andrienko

. A general framework for trajectory data warehousing and visual OLAP. Geoinformatica. 2014; 18: 273-312. doi: 10.1007/s10707-013-0181-3.

12.

Manaa

Sakouhi

Akaichi

. A Trajectory Ontology Design Pattern for Semantic Trajectory Data Warehouses: Behavior Analysis and Animal Tracking Case Studies. In: Taniar

Rahayu

, eds. Emerging Perspectives in Big Data Warehousing. Hershey (PA): IGI Global; 2019. pp. 83-104. doi: 10.4018/978-1-5225-5516-2.ch004.

13.

Alsahfi

Almotairi

Elmasri

. A Survey on Trajectory Data Warehouse. Spat Inf Res. 2020; 28(1): 53-66. doi: 10.1007/s41324-019-00269-x.

14.

Garani

Adam

. A semantic trajectory data warehouse for improving nursing productivity. Health Inf Sci Syst. 2020; 8(1): 1-13. doi: 10.1007/s13755-020-00117-5.

15.

Garani

Helmer

. Integrating Star and Snowflake Schemas in Data Warehouses. Int J Data Warehous Min. 2012; 8(4): 22-40. doi: 10.4018/jdwm.2012100102.

16.

Wagner

de Macêdo

JAF

Raffaetà

Renso

Roncato

Trasarti

. Mob-Warehouse: a semantic approach for mobility analysis with a trajectory data warehouse. In: Parsons

Chiu

, eds. Advances in Conceptual Modeling. ER Workshops: Proceedings of International Conference on Conceptual Modeling. 2013 Nov 11-13; Hong Kong, China. Lecture Notes in Computer Science, vol. 8697, Cham (Switzerland): Springer, 2014; pp. 127-136.

17.

Ziani

Ouinten

. An Improved Approach for Automatic Selection of Multi-tables Indexes in Ralational Data Warehouses Using Maximal Frequent Itemsets. Intell Decis Technol. 2013; 7(4): 279-292. doi: 10.3233/IDT-130169.

18.

Mahmud

Haque

.Solving Multiple Depot Vehicle Routing Problem (MDVRP) using Genetic Algorithm. In: Proceedings of International Conference on Electrical, Computer and Communication Engineering 2019; 2019 Feb 7-9; Cox’sBazar, Bangladesh. IEEE Computer Society, 2019. pp. 1-6. doi: 10.1109/ECACE.2019.8679429.

19.

Verykios

Damiani

Gkoulalas-Divanis

. Privacy and Security in Spatio-temporal Data and Trajectories. In: Giannotti

Pedreschi

, eds. Mobility, Data Mining and Privacy. Berlin-Heidelberg: Springer, 2008; pp. 213-240.

A novel approach for handling semantic trajectories on data warehouses

Abstract

Keywords

1. Introduction

2. Related work

3. Motivation

4. Generic semantic trajectory DW design approach

Table 1 Changes from flat star to S-TrODW schema

Algorithm for transforming the flat star schema to the S-TrODW schema

Table 2 Flat star model tables size

Queries

Table 4 Queries features

Footnotes

Acknowledgments

Appendix

References

Table 1
Changes from flat star to S-TrODW schema

Table 2
Flat star model tables size

Table 4
Queries features