Header

UZH-Logo

Maintenance Infos

Supporting Set Operations in Temporal-Probabilistic Databases


Papaioannou, Aikaterini; Theobald, Martin; Böhlen, Michael Hanspeter (2018). Supporting Set Operations in Temporal-Probabilistic Databases. In: 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, 16 April 2018 - 19 April 2018, 1180-1191.

Abstract

In temporal-probabilistic (TP) databases, the combination of the temporal and the probabilistic dimension adds significant overhead to the computation of set operations. Although set queries are guaranteed to yield linearly sized output relations, all of the existing solutions exhibit a quadratic runtime complexity. They suffer from redundant interval comparisons and additional joins for the formation of lineage expressions. In this paper, we formally define TP set operations and study their properties. For their efficient computation, we introduce the lineage-aware temporal window, a mechanism that binds intervals with lineage expressions. We suggest the lineage-aware window advancer (LAWA) for producing lineage-aware temporal windows, which enable direct filtering of irrelevant intervals and finalization of output lineage expressions. This way, we compute TP set operations in linearithmic time. A series of experiments over both synthetic and real-world datasets show that (a) our approach has predictable performance, which depends only on the size of the input relations and not on the number of time intervals per fact or the overlap of the time intervals, and that (b) it outperforms state-of-the-art approaches.

Abstract

In temporal-probabilistic (TP) databases, the combination of the temporal and the probabilistic dimension adds significant overhead to the computation of set operations. Although set queries are guaranteed to yield linearly sized output relations, all of the existing solutions exhibit a quadratic runtime complexity. They suffer from redundant interval comparisons and additional joins for the formation of lineage expressions. In this paper, we formally define TP set operations and study their properties. For their efficient computation, we introduce the lineage-aware temporal window, a mechanism that binds intervals with lineage expressions. We suggest the lineage-aware window advancer (LAWA) for producing lineage-aware temporal windows, which enable direct filtering of irrelevant intervals and finalization of output lineage expressions. This way, we compute TP set operations in linearithmic time. A series of experiments over both synthetic and real-world datasets show that (a) our approach has predictable performance, which depends only on the size of the input relations and not on the number of time intervals per fact or the overlap of the time intervals, and that (b) it outperforms state-of-the-art approaches.

Statistics

Citations

Downloads

24 downloads since deposited on 11 Jan 2019
24 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Event End Date:19 April 2018
Deposited On:11 Jan 2019 13:46
Last Modified:12 Jan 2019 09:22
Publisher:IEEE
OA Status:Green
Official URL:http://orbilu.uni.lu/bitstream/10993/37837/1/377_ICDE2018.pdf
Other Identification Number:merlin-id:16908

Download

Download PDF  'Supporting Set Operations in Temporal-Probabilistic Databases'.
Preview
Content: Published Version
Filetype: PDF
Size: 243kB