Bringing Temporal Reasoning to Mangle

[danielostrow]

I'm drafting a PR #84 for a feature introducing temporal reasoning into Mangle.

Facts are stored, rules derive new facts. But currently all facts are "eternally true." Once team_member(/alice, /engineering) is added, it's true forever. There's no way to express that Alice was in engineering from 2020-2023, but is now in management.

Currently, to get historical context, you'd add start_date and end_date as extra arguments to predicates, which is messy and loses the semantic meaning of time.

I'm proposing we add an optional time dimension to Mangle's fact model, so facts can express when they were valid.

This design is inspired by DatalogMTL, an academic extension for metric temporal logic in Datalog.

We can tag facts with a time range using @[start, end]:

# Alice was in Engineering from 2020 to mid-2023
team_member(/alice, /engineering)@[2020-01-01, 2023-06-15].

# Alice moved to Management in 2023 and is still there (unbounded)
team_member(/alice, /management)@[2023-06-15, _].

# A single point-in-time event
login_event(/alice, /web)@[2024-03-15T10:30:00].

We can use new operators to ask questions about the past without complex joins.

• <-: was this true at some point in the past?
• [-: was this true continuously for the whole duration?

Example: Find employees who have been employed continuously for the last 365 days.

# The `[-` operator checks if the fact held true for the entire window
stable_employee(X) :- [-[0d, 365d] employed(X).

Use case: Compliance checking
"An employee can only operate equipment if they've been certified
for at least 30 days."

violation(Person, Equipment) :-
    operated_equipment(Person, Equipment)@[Time, Time],
    ![-[30d, 30d] certified(Person, /heavy_machinery).

All existing Mangle programs work unchanged. Facts without @[...] are treated as eternally valid (the current behavior).

I need feedback.
I am aiming for a balance between power and simplicity. Before I start submitting PR's, I'd love to open a conversation on:

The Syntax: Does fact(...)@[start, end] feel natural to write?

Granularity: Do we need sub-second precision (milliseconds/nanoseconds) for your use cases?

Missing Pieces: Are there specific "time travel" queries you need to run that this doesn't cover?

Thanks!
Daniel

[burakemir]

Thanks for starting this discussion. I need to look in more detail, but want to share a few thoughts right away.

In general, I am all for adding time to Mangle datalog and enable temporal graph reasoning in a principle manner. I agree that the option of adding time values as columns according to convention loses semantics, even though we should appreciate that convention alone does enable time-travel queries.

The syntax for intervals right, it matches the syntax used by the badwolf project which was an inspiration for Mangle. It overlaps a bit with Mangle syntax for list values [ e1, ..., en ] and map values [ k1: v1, ..., kn : vn ] but with the @ character that should be ok. The syntax of the operators is bit dense, maybe we can use suitable Unicode operators and/or box/diamond prefix, but I am sure we can figure something out.

Semantics wise, adding time to semantics exposes us to the whole topic of absolute vs civic time, dates and timezones. See https://abseil.io/docs/cpp/guides/time

It has been proposed to add time/date handling to Mangle's data model, which matches SQL. I want to carefully consider what happens when the mode of "native" handling of temporal reasoning gets mixed with some convention or date/time values appearing in source data. It's tempting to say "let's not do that" but when the language supports multiple modes it is almost inevitable that users will run into it.

Finally, I need to get an understanding for decidability and performance. Mangle already crossed the Rubicon by extending datalog with features that lead to non-terminating programs, or using fact deletion in custom-lattice without checking that the user-defined relation is actually an ordering. Still, I want to help users (or agents) avoid generating non-terminating queries and give helpful error messages where possible. Besides a working implementation that covers expected queries/programs, it would help to have a characterisation of limitations and queries that can "go wrong".

[danielostrow]

Thanks @burakemir ill convert PR #84 to a draft and update based on your feedback.

[danielostrow]

Here are my thoughts for each of the items you brought up.

Alternative syntax options:
Current in PR

<-[0d, 7d]  # sometime in past
[-[0d, 7d]  # always in past
<+[0d, 7d]  # sometime in future
[+[0d, 7d]  # always in future

could use a keyword prefix, Its self documenting but I think is a bit too verbose:

sometime_past[0d, 7d]
always_past[0d, 7d]
sometime_future[0d, 7d]
always_future[0d, 7d]

Could also use short keywords, however using ! overloads negation...:

past[0d, 7d]
past![0d, 7d]
future[0d, 7d]
future![0d, 7d]

The current implementation in the PR with [-,[+,<-,<+ operators is clean, clear and robust. just need to ensure they come first defined in the parser as to not be overridden by a singular [ or <.

---

Regarding the time model implementation, in the current PR I proposed an internal int64 nanoseconds since Unix epoch (UTC). Parsing formats: ISO 8601 dates/datetimes (2024-01-15, 2024-01-15T10:30:00Z) with all times normalized to UTC internally.

Per the Abseil (https://abseil.io/docs/cpp/guides/time) we distinguish:

Concept	Representation	Use Case
Absolute Time	int64 Unix nanoseconds	Internal storage, interval arithmetic, comparisons
Civil Time	Parsed from ISO 8601 string	User input in source files

the current behavior presented in the PR:

// ast/temporal.go - stored as absolute time
type TemporalBound struct {
    Timestamp int64  // Unix nanoseconds (absolute)
}

Timezone Handling:

Input: Timestamps without timezone suffix (2024-01-15T10:30:00) are treated as UTC
Input with Z: Explicit UTC (2024-01-15T10:30:00Z)
And we make no assumptions on local timezone.

---

so what happens when "native" temporal facts mix with date/time columns in the source data...

Here are my proposed rules:

• Temporal facts (@[start, end]) use the temporal system exclusively
• Regular columns containing time data (for example, created_at as a number) are opaque values
• Bridge functions allow explicit conversion:

# Convert column timestamp to temporal query
valid_order(Order) :-
    order(Order, CreatedAtNanos),
    fn:time:from_nanos(CreatedAtNanos, T),  # NEW: explicit conversion
    <-[30d] active(Order)@T.

• No implicit coercion, so a number column 1704067200000000000 is NOT automatically a temporal bound.

@burakemir should this support timezone-aware time input? If I add to my PR timezone support, I think the explicit syntax would be along the lines of 2024-01-15T10:30:00[America/New_York]

---

Regarding complexity results (from https://www.ijcai.org/proceedings/2019/0261.pdf, and https://www.jair.org/index.php/jair/article/view/14040)
It was found that DatalogMTL can express programs with infinite models. Forward chaining may not terminate.
The current implementation I proposed in my PR #84 is close to forward-propagating using these features:

Feature	Status	Termination Risk
Past operators (<-, [-)	Implemented	Safe - finite lookback
Future operators (<-, [+)	Implemented	Risky - can generate infinite facts
Recursion + temporal	Allowed	Risky - interval explosion
Negation + temporal	Limited	Research shows undecidable over rationals

There are some Non-terminating patterns that would come up that should throw detect/warn...

# DANGEROUS: Recursive temporal rule with unbounded future
will_happen(X) @[now, _] :- 
    trigger(X),
    [+[1d] will_happen(X).  # Generates infinite future intervals

# DANGEROUS: Self-referential interval extension  
extended(X) @[T1, T2] :-
    base(X) @[T1, T0],
    extended(X) @[T0, T2].  # Can extend infinitely

Safe patterns look like:

# SAFE: Past-only lookback, no recursion through temporal
recent_login(User) :-
    <-[7d] login(User).

# SAFE: Bounded future with no self-reference
expires_soon(License) :-
    license(License) @[_, End],
    fn:time:before(End, fn:time:add(now, 30d)).

There are safeguards that can be put in place.
Coalescing (already implemented in my PR)... we merge adjacent intervals to prevent explosion.

// factstore/temporal.go
func (s *SimpleTemporalStore) Coalesce(predicate ast.PredicateSym) error

I can add an interval count limit that throws an error if a single atom has >N intervals.

const MaxIntervalsPerAtom = 1000

Could also implement a static analysis warning that detects recursive rules with temporal heads:

Warning: Rule 'extended' has recursive temporal derivation - may not terminate

and can also include cycle detection in temporal graph that warns if temporal predicates form cycles.

---

PERFORMANCE
The current indexing strategy proposed in the PR:

// factstore/temporal.go
type SimpleTemporalStore struct {
    // Map from predicate -> atom hash -> temporal entry
    facts map[ast.PredicateSym]map[uint64]*temporalEntry
    atoms map[uint64]ast.Atom
}

type temporalEntry struct {
    intervals []ast.Interval  // Linear scan for now
}

Query complexity:

Operation	Current Complexity	Notes
GetFactsAt(atom, t)	O(predicates × atoms × intervals)	Linear scan of intervals
GetFactsDuring(atom, interval)	O(predicates × atoms × intervals)	Linear scan with overlap check
Add(atom, interval)	O(1) amortized	Hash map insertion
Coalesce(predicate)	O(n log n) per atom	Sort + merge

Operator Complexity:

Operator	Algorithm	Complexity
<- (diamond-minus)	Scan facts overlapping query window	O(facts × intervals)
[- (box-minus)	Scan facts, check containment	O(facts × intervals)
<+/[+ (future)	Same as past operators	O(facts × intervals)

Coalescing behavior:

Adjacent intervals are merged:
[1, 5] + [5, 10] → [1, 10]
[1, 5] + [4, 10] → [1, 10]  (overlapping)
[1, 5] + [7, 10] → [1, 5], [7, 10]  (gap preserved)

To optimize I want to add to my PR proposal Interval tree indexing that replaces the linear interval list with a tree for O(log n + k) queries. will also add time bucketed index where we partition intervals by time buckets for faster range queries. Also looking into materialized coalescing for options during insertion vs. on demand... and bitmap indexing for predicates with many boolean like temporal facts.

[danielostrow]

@burakemir I opened PR #84 back up for a review after making some changes. I think my feature addition is incredibly useful and adds a powerful benefit natively to mangle.

[burakemir]

Thank you for the temporal reasoning PR (#84) - implementing DatalogMTL for Mangle is a great contribution!

While reviewing the PR, I noticed an opportunity to simplify the implementation by adding first-class time and duration types to Mangle's core. I've implemented this foundation, which includes:

New built-in types:

• Time - instant in time (int64 nanoseconds since Unix epoch UTC)
• Duration - time span (int64 nanoseconds)

New predicates:

• :time:lt, :time:le, :time:gt, :time:ge - time comparisons
• :duration:lt, :duration:le, :duration:gt, :duration:ge - duration comparisons

New functions:

• fn:time:now, fn:time:add, fn:time:sub, fn:time:format, fn:time:parse
• fn:time:year, fn:time:month, fn:time:day, fn:time:hour, fn:time:minute, fn:time:second
• fn:time:from_unix_nanos, fn:time:to_unix_nanos
• fn:duration:from_hours, fn:duration:from_minutes, fn:duration:from_seconds, fn:duration:from_nanos
• fn:duration:hours, fn:duration:minutes, fn:duration:seconds, fn:duration:nanos
• fn:duration:add, fn:duration:mult

I have this under review and expect to land this very soon (in the next days) - once landed would you mind rebasing your DatalogMTL implementation on top of this? It should allow you to remove custom time handling code and use the built-in facilities instead, making the temporal reasoning logic cleaner.

A notable difference is the handling of durations. The work on parsing time and duration literals is important and needs some scrutiny. Would it be possible to split the parsing of time and duration values into a separate PR so I can review it separately?

I would like to ask for the following: while for a duration datatype, it makes sense to support negative durations, it clearly does NOT make sense for DatalogMTL. So in the context of temporal queries/goals, we should detect and reject the use of negative durations, and document clearly that the operator determines direction.

Duration Literal Grammar (EBNF)

duration = [ sign ] component { component } ;
sign = "+" | "-" ;
component = number unit ;
number = digit { digit } [ "." digit { digit } ] ;
unit = "h" | "m" | "s" | "ms" | "us" | "µs" | "ns" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Examples

  ┌──────────┬───────────────────────────────┐                                                                                                                                                                  
  │ Literal  │            Meaning            │                                                                                                                                                                  
  ├──────────┼───────────────────────────────┤                                                                                                                                                                  
  │ 1h30m    │ 1 hour 30 minutes             │                                                                                                                                                                  
  ├──────────┼───────────────────────────────┤                                                                                                                                                                  
  │ 2h45m30s │ 2 hours 45 minutes 30 seconds │                                                                                                                                                                  
  ├──────────┼───────────────────────────────┤                                                                                                                                                                  
  │ 500ms    │ 500 milliseconds              │                                                                                                                                                                  
  ├──────────┼───────────────────────────────┤                                                                                                                                                                  
  │ 1.5h     │ 1 hour 30 minutes             │                                                                                                                                                                  
  ├──────────┼───────────────────────────────┤                                                                                                                                                                  
  │ -30m     │ negative 30 minutes           │                                                                                                                                                                  
  ├──────────┼───────────────────────────────┤                                                                                                                                                                  
  │ 100ns    │ 100 nanoseconds               │                                                                                                                                                                  
  └──────────┴───────────────────────────────┘                                                                                                                                                                  
  Units (descending)                                                                                                                                                                                            
  ┌──────────┬──────────────┐                                                                                                                                                                                   
  │   Unit   │   Meaning    │                                                                                                                                                                                   
  ├──────────┼──────────────┤                                                                                                                                                                                   
  │ h        │ hours        │                                                                                                                                                                                   
  ├──────────┼──────────────┤                                                                                                                                                                                   
  │ m        │ minutes      │                                                                                                                                                                                   
  ├──────────┼──────────────┤                                                                                                                                                                                   
  │ s        │ seconds      │                                                                                                                                                                                   
  ├──────────┼──────────────┤                                                                                                                                                                                   
  │ ms       │ milliseconds │                                                                                                                                                                                   
  ├──────────┼──────────────┤                                                                                                                                                                                   
  │ us or µs │ microseconds │                                                                                                                                                                                   
  ├──────────┼──────────────┤                                                                                                                                                                                   
  │ ns       │ nanoseconds  │                                                                                                                                                                                   
  └──────────┴──────────────┘                                                                                                                                                                                   

Notes

• Components are additive: 1h30m = 1h + 30m
• Order conventionally descending but not required
• Decimals allowed: 1.5h equivalent to 1h30m
• Zero duration: 0s or 0
• Go's time.ParseDuration() can be used directly for implementation

This is the exact format Go uses, so the implementation can simply delegate to time.ParseDuration().

[danielostrow]

@burakemir I like this and will keep a look out for your implementation. Once your core implementation is accessible by me I will rebase my PR and split for an easier review.

either message me, or tag me so I can get notice and I should have the work done very soon after.

[burakemir]

@danielostrow The time and duration types landed, see dd902ac

[danielostrow]

Amazing. @burakemir i'm on it. give me a few hours for a substantial rebase.

[danielostrow]

@burakemir #84 is dependent on #87. ready for review.

[danielostrow]

@burakemir the temporal graph is great stuff. Mangle is looking very attractive to use in a few of my projects.

I’m very much interested in feedback from users. Do you suggest updating the main project readme to share this feature?

[burakemir]

Added a section to README, see here: https://github.com/google/mangle?tab=readme-ov-file#temporal-knowledge-graphs