Allen's Interval Algebra

The Before relation (and its inverse After) describes two intervals where one ends before the other begins. There is a temporal gap between them.

• Notation: X before Y or X < Y; Y after X or Y > X.
• Example: A project's planning phase (Interval A) ends on Friday. The execution phase (Interval B) starts the following Monday. A before B.
• Key Property: The relations are converse of each other. If A before B, then B after A.

The Meets relation describes two intervals where one ends exactly when the other begins. There is no gap and no overlap.

• Notation: X meets Y or X m Y; Y met-by X or Y mi X.
• Example: A one-hour meeting ends at 3:00 PM. A subsequent meeting begins at 3:00 PM. The first meeting meets the second.
• Key Property: This is the fundamental relation for modeling contiguous events or processes in schedules and workflows.

The Overlaps relation describes two intervals where one starts before the other, and they share a common period before the first one ends.

• Notation: X overlaps Y or X o Y; Y overlapped-by X or Y oi X.
• Example: A software development sprint (Interval A: weeks 1-4) and a quality assurance phase (Interval B: weeks 3-6). A overlaps B.
• Key Property: This is a common relation for modeling concurrent, interacting processes with partial temporal alignment.

The Starts relation describes two intervals that begin at the same instant, but the first interval ends before the second.

• Notation: X starts Y or X s Y; Y started-by X or Y si X.
• Example: A temporary promotional discount (Interval A: Jan 1 - Jan 15) begins on the same day as a quarterly sales period (Interval B: Jan 1 - Mar 31). A starts B.
• Key Property: Useful for modeling sub-events or conditions that are initiated simultaneously with a larger containing event.

The During relation describes an interval that is completely contained within another, with different start and end times.

• Notation: X during Y or X d Y; Y contains X or Y di X.
• Example: A employee's two-week vacation (Interval A) occurs entirely within the third fiscal quarter (Interval B). A during B.
• Key Property: This is the primary relation for modeling hierarchical or nested temporal structures, such as events within a timeframe.

The Finishes relation describes two intervals that end at the same instant, but the first interval starts after the second.

• Notation: X finishes Y or X f Y; Y finished-by X or Y fi X.
• Example: A final project milestone review (Interval A: last 3 days of March) concludes at the end of the month, coinciding with the end of the monthly reporting cycle (Interval B: entire month of March). A finishes B.
• Key Property: Models events that culminate or terminate simultaneously with a larger containing interval.

The Equals relation describes two intervals that share identical start and end times. They are temporally coincident.

• Notation: X equals Y or X = Y.
• Example: A scheduled server maintenance window is defined as 2:00 AM to 4:00 AM. The recorded downtime for the server is also from 2:00 AM to 4:00 AM. The scheduled window equals the recorded downtime.
• Key Property: This relation is its own converse and is symmetric. It is crucial for data reconciliation and verifying temporal alignment between different records of the same event.

Allen's relations are used to infer missing temporal facts within a Temporal Knowledge Graph (TKG). By applying the algebra's transitivity rules, a system can deduce that if Event A overlaps Event B, and Event B is during Event C, then Event A must overlap or be during Event C. This enables Temporal Knowledge Graph Completion (TKGC) models to predict not just what happened, but when it happened relative to other known events, filling gaps in historical records.

In Event Graph architectures, Allen's 13 relations serve as the primary edge types connecting interval-based events. This creates a rich, queryable structure for complex temporal narratives. For example:

• A manufacturing process meets a quality inspection.
• A server outage overlaps with a maintenance window.
• A financial transaction is before an audit cycle. This modeling is central to the Event Sourcing Pattern, where the sequence and relationships of immutable events define system state.

Specialized Temporal Reasoning Engines implement Allen's algebra to answer complex queries over time-varying data. These systems power:

• Temporal SPARQL extensions that allow queries like "Find all contracts that were active during the 2023 fiscal year."
• Consistency checking to ensure no logical contradictions exist in scheduled events (e.g., a task cannot start before and finish after its prerequisite).
• Temporal Fact Checking by verifying if a claimed sequence of events (e.g., "X happened after Y") is consistent with the known graph.

Allen's algebra formalizes scheduling and planning as Temporal Constraint Satisfaction Problems (TCSPs). Each interval (e.g., a task, a meeting, a machine operation) is a variable, and the allowed relationships between them are constraints. A solver finds a consistent global arrangement, enabling applications in:

• Autonomous Supply Chain Intelligence: Scheduling shipments where loading meets transit, which overlaps with customs clearance.
• Clinical Workflow Automation: Ensuring a patient assessment is before treatment, which is during a hospital stay.
• Smart Grid Optimization: Coordinating maintenance windows that must be before peak demand periods.

Temporal Knowledge Graph Embedding (TKGE) models, such as TA-TransE or TeRo, incorporate Allen's relations into their learning objective. Instead of treating time as a simple timestamp, these models learn vector representations that encode how entities interact over specific intervals. This allows machine learning models to perform Temporal Link Prediction, forecasting not just if a relationship will form, but the qualitative temporal context (e.g., will Project Beta start after Project Alpha concludes?).

Temporal Knowledge Graph Question Answering (TKGQA) systems use Allen's algebra to parse and reason over natural language questions involving time. For example, the question "What ongoing initiatives overlapped with the CEO's tenure?" requires the system to:

1. Identify the interval for "CEO's tenure."
2. Find all "initiative" intervals.
3. Apply the overlaps relation filter. This enables Multi-Document Legal Reasoning to establish timelines of case law or Biomarker Identification Systems to correlate treatment intervals with patient outcome periods.

A knowledge graph that explicitly represents the time-varying nature of facts, entity states, and relationships by associating them with temporal validity intervals or timestamps. It transforms static entity-relationship models into dynamic systems that can answer questions like "What was the organizational structure in Q3 2023?" or "When did this product become obsolete?"

• Core Extension: Adds a temporal dimension to each triple (subject, predicate, object), creating a quadruple (subject, predicate, object, time).
• Use Case: Enterprise change tracking, regulatory compliance auditing, and predictive maintenance based on historical asset states.

A time range, defined by a start timestamp (validFrom) and an end timestamp (validTo), during which a specific fact, entity property, or relationship in a knowledge graph is considered to be true. This is the concrete data structure that implements the abstract intervals defined in Allen's Algebra.

• Representation: Often stored as [t_start, t_end) where the interval is inclusive of the start time and exclusive of the end time.
• Key Challenge: Managing overlapping, contiguous, or gap-filled intervals to ensure a consistent historical narrative.

A specialized graph database system with native support for storing, indexing, and querying time-evolving graph data. It provides built-in operators for reasoning over temporal validity intervals, eliminating the need for manual time-filtering in application code.

• Native Features: Include time-aware indexes, interval intersection joins, and support for temporal graph traversal queries.
• Examples: Systems like Apache Age with temporal extensions, or custom layers atop Neo4j or Amazon Neptune using property graphs with temporal attributes.

An extension to the standard SPARQL query language that incorporates temporal operators and functions to query time-annotated RDF data. It allows direct expression of Allen's relations (e.g., ?event1 :before ?event2) within the query itself.

• Core Functions: Include VALID_TIME(?triple) to extract an interval, and DURING(?interval1, ?interval2) to test relationships.
• Query Example: SELECT * WHERE { ?employee :heldPosition ?role . VALID_TIME(?role) DURING "2023-01-01"^^xsd:dateTime . } finds roles active during 2023.

A system that performs logical inference and consistency checking over temporal knowledge graphs by applying formal rules, including those defined by Allen's Interval Algebra. It can deduce new time-aware facts or identify contradictions (e.g., an employee being in two cities simultaneously).

• Mechanism: Uses a temporal constraint satisfaction problem (TCSP) solver to propagate interval relationships and maintain a consistent global timeline.
• Application: Critical for automated planning, scheduling systems, and maintaining data integrity in complex event histories.

A temporal knowledge graph model where events are first-class entities, connected by temporal (e.g., before, meets), causal (e.g., triggers), and participative (e.g., involves) relationships. It provides a narrative-centric view complementary to the state-centric view of interval-based TKGs.

• Core Structure: Nodes represent events (e.g., "Product Launch", "System Failure"), edges represent their qualitative and causal linkages.
• Integration with Allen's Algebra: The temporal relationships between event nodes are precisely defined using Allen's 13 relations.