# Temporal database reconstruction in mathematica

<EDIT> after some internet research I found the database domain that deals with this kind of thing: Temporal Databases. I think my question therefore becomes how to reconstruct a temporal database in mathematica, so I've retitled my question as such. Note that TemporalData doesn't do this trick directly, although it might play a role in a possible solution. </EDIT>

<EDIT2> I've come across Indexing temporal data using existing B+ trees and it appears to be a very interesting way of modeling this dataset. I think simple enough that I could probably hack it together in Mathematica :)</EDIT2>

I am trying to reconstruct the history of a bug tracking system, and what I have access to is an event log that describes a snapshot of the bug state each time an attribute changed. But I think you could encounter this style of problem in many other kinds of system or data collected from almost anywhere.

Needs["GeneralUtilities"]
ds = Import["https://gist.githubusercontent.com/lburton/fb01b7c693c4e294dd37/raw/a74bf793c2e4c184488aa7ee71c39d325de21922/gistfile1.json","JSON"] // ToAssociations // Dataset


This is of course obfuscated data. I wish to ask questions like "count the number of bugs that were open each day" so I can draw a graph of open bugs over time.

Since this is an event log, there are holes in the data. I can't just ask for the open bugs on a particular date, I need to somehow reconstruct the state of all bugs for any given day.

I've solved this one way in Mathematica, but as I worked on the problem I had the uncomfortable feeling that I was probably re-implementing a data structure someone had already labored on to perfection. However, I couldn't find anything in Mathematica that seemed to specifically solve the problem (maybe SparseArray?) I ended up using Dataset and lots of filtering and munging.

My question is therefore: how would you solve it? Here's the approach I've used.

Firstly, group the event data by the unique identifier for the bug. Then, apply two functions to the grouped event data:

eventData = ds[GroupBy[Key["bug_id"]], FindEvents /* EventsToDateRange];


FindEvents searches through the events for each bug id looking for "start" and "stop" events of interest. In my case I have a hard coded interest in when the bug became "open" and when it became "closed". The case of an odd number of results implies the bug has not yet transitioned to a "closed" state and therefore is considered open on today's date.

FindEvents[rows_] := Module[{events},
events = Last@Reap[Fold[MatchEvents, <| |>, SortBy[rows,Key["timestamp"]]]] // Catenate;
If[OddQ[Length[events]],AppendTo[events,<| "timestamp" -> AbsoluteTime[] |>]];
events];


The MatchEvents function that I'm Fold-ing over detects "start" and "stop" events and Sows them (note that I don't actually use the tags)

MatchEvents[previous_,current_] := Module[{foundStart,foundStop},
foundStart =
(current["state"] == "Open")&&
(Length[previous] == 0 ||  previous["state"] != "Open" );
If[foundStart, Sow[current,start]];

foundStop =
(current["state"] !=  "Open") &&(previous["state"] ==  "Open");
If[foundStop, Sow[current,stop]];
current];


Finally, now that we have "start" and "stop" events, I can interpolate a date range across them.

EventsToDateRange[events_] :=
Apply[DateRange] /@ Partition[( Take[Normal@DateList[#timestamp], 3] & /@ events), 2];


Now we have, for each bug_id, a single date entry in a list for each day that bug was marked as "open". All I do then is Flatten, Normal, Tally, and plot 'em:

Flatten[eventData // Values // Normal, 2] // Tally // DateListPlot


This produces the following plot. Note that in my zealousness to generate real-ish fake data and remove proprietary clutter from my code, this graph is slightly wrong. It should drop down to zero. I have not yet investigated what broke.

A generalized solution would be able to be given a date (or date range) return the state of all bugs known to exist on that date (i.e. omitting bugs not yet created). It could then have basic predicates and functions applied to it (state = open, length)

I have some other solutions in mind, but I'd much rather spend time analyzing the data I've been asked to analyze, hence my appeal for ideas here. Pursing the implementation of a generalized solution when your business doesn't need one is a trap for young players I'm trying to avoid, since I'm now anything but young ;)

• It would help if you provide some sample data, and a few sample specific queries you'd like to do, in addition to this general description. The set of sample queries would ideally cover the use cases you have in mind reasonably well. You are then more likely to get more people interested in answering. – Leonid Shifrin Sep 29 '14 at 18:40
• Agreed! I can absolutely provide sample data and some code, look for it later on today. – Hagmonk Sep 29 '14 at 19:13
• In DB parlance you've what is known as an "after image journal". Perhaps the name may help your internet/book search – Dr. belisarius Sep 29 '14 at 22:03
• take a look at TemporalData – kglr Sep 30 '14 at 0:03
• @kguler - I looked at TemporalData, but could not find any way to control the interpolation function. I went through he documentation pretty exhaustively. If I could insert my own function there, I agree, it could be very interesting. – Hagmonk Sep 30 '14 at 17:31

It's not clear to me whether you're looking for general insight into this data or to develop specific analytical queries.

But here's a barebones forest-for-the-trees graphical overview of the state changes which you could use to refine your questions, such as what metrics are relevant (eg median time to close a ticket vs number of times it's still open in a row)

eventColor = <|"Open" ->  Red, "Reviewing" -> Yellow,
"Fixing" -> Orange, "Verify" -> Blue, "Closed" -> Green|>;


.

eventColor // Normal // Map[Reverse] // Column // Panel


.

With[{timeRange = Normal@ds[Query[{Min, Max}], "timestamp"]},
ds[GroupBy[Key@"bug_id"], All, {"timestamp", "state"}][All,
SortBy[Key@"timestamp"]][SortBy[First /* "timestamp"]][
KeyMap[Style[#, Small] &] /*
Normal /* (Column[#, Spacings -> -1] &),
Map[{eventColor[#state] ,
Point[{#timestamp, 0}]} &] /* (Graphics[{PointSize[0.01], #},
PlotRange -> {timeRange, {-1, 1}} , AspectRatio -> 1/30,
ImageSize -> 600, Axes -> {True, False}, Ticks -> False] &)]
]


• This is fantastic, thanks for this … I missed all the email notifications so I apologize for not seeing your reply earlier! – Hagmonk Oct 22 '14 at 5:25
• @Hagus, thanks - let me know if you're looking for more specific improvements on this. – alancalvitti Oct 25 '14 at 21:48
• @Hagus, if you like my solution you can "accept" it by clicking the checkbox below the vote counter. – alancalvitti Dec 11 '14 at 15:33
• Thought I accepted this a long time ago, apparently I did not! Better late than never. – Hagmonk Apr 26 '15 at 22:12
• @Hagus, thanks, you may also find this interesting: mathematica.stackexchange.com/a/72483/801 – alancalvitti Apr 27 '15 at 17:08

Ok, here's an answer to my own question based on the paper by Cheng Hian Goh, et al. There doesn't seem to be any pre-canned data structure in mathematica that supports this, perhaps it's an enhancement request for the future. Therefore this answer is really just my favorite solution so far (that doesn't involve round tripping to an external database).

The general idea is that you build an index of the events that makes lookups cheap and reliable. You define a mapping function that, given your event, produces a tuple of the start time and the duration. A fun side effect is that queries become quite easy to visualize in simple plots!

Firstly, I refined MatchEvents. It now uses Split to group events together. To measure a transition from one state to the next, simply find a block of events you're interested in (in my case state = open), and take the first time within. This is your start. The next block of events represents a different state, so the first event within that block is your end time. In the event of no ending block, use the current time.

MatchEvents[events_] := Module[{sortedAndSplit, startStop},
sortedAndSplit = Split[Sort[events, #1["timestamp"] < #2["timestamp"] &],
#1["state"] == #2["state"] &];
startStop = Partition[sortedAndSplit, 2] //
Select[#[[1, 1]]["state"] == "Open" &] //
Map[{#[[1, 1]]["timestamp"], #[[2, 1]]["timestamp"]} &] //
Map[{#[[1]], DateDifference[#[[1]], #[[2]], "Second"]} &];

If[OddQ[Length@sortedAndSplit],
With[{openEvent = sortedAndSplit[[-1, 1]]},
If[openEvent["state"] == "Open",
AppendTo[startStop,
{AbsoluteTime@openEvent["timestamp"],
DateDifference[openEvent["timestamp"], DateList[], "Second"]}]]]
];
Return[startStop];
];


Now run MatchEvents across the events for each bug_id. This produces our mapping to [time,duration] tuples.

eventData = ds[GroupBy[Key["bug_id"]], MatchEvents] // Normal // Values // DeleteCases[{}];


In the paper, there are some nice graphics that help emphasize how easy it is to do lookups for dates or date ranges. Here's my sample data plotted in a similar fashion.

flattened = Flatten[eventData,1];
minTime = Min[flattened[[All,1]]];
maxTime = AbsoluteTime[];
maxDuration = maxTime-minTime;

Show[
DateListPlot[flattened,
Joined->False,
PlotRange->{{minTime,maxTime},{0,maxDuration}}],
DateListPlot[{{minTime,maxDuration},{maxTime,0}},
Joined->True,
PlotStyle->Red],
Graphics[Inset[Rotate[Style["Future",15,Bold,Red],-45 Degree],{minTime + maxDuration/1.8,maxDuration/1.8},{Center,Center}]],AspectRatio-> 1/1]


The red line represents now, and anything on its right hand side is the future. Tuples plotted on the red line are bugs still open.

So now things get pretty easy! To find the bugs open on a particular date, we simply need to find bugs with events starting prior to our date of interest, but whose duration indicates they ended after that date. There's a nice plot of this I could replicate from the paper but I'm short on time. Here instead is the query to get the tuples and the plot that results.

FindEvents[inDate_] :=
Module[{date = AbsoluteTime[inDate]}, {date,
Length@Select[flattened,
First[#] < date && (#[[1]] + #[[2]][[1]]) > date &]}];

FindEvents /@ DateRange[ minTime, maxTime, "Day"] // DateListPlot


You can adjust the DateRange step down to Minutes or Hours, but that reveals even for small datasets the inefficiency of scanning the entire data set with Select for each block of time. I have not spent any time improving this as yet, but would definitely like to hear suggestions for the best approach.

• ds[Tally, "state"][SortBy[#[[2]] &]] shows {{"Closed", 134}, {"Reviewing", 142}, {"Fixing", 164}, {"Verify", 262}, {"Open", 520}}`. These distinctions aren't reflected in the above analysis. Are you interested in statistics like latency distribution b/w state changes (eg "Open"-->"Closed")? – alancalvitti Oct 10 '14 at 17:33
• @alancalvitti yes one of the next areas of investigation is exactly this. The most basic metric is "how many issues do you have Open?" since the project by definition (well, our definition) cannot be considered "done" while issues are unresolved. But not long after that you start wanting to know how long issues take to close, the rate at which they bounce back to Open from Verify, whether the Open issues count is increasing because fix rate has gone down or because new issues are pouring in, etc. So your graph below is a great visualization to help consider these metrics! – Hagmonk Oct 22 '14 at 5:31