Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Conference or Workshop Paper |
| Scope | Discipline-based scholarship |
| Published in Proceedings | Yes |
| Title | Supporting Set Operations in Temporal-Probabilistic Databases |
| Organization Unit | |
| Authors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| Page Range | 1180 - 1191 |
| Event Title | 34th IEEE International Conference on Data Engineering, ICDE 2018 |
| Event Type | conference |
| Event Location | Paris, France |
| Event Start Date | April 16 - 2018 |
| Event End Date | April 19 - 2018 |
| Publisher | IEEE |
| Abstract Text | 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. |
| Official URL | http://orbilu.uni.lu/bitstream/10993/37837/1/377_ICDE2018.pdf |
| Digital Object Identifier | 10.1109/ICDE.2018.00109 |
| Other Identification Number | merlin-id:16908 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|