Understanding time-based e ects has become an important aspect for the analysis of Knowledge Graphs (KGs). We have seen this in di erent areas such as IoT or economics. Scalable solutions for using Datalog-based KGs with time are in their infancy and the usage together with aggregation has not been considered so far. Yet, one needs both aggregation and time-based analysis when analysing KGs such as those of economic phenomena. In this paper, we analyze monotonic aggregation over DatalogMTL, establishing the rst work that covers full recursion like in Datalog, aggregation, and temporal reasoning.
Understanding time-based e ects has become a central aspect of reasoning on
Knowledge Graphs (KGs), particularly in speci c but prominent application
settings and business domains. They include: IoT, where context awareness requires
aggregating temporal data from continuous (and heterogeneous) sources [
In order to support such use cases in Datalog-based reasoning, a temporal
extension of Datalog for aggregation over time is required. MTL (Metric
Temporal Logic) for Datalog (short DatalogMTL) [
To support the mentioned use cases, temporal reasoning must be enriched
with the possibility to compute aggregations over time. Monotonic aggregation
has received a great deal of attention in the literature [
Our contribution. In this paper, we investigate aggregation for temporal Datalog languages. Our main contributions are: { We provide the rst reasoning language that covers at the same time (1) full recursion (i.e., it comprises Datalog); (2) aggregation capabilities, and (3) temporal reasoning (i.e., it comprises MTL as in DatalogMTL). { We provide a principled integration of state-of-the-art semantics of (1-3), overcoming critical semantic di erences while sustaining e cient evaluation. { We propose tractable, non-blocking algorithms for calculating monotonic time-point aggregation in Datalog. To this end, we augment speci c fragments of DatalogMTL with monotonic aggregation, by using advanced interval tracking and enabling several time-based optimisations. { We introduce speci c, novel monotonic aggregation over the time axis without any pre-determined bounds, which requires special care as time is the aggregation dimension. In particular, we introduce, as an example, an operator to analyse monotonic trends. { We provide real-world examples and show the practical relevance of our extensions within settings of industrial relevance, such as those in the nancial settings experienced in our work with the Central Bank of Italy. Organization. The remainder of this paper is organized as follows: In Section 2 we introduce some preliminaries for DatalogMTL and non-temporal monotonic aggregation. In Section 3 we discuss the requirements for temporal aggregation in Datalog. In Section 4 we present time-aware algorithms for time-point aggregation and discuss aggregation along the time axis in Section 5. We provide related work in Section 6 and conclude the paper in Section 7. We provide proofs and additional explanations in the appendix. 2
In this section, we introduce DatalogMTLFP under continuous semantics [
Syntax of DatalogMTLFP. Let C and V be disjoint sets of constants, and variables, respectively. A term is either a constant or a variable. An atom is an expression of the form P ( ), where P is a predicate of arity n ≥ 0 and is a n-tuple of terms. A rule is an expression of the form
A1 ∧ ⋅ ⋅ ⋅ ∧ Ak → B for k ≥ 0 where all Ai and B are literals that follow the grammar:
A ∶= P ( ) S ⊟ A S x A
B ∶= P ( ) The conjunction of Ai is the rule body, whereas B is the rule head. Instead of ∧ we sometimes use \;" to denote conjunction. A predicate p ∈ P is intensional (IDB), if p occurs in the head of the rule whose body is not empty, otherwise p is extensional (EDB). A rule is ground if it contains no variables, and safe if each variable in the head is also contained in the body. A program is a nite set of safe rules and is in normal form if it contains only rules of the form: P1( 1) ∧ ⋅ ⋅ ⋅ ∧ Pn( n) →P0( 0) (n ≥ 0) x P1( 1) →P0( 0) ⊟
P1( 1) →P0( 0) (1) (2) (3)
= ⟨x; y⟩ is de ned over the domain Q≥0 ∪ {+∞} where ⟨x; y⟩ = {t ∈ Q≥0 S x ≤ t ≤ y and x; y ≥ 0 and x ≠ t if ⟨ is `(', and y ≠ t if ⟩ is `)'}: We use ⟨, (resp. ⟩) depending on the context for unspeci ed or value-speci c, (, resp. ) for open and [, resp. ] for closed intervals. An interval is bounded if bxy;yt∈. QTh≥0e, lpeuftncetnudapl oifinitt iiss odfetnhoetefodr mby[t;−t],ani.de.,thhaesraiglhetngetnhdpofoi0n,tabnyd is+d,ewnohteerde + = ∞ if the interval is unbounded to the right. The length is de ned as S S = ∞ if + = ∞, otherwise S S = + − −. For two non-empty intervals 1 and 2, we de ne the union 1 ∪ 2 and intersection 1 ∩ 2 as usual. Note that, a union operation creates one or two intervals, whereas an intersection of two intervals is either the empty set or exactly one interval. We de ne 1 + 2 as ⟨ 1− + 2−; 1+ + 2+⟩, where ⟨ (resp. ⟩) is closed if 1 and 2 are left-closed (resp. right-closed), as well as 1 ⊕ 2 as ⟨ 1− + 2+; 1+ + 2−⟩, where ⟨ (resp. ⟩) is closed if 1 is left-closed and 2 is right-open (resp. if 1 is right-closed and 2 is left-open). We de ne an interval as an empty set if − > +.
is a ground atom and t a punctual interval.
Semantics of DatalogMTLFP. Let M be an interpretation based on a domain ≠ ; for the variables and constants that speci es, for each ground atom and each time point t ∈ Q≥0, whether is true at t. In this case, we write M; t ⊧ . Let be an assignment of elements of to terms such that (c) = c for each constant c. We then de ne inductively:
M; t ⊧ P ( ) M; t ⊧ ⊟ A M; t ⊧ x A if M; t ⊧ P ( ( )) if M; s ⊧ A for all s with t − s ∈ We say that M satis es a rule under an assignment if M; t ⊧ B, whenever M; t ⊧ Ai, for each 1 ≤ i ≤ k, and satis es a program if it satis es all its rules. The interpretation M is a model of and D if M satis es for all possible assignments (i.e., model of ), and if M; t ⊧ , for all facts a@t ∈ D (i.e., model of D). Finally, a program and a dataset D entail a fact @t, written ( ; D) ⊧ @t, if M; t ⊧ for each model M of and D.
In the following, we provide as example the rules for detecting spamming traders to illustrate the usage of DatalogMTL. We de ne spamming traders as trader that send at least every 5 seconds a trading signal for a duration of one hour (assuming seconds as granularity), where X is the trader identi er.
⊟[0;3600) x[0;5)tradingSignal (X) → spammingTrader (X)
Monotonic Aggregation. Monotonic aggregation so far has only been
introduced for non-temporal Datalog. Here we summarize the aggregation operators
mcount, msum, mmax, mmin, as introduced by Shkapsky et al. [
In the following, we provide as example the rules for path-counting in a DAG [
edge(X; Y ) → cpaths(X; Y; mcount⟨(1; X)⟩) edge(Z; Y ); cpaths(X; Z; C) → cpaths(X ; Y ; mcount ⟨(C ; Z )⟩) cpaths(X; Y; C) → countpaths(X ; Y ; max ⟨(C )⟩) 3
In this section, we analyze the requirements of temporal reasoning and aggregation in Datalog. We rst consider general requirements that are desirable in a declarative AI solution in this context and then instantiate them into speci c requirements for temporal aggregation: { RQ1: Declarative. Managing temporal properties calls for complex interval checking logic and arithmetic. This easily leads to an error-prone and laborintensive procedural approach. Declarative temporal operators that specify what should be done instead of how it should be done avoid such pitfalls. Example. A baseline implementation for UC2 would rst extend a time-point interval to an hour-long interval, then split the intervals into independent \counting" intervals|at each start or end of some interval in the data the count changes, i.e., either a trade is added or removed from the data|and nally count the number of entries per interval.
{ RQ2: Implicit Time. While explicit time in rules provides the user the possibility to access and modify temporal properties, they require semantic restrictions for the chosen operations to block arbitrary rule behavior. Implicit time handling, such as in temporal logics or DatalogMTL, does not have such issues, allowing for a fully declarative, composable solution. Example. For example, if time is explicit part of tuples and manipulated using arithmetic, a user can add arbitrary arithmetic operations to the start and end points of a rule (P (S; E) → R(S + 5; E + 5) or P (S; E) → R(S ∗ S; E + 5)). { RQ3: Optimizability. Temporal data often has the property of staying the same for a longer interval. Yet, many temporal operations are de ned by time point. Declarative operators and implicit time already lead to a certain degree of optimizability, but any operators de ned should take into account optimizable evaluation on intervals.
We also need support for fundamental types of temporal aggregation, as e.g., required by the archetypal use cases discussed in the introduction. { RQ4: Windowed Temporal Aggregation. The ability to aggregate over a xed time window, e.g., aggregate all values across the last hour. This should at least support aggregates min, max, count, sum. { RQ5: Fixed-interval Temporal Aggregation. The ability to aggregate over a xed interval, e.g., aggregate all values from the month of April 2021.
This should at least support aggregates min, max, count, sum. { RQ6: Time Axis Aggregation. The ability to aggregate over intervals of arbitrary length, e.g., nding periods of time where values are monotonically increasing (a temporal trend in the data). This should at least support monotonic increases and decreases.
Looking at our archetypal use cases, UC2 is possible in a system that meets RQ4, UC1 in RQ5, and UC4 in RQ6. UC3 is already possible using recursion provided by Datalog, as well as, e.g., a system meeting RQ4 (it, however, would be hard to meet in a system that does not support recursion). 4
In this section, we take on the requirements for windowed and xed-interval
temporal aggregation we have laid out and introduce our core approach based
on declarative operators with implicit representation of time. In particular, we
focus on windowed and xed-interval aggregation and show e cient algorithms
extending the application of the standard non-temporal aggregations [
The rst type of aggregation we discuss are moving window aggregations (e.g.,
covering the last hour; RQ4). This form of aggregation aggregates per time point
t all the facts that have been valid between t−w and t, where w is some arbitrary
window size. For this, we build upon DatalogMTLFP. Our basic approach is using
the x operator to extend the time validity of facts to size w and then applying
the non-temporal aggregation operation [
Semantics. Let us continue by de ning the semantics of the newly introduced
rules. For this, we de ne the semantics on top of regular aggregation in
Datalog [
M; t ⊧ x = aggr (P ( 0; 1; a))
if = {P ( 0; 1; a) → AggrResult ( 0; aggr⟨a; 1⟩)} and S = {P ( ) S M; t ⊧ (x) ∈ {u S AggrResult( 0; u) ∈ R}
P ( )} and R = Eval (S; ) and where stands for the sequence of terms ( 0; 1; a), AggrResult is a predicate storing the aggregation value, and Eval returns the sets of facts resulting from the evaluation of on S, using the regular aggregation in Datalog. Example. Let us show the bene ts of using native temporal operators by expressing UC2 in DatalogMTL extended by monotonic aggregation. Rule 1 extends the interval of Trade facts to one hour (assuming a time granularity of seconds) and Rule 2 applies the count operation, using the trader account u as the group-by term and a unique identi er id as the contributing term, to derive the number of trades for each time point.
x[0;3600)Trade(u; id) → TradeInterval(u; id) m = mcount (TradeInterval(u; id)) → NumberOfTrades(u; m) (1) This example immediately highlights the visual and usability advantages of using temporal operators. Note that we have provided a formulation using nontemporal Datalog in the Appendix, underpinning the highly increased readability of this version.
Algorithm. The application of the rules follows the standard chase procedure
used with Datalog [
Our algorithm for time point aggregation extends existing temporal Datalog derivation rules as follows. Let x = aggr (A( 0; 1; a)) → B( 0; x) be an instance of a rule of form 4. We apply Algorithm 1 to derive a set B of facts in the form @ . The algorithm takes as input the type T of the aggregation (e.g., min, max, etc.), the aggregation predicate A, and a number of group-by terms g; it returns as output a set of facts B with arity g + 1, where the rst g terms are the group-by terms followed by the aggregated value. Line 1 de nes a map, whose key is the group-by clause and the value is an ordered set (per time-interval) of the current aggregation values, which, by construction of the algorithm, can contain only non-overlapping time intervals. Line 2 de nes a similar map, storing the intermediate results of speci c contributor terms. Line 3 iterates over all currently derived facts ltered by the matching predicate name. Lines 4-6 extract the relevant properties of the fact and retrieve the current sets for the provided keys. In particular, the function getData maps the rst g terms to the Algorithm 2: Update List for Temporal Aggregation groupByKey , the last term to a and the remaining terms to the cKey (contributor Key). Then the algorithm branches depending on the aggregation type. For instance, we continue with Line 7 for monotonic minimum, Line 9 for monotonic maximum, or with Line 11. In case of min or max (Line 7-10) we can directly update the nal result whereas for count and sum, we rst calculate the highest value per contributor (Line 11). Since such value may increase over time, in order to avoid full recomputation, we just consider the di erence with respect to the previous contributor value for a certain interval (Lines 13-14). At the end (Lines 14-16) we iterate over the lists and call mergeAdjacentInterval, which as the name says merge non-overlapping adjacent intervals with the same value to reduce the list size and write the resulting intervals back to the storage. Line 17 returns all output facts of the algorithm (that is, it removes the required grouping for the calculation).
The UpdateList function is detailed in Algorithm 2. It iterates over a list of intervals and updates it with the new values. In case the interval list is empty, it just adds the interval (Lines 3-6), otherwise it searches for the rst interval starting after the interval to be inserted (Line 10). It then checks whether there is some interval to be inserted before the current interval (Lines 14-17), modi es the boundaries of the current entry in case the interval starts or ends in this entry (Lines 18-23), and updates the value of the current entry (Lines 24-27). Having reached the end of the list or an interval that is after the insertion range (Lines 10-12), it adds the remaining interval to the list (Lines 28-30).
Note that storing the aggregation result enables an e cient incremental approach in the algorithm, so that in further applications of the derivation rules, only partial \delta-updates" are computed. For this reason, we skip the initialization of the global variables and keep the current values. In addition, in Line 3 we do not check over all facts, but only over the newly derived ones. We use the function symbols prec and succ to reference the preceding (resp. succeeding) interval points and use them to harmonise the interval endpoints. Theorem 1. Algorithm 1 has worst-case runtime O(n2) and worst-case memory consumption O(n), where n is the number of facts contributing to the aggregation. The output has maximum size O(n).
Proof Sketch. We now show the basic idea behind the complexity of the algorithm. The interested reader can nd the full proof in the Appendix. The O(n) space requirement depends only on UpdateList. In particular, we argue that at most 2n intervals are created in the process of adding n intervals to the list.
This follows from a rather technical argument, but can be intuitively grasped as follows: Let denote an inserted interval. Our interval can intersect at its left endpoint ( −) one interval from the current list (and, importantly, at most one such interval, as maintaining non-overlapping intervals is central to the algorithm). In this case we need to split , creating a total of two new intervals: we replace by the interval − to −, create a new interval from − to +, and another new interval one from + to +. Multiple other variants are possible. The interesting part is when our newly inserted interval intersects more than one interval, in which, intuitively speaking it uses \budget" stemming from earlier inserts that necessarily have not used their full \budget" of two inserts. As mentioned before, the full, technical argument can be found in the Appendix.
The runtime of O(n2) descends from the fact we iterate over all facts, and for each fact the UpdateList is performed, taking O(n) time. Since both changes and aggrVals are sorted lists, they can be scanned together within a one-pass iteration, hence keeping linear complexity (intuitively, like in the usual merging of sorted lists).
We now show soundness and completeness of Algorithm 1, i.e., that every interval produced by the semantics is also derived by the algorithm, and the other way around, every interval derived by the algorithm is also produced by the semantics. Note that this is in the context of the facts that are input of the algorithm. As discussed earlier we consider recursive derivation in the Appendix.
Proof Sketch. We now show the basic idea behind the soundness and completeness of the algorithm. The interested reader can nd the full proof in the Appendix. Soundness requires to retrieve the best (e.g., min, max, highest) value for derived intervals. This is trivially achieved by Line 24 of UpdateList. Completeness requires that all intervals are derived. Since possible overlapping intervals at the start and end are split (Line 18-23), missing intervals before an entry are inserted (Line 14-17) and missing intervals after the last entry are added (Line 28-30), all possible intervals are created. 4.2
The next type of aggregation we discuss are xed interval aggregations (e.g.,
per month). In comparison to moving windows, we cannot rely on temporal
operators provided by DatalogMTL due to di erent lengths, e.g., months vary
between 28 and 31 days. Therefore, we introduce an additional operator that
extends intervals to their complete unit of interest, e.g., an interval from the
15th of March to 17th of April to the 1st of March to the 30th of April. Such
kinds of operators have been successfully applied in the context of temporal
databases (cf., Bettini et al. [
Syntax. Let us start by formally de ning the new operator. For this, we extend the DatalogMTLFP normal form with an additional rule of the following form: (5) (1) (2) △unit P1( 1) →P0( 0) where △ is the new time extension operator and unit is a time unit, e.g., day, month, or year.
Semantics. The semantics of the operator △ is de ned as follows: M; t ⊧ △unit A
A for some s with conv(t; unit) = conv(s; unit) where conv converts the time point to the provided time unit. For example, the date 31.12.2020 with unit year, would be converted to 2020.
Example. Let us demonstrate the xed interval aggregation by expressing UC1. Rule 1 extends the interval of the sales to its corresponding year and Rule 2 applies the sum operation, using the id (and price) as contributing terms, to derive the revenue of the year.
△yearSale(id; price) → YearSale(id; price) m = msum(YearSale(id; price)) → Revenue(m) Derivation Rule. In order to handle such rules in the chase procedure, we use the following derivation rule: If △u → is a ground instance of a rule, and @ 1 ∈ F , then add @ to F where = [a; b), where a = conv(conv( 1−; u); u2), b = conv(conv( 1+; u) + 1 u); u2) and u2 is the initial unit of 1, i.e., the time unit gets converted back to the precision of the predicate, e.g. 2021-02-16 with a precision of month gets after the inner conversion 2021-02 and after applying the outer conversion 2021-02-01.
Limitations. We brie y want to discuss the limitations of this approach. The main goal of using the extension of intervals is keeping compatibility with DatalogMTL and its interval semantics by calculating the aggregates over the interval boundaries asked in the query. However, using such an approach limits the possibility to answer queries that require changing time granularity, like in the following example where we wish to compare the revenue on a weekday basis. For such requirements, we suggest the introduction of unwrapping operations that map the timestamp to an appropriate representation in usual Datalog, e.g., by introducing rules of the form Sale(id; price)@t → SaleEscaped (id; price; weekday(t)). A detailed discussion of such rules is out of scope for this paper. 5
So far, we have focused on aggregations which work per time point. In this section, we now move to aggregations along the time axis. As introduced in UC4 and RQ6, this means we need to summarize values changing over time considering adjacent intervals. One such function, which we study in detail in this paper, is the one detecting whether a trend is monotonically increasing/decreasing over time. Let us call it minc resp. mdec. This is e ective in many domains, e.g., that of change of control we have introduced, but also for example population counts. We rst start with an example and consider the desired formulation. Example. Assume that we want to detect changes of control described in UC4. Then, we are interested in nding the time intervals in which the number of shares has been monotonically increasing as well as the minimum and maximum values in those intervals. Assume now that the atom Shares(p; c; s) represents the number of shares s that an investor p owns of a company c. Rule 1 shows the minc operator in action. It takes as argument the number of shares, groups them by investor and company and returns as output the lower bound (i.e., the leftmost value) and the upper bound (i.e., the rightmost value) per monotonically increasing interval.
⟨l; u⟩ = minc(Shares(p; c; s)) → SInc(p; c; l; u) Similar to the previous section, we (i) provide a normal form (syntax) for time axis aggregations, (ii) specify the semantics of each time axis aggregation, (iii) provide a derivation rule, and (iv) suggest an algorithm for time axis operation. Syntax. We start by providing a normal form (actually already used in Rule (1), generalizing the normal form introduced for time point aggregation: ⟨x⟩ = aggr(P1( 0; 1; a)) → P0( 0; x) (1) (6) Functor aggr is the name of the time axis aggregation, in our case minc or mdec, and P1 and P0 are predicates. Like in time point aggregation, 0 de nes the group-by clause, 1 the contribution terms, not directly used in this form of aggregation but kept for uniformity reasons, and a is the aggregation term of P1. Over time, there can be multiple values of interest, for example the start and end value of a monotonically increasing interval. Hence, the function returns a vector x = x1; : : : ; xn of aggregation values instead of a single value. For minc and mdec we use x = l; u to denote the lower and upper bound of the monotonic interval.
Semantics. We assume that the domain of temporal aggregation is that of disjoint intervals, and so, for a single group-by key, no ambiguity arises w.r.t. the aggregation term. Also, this makes time axis aggregation fully orthogonal to time point aggregation, where, instead, intervals are combined. Also, time point aggregation can be e ectively used to disambiguate values per time interval (e.g., by considering their maximum/minimum resp. the summation) before proceeding with time axis aggregation. Another e ect of such disjoint intervals is that the semantics of time axis aggregation can be easily formulated by moving from time points to time intervals, i.e., M; ⊧ if for all t ∈ it holds that M; t ⊧ . ⊧ ⟨l; u⟩ = minc(P1( 0; a)) if M; ⊧
M (P1; 0; l; u) M; M; ⊧ M; ⊧
M (P1; 0; a; a) M (P1; 0; l; u) if M; ⊧ P1( 0; a) if M; 1 ⊧
M; 2 ⊧
M (P1; 0; l; u1) and
M (P1; 0; l2; u) and u1 ≤ l2 and + 1 ≺ 2− and = 1 ∪ 2 where ≺ is the predecessor relation (i.e., the intervals are adjacent), M a fresh predicate for deriving minc. In short, the second de nition states that a value constant in an interval is both lower and upper bound, and the third one merges two intervals if their lower and upper bounds match. The semantics for mdec is analogous, with u1 ≤ l2 changed to u1 ≥ l2.
Derivation rule. Let us now introduce our derivation mechanism. For each instance ⟨x⟩ = aggr (A( 0; 1; a)) → B( 0; x) of a rule of form 6, where aggr is minc or mdec and 1 is the empty set, apply Algorithm 3 to derive a set B of facts of the form @ , where contains the group-by values and the aggregation values l and u.
Algorithm. Like for time point aggregation, we provide an e cient algorithm for minc and mdec which uses the bene ts of native temporal operators. Algorithm 3 takes as input the aggregation predicate A and a number of group-by indices g; it returns as output a set of facts B. Line 1 de nes an empty map for the result, where the keys are the group-by terms and the values are B-trees with the intervals as key of the entries. Then for each fact, we add the fact to the appropriate group-by clause (Lines 3-5). We then merge the inserted fact (Line 7-12) with their adjacent intervals, if they exist, so that we derive the largest possible, monotonically increasing interval. For deriving monotonically decreasing intervals, the comparison operator in Lines 7 and 11 has to be changed from ≤ to ≥. Line 13 returns all output facts of the algorithm (that is, it removes the required grouping for the calculation). Note that, similarly to Algorithm 1, delta-updates can be applied by skipping Line 1 of the algorithm. Theorem 3. Algorithm 3 has runtime O(nlog(n)) in the worst case and worstcase memory consumption O(n), where n is the number of facts contributing to the aggregation. The output has maximum size O(n).
Proof Sketch. We show here the basic idea behind the complexity of the algorithm (details in Appendix). The space requirement of O(n) depends on the fact that at most n entries are inserted in the tree. The runtime of O(nlog(n)) is based that we iterate over all facts (O(n)), and for each fact we insert to and remove entries from the tree, which has a complexity of O(log(n)).
Proof Sketch. We show the basic idea behind the soundness and completeness regarding the maximum derived intervals (details in Appendix). Completeness follows immediately, since all intervals are inserted in the tree. For soundness we have to show that maximum intervals are derived with the correct lower and upper value. This follows by the two merging operations of possible adjacent intervals, where adjacent intervals are replaced with a new interval and the lowest value is chosen from the left and the highest value is chosen from the right interval.
First temporal extensions to Datalog were suggested already in the 1980s. Most
approaches can be grouped into two types, one focusing on implementing
temporal constructs via arithmetic operations, e.g., by applying the +1 function to
model di erent discrete temporal units (Datalog1S [
Similarly, aggregation in Datalog has been discussed for many years. The
standard Datalog xpoint semantics only works as long as rules de ne monotonic
transformations (w.r.t. set containment). Aggregation breaks this requirement.
Earlier solutions [
Apart from Datalog-speci c related work, LARS [
In this paper, we presented a solution for using monotonic aggregation over temporal Datalog fragments. This paper is, to the best of our knowledge, the rst work to include (1) full recursion as in Datalog, (2) aggregation, and (3) temporal reasoning - a combination required by important use cases as we have shown. We showed that native temporal operators allow to apply speci c optimization techniques to reduce performance overhead and memory consumption as well as increase usability. Our suggested algorithms can be executed in a nonblocking fashion (i.e., there is no need to wait for all the aggregation contributes to be available). In future work, we aim at providing a choice of experimental results showing the bene ts of using native temporal operators for monotonic aggregation.
The nancial support by the Vienna Science and Technology Fund (WWTF) grant VRG18-013 is gratefully acknowledged.
The appendix is structured as follows: In Section B we provide an extended DatalogMTL reasoning algorithm, in Section C we provide additional background information to Section 4, and in Section D we explain details for Section 5. B
In this section we present a modi ed version of the DatalogMTL reasoning
algorithm presented in [
Algorithm 4: A reasoning algorithm for monotonic aggregation over time by using DatalogMTLFP
Input: A program , a dataset S, a list of output predicates Q, a set of output intervals X (optional, if not present X = {D}), a bounded reasoning interval domain D
Output: All valid predicates, given in Q, with its intervals in D and X 1 F := S; 2 do 3 Apply rules from Table 1 exhaustively; 4 F := F ∩ D, i.e., map each P ( )@ f ∈ F to P ( )@ , s.t., = f ∩ D; 5 while F has changed ; 6 foreach P ( ) in F do 7 if P in Q then 8 P ′( ) ← P ( ) ∩ X, i.e., map each x ∈ X and P ( )@ f to P ′( )@ s.t. = x ∩ f is not empty; 9 output P ′( ); Algorithm 4 takes as input a program in normal form, a dataset S, a list of output predicates Q, optionally a set of output intervals X, a bounded reasoning interval domain D and returns as output a maximal set of facts (i.e., due to the union rule all intervals are merged, if possible). Only facts valid in the reasoning domain interval D are returned, and, if X is given, in particular, only those valid within non-empty intersection with some interval x ∈ X. De ning X as a single punctual interval allows to output all valid facts at a certain time point. Line 1 initializes the derived facts with the provided dataset. Lines 2-5 apply the rules of Table 1 to derive new facts and restrict those facts to the chosen interval domain.
{ The Horn rule adds all heads, where the intervals of the bounded body predicates overlap. (D) If x 1
where (B) If ⊟ 1
where (H) If ∧in=1 i → a ground instance of a rule and for each i i@ i ∈ F , then add @ to F with = ∩in=1 i
a ground instance of a rule, and 2@ 2 ∈ F , then add @ to F → = 1 + 2.
a ground instance of a rule and 2@ 2 ∈ F , then add
{ The Diamond rule captures the semantics of the x operator. It expands
(i.e., if 1− < 1+) the interval 2 and shifts (i.e., if 1− > 0) it into the future.
{ The Box rule captures the semantic of the ⊟ operator. It reduces (i.e., if
1− < 1+) the interval 2 and shifts (i.e., if 1− > 0) it into the future.
{ The Triangle rule captures the semantics of the △ operator. It expands the
interval to the range of the chosen unit.
{ The time Point aggregation rule captures the semantics of time point
aggregation. It applies the aggregation per time point over all facts where the
time point is in the interval of the fact.
{ The time Axis aggregation rule captures the semantics of monotonic
increasing and decreasing intervals. It applies the aggregation over the time axis
and merges adjacent intervals following the given criteria.
{ The Union rule derives new intervals based on derived facts by merging
overlapping intervals. In addition, it optimizes the storage size by removing
the old, now merged, intervals. This rule includes the deletion of subsets.
Lines 6-9 output the derived facts that are part of the list of predicates Q and
intersect with the output intervals X. Due to the union rule, each interval of
a fact in the output is not a subset of another interval of the same fact in the
output. Note that this algorithm does not terminate, in case the time point
aggregation derives no xpoint, that is for example when a recursive sum is
calculated, where additional facts are produced per application of the rule. This
is a typical issue for monotonic aggregation, which is also experienced in [
In this section we provide a non-temporal Datalog encoding of UC2 and the proofs of Theorem 1 and Theorem 2.
Trade(u; id; t) → TradeInterval (u; id; t; t + 3600; 1; 0) TradeInterval (u; id; x; y; xb; yb) → IPoint (x; xb); IPoint (y; yb)
IPoint (t ; c) → Int ′(0; mmin(t); 1; c)
Int ′(x; y; 1; 0) → Int (x; y; 1; 1)
Int ′(x; y; 1; 1) → Int (x; y; 1; 0) Int ( ; tp; ; 1); IPoint (t ; c); t > tp → Int ′(tp; mmin(t); 0; c) Int ( ; tp; ; 0); IPoint (t ; c); t > tp → Int ′(tp; mmin(t); 1; c)
Int ′(x; y; 0; 0) → Int (x; y; 0; 1)
Int ′(x; y; 0; 1) → Int (x; y; 0; 0)
Note that Rules 3b and 3c complete 4c and 4d Int (x; y; xc; yc); TradeInterval (u; id; st; et; sc; ec);
(x < et); (y > st); → V (u; id; x; y; xc; yc) Int (x; y; xc; yc); TradeInterval (u; id; st; et; sc; ec); UC2 in non-temporal Datalog. Figure 1 highlights the required rules for writing such an aggregation in non-temporal Datalog. In a rst step, for all four aggregation types, we calculate all interval points at which the query answer may change. We provide the calculation of such points in Rules 1-4. Rule 1 extends the Trade facts to one-hours intervals TradeInterval (i.e., the desired time of the query) and de nes that the intervals are left-closed and right-open (represented by 1 resp. 0). Rule 2 extracts all relevant interval points IPoint . Rules 3 and 4 create intervals Int between all extracted points and assign open and closed properties. Having established the relevant intervals, we continue in Rule 5 with detecting overlaps between TradeInterval and Int and assigning the values of TradeInterval to the overlapping intervals Int . In particular, this rule covers overlapping checks of all combinations of open and close intervals. Finally, Rule 6 calculates the number of trades per interval and user (so we are grouping per T radeInterval 1 2 user and time-interval). In order to support other aggregation types, we have to adapt Rule 6, where the aggregation has to be changed accordingly.
Consider Figure 2 for an example of ve Trade events already extended to one hour intervals. The ve top-most intervals denote all TradeInterval predicates. Vertical, dashed lines show all IPoint . The intervals at the bottom of Figure 2 refer to the nal result, that is, the NumberOfTrades predicates. Theorem 1 Algorithm 1 has worst-case runtime O(n2) and worst-case memory consumption O(n), where n is the number of facts contributing to the aggregation. The output has maximum size O(n).
Proof. We rst show the space requirements. For this, we consider UpdateList, which is the only part where new data is added, where we show a space requirement of O(n). Let us start with the list which in total contains at most 2n entries. There are two di erent options: (1) the list is empty, then the fact is added (Line 3-6), which creates at most one entry for a single fact, or (2) the set is not empty, then the number of added facts depend on existing facts in the list . It is clear that Line 14-17 (resp. 18-20), only re at most once, that is when the new interval to be inserted starts (resp. ends) inside an existing interval. The same applies when the interval starts or ends not in an existing interval, where Line 14-17 add the starting interval before the current entry and Line 28-30 append the ending interval after the current entry. This in total creates at most 2 new entries. It remains to show the additional rings of Line 14-17. If n entries exist in the set, there can be a maximum of n − 1 gaps. It is clear that a gap is only created when the inserted interval ts between two existing intervals, requiring only 1 new entry. So, in worst case, Line 14-17 only ll up the remaining budget of 2n entries. Let us now consider changes. In worst case, when the new interval spans over the complete list , then each entry in the list requires one changes entry, that is in total at most 2n entries. In total, this yields O(2n + 2n) = O(4n) = O(n) as the space bound. For runtime, we can build upon the space requirements. It is clearly visible that the runtime for mmin and mmax equals to the rst part of msum and mcount, i.e., the update operation of line 11 and 9 are equal for mmax or similar for mmin. Hence, we only have to consider the else part inside the outer foreach loop. For each fact (O(n)), we update the contributor set (Line 13) and then apply updates to the aggregation value (Line 15-16). We start by showing the runtime of the update for the contributor set. It is clear that UpdateList iterates once over the list, which require O(2n) times in worst case. We now consider the update process and show that we will not exceed the runtime of the updating process. We have shown that the space bound of aggrValues as well as changes is O(2n). Since those sets are ordered, we can scan both sets together within a one-pass iteration by checking the boundaries of the following intervals. Hence, we do not exceed the runtime of O(2n). The same applies to the merging operations, which iterates over the list once. This concludes the argument that the algorithm takes O(2n) = O(n) time in worst case for a single added value. Now we consider that n facts contribute to 2 . the aggregation, hence the algorithm is executed n times and thus run in O(n ) The nal attening step loops over the aggrResult of size O(2n) and maps the result to the appropriate format of the output. Hence, the output size is also at most O(n).
Theorem 2 Algorithm 1 is sound and complete.
Proof. Let us start with the soundness of the algorithm, which is trivial. We have to show that the returned results are the best result per interval, where best mean the minimal one for mmin, the maximum one for mmax, the highest sum for msum or count for mcount. This means, for each interval we have in the output list, we detected the best value. This is given by the chosen aggr-function and Line 24 of UpdateList that calculates the best value for each interval. Let us now consider the completeness of the algorithm to show that all interval rules are considered. For this, we show that we do not miss any interval in the update process, when we consider a new fact. It is clear by Line 14-17 that an interval that does not exist before a list entry, is added and by Line 28-30 that an interval that is after the last list entry or together with Line 11-13 ends after an existing list entry is added. It remains to show that also existing intervals are modi ed correctly. This is handled by Lines 18-20 if the interval starts inside another interval and Lines 21-23 if the interval ends inside another interval. The remaining part of time point algorithm does not modify the intervals, except of the merging functions, which only combine existing intervals to maximum ones, having no impact on the covering of the intervals. Hence, the algorithm is sound and complete.
D
In this section, we show the proofs of Theorem 3 and Theorem 4. Theorem 3 Algorithm 3 has runtime O(nlog(n)) in the worst case and worstcase memory consumption O(n), where n is the number of facts contributing to the aggregation. The output has maximum size O(n).
Proof. First, we show the space requirement of O(n). Each fact can be added to the tree at most once (Line 5). This state is reached, if the facts are strictly monotonically decreasing when monotonically increasing is asked. The other lines remove more facts than those added, hence the size of the list only reduces. This ends the argument of space requirement of at most O(n). This also shows the output size of O(n) of the algorithm.
Now, we show the runtime complexity of O(nlog(n)). Inserting and removing facts in a B-tree has a complexity of O(log(n)). We then consider that we have to execute this for each fact contributing to the aggregation, i.e., O(n) times. This yields a runtime complexity of O(nlog(n)).
Theorem 4 Algorithm 3 is sound and complete.
Proof. Let us start by completeness, which follows immediately. Since all values (with their intervals) are inserted in the tree, the algorithm does not miss any case. We now show the soundness of the algorithm. We show this by induction. In the base case, we add the rst interval to a group-by key, which is simply the value of the fact. We now assume that we have maximal monotonic increasing intervals and that we add another fact. Since the considered facts must have a disjunct interval by de nition, there are three cases, we have to distinguish.