Temporal Graph in Neo4j: Comparing Storage Structures and Incrementally Constructing an Allen Interval Relation Network

Eremeev Aleksandr Pavlovich ORCID: 0009-0003-1804-6488 Doctor of Technical Science Professor; Federal State Budgetary Educational Institution of Higher Education National Research University 'MEI'; National Research University 'MEI' 111250, Russia, Moscow, Lefortovo district, Krasnokazarmennaya str., 14, building 1 eremeev@appmat.ru

Kutdusov Ruslan Kamilevich ORCID: 0009-0009-9071-0850 Master's student; Federal State Budgetary Educational Institution of Higher Education National Research University 'MEI'; National Research University 'MEI' 111250, Russia, Moscow, Lefortovo district, Krasnokazarmennaya str., 14, building 1 kutdusovrk@mpei.ru

Introduction

Tasks where the state of an object is inextricably linked to the time of its existence are becoming more common in practice. The Neo4j graph model allows you to store objects, relationships, and their attributes, including the time boundaries of events, but it does not specify the semantics of interval relationships. The relationships of Allen's interval logic between events either have to be recalculated with each request, or fixed in advance by separate connections. The choice between these strategies for the ISPR RV component determines the query execution time, storage capacity, and the logic of the temporal Knowledge Base (TBB) rules.

Previously, graph data models were used to unify structures and convert formats in the Neo4j environment ^[1]. A temporal database (TBD) for intelligent real-time decision support systems was built on this technological basis ^[2]. The temporal graph in such an architecture combines interval facts, connections between events, and derived objects that the decision support component works with.

Research on temporal graph models with attributes is developing in several interrelated areas, including the integration of the time dimension into the data model, the expansion of query languages, the preservation of the history of changes and the physical organization of time versions of the graph. Route queries to temporal graphs, equipped with temporal predicates and aggregates, were created specifically for distributed processing ^[3]. Bitemporal graph models draw a boundary between actual and transactional time, which makes it possible to separately track the history of changes in subject facts and the history of their registration in the system ^[4]. Temporal regular route queries formalize navigation through time graphs ^[5]. They distinguish between point timestamps and interval representation. The AeonG system transfers time support to the graph database layer, linking the acceleration of time queries with the separate organization of current and historical versions ^[6].

Temporal knowledge graphs and temporal reasoning form a related research area. Time in a Box suggests analyzing the time domain of the truth of statements in the process of replenishing the knowledge base ^[7]. The TEILP method is based on logical rules that allow predicting the time of events in temporal graphs ^[8]. The existing methods of representation, data sets and applied tasks in this field are systematized in the review of methods of teaching representations of temporal knowledge graphs ^[9]. IA-RAG refers to Allen's interval algebra: this approach provides search and reasoning over dynamic knowledge, the boundaries of which are set by time intervals ^[10].

Research ^[3-10] touches on the languages of temporal queries, ways of storing current and historical versions of the graph, bitemporal representations and reasoning mechanisms in temporal knowledge graphs. The authors of these papers, however, do not directly compare the two strategies for processing Allen's relationships: calculating the relationship along the boundaries of the intervals immediately at the time of query execution and first saving this relationship (as a typed relationship in a Neo4j schema or writing a table in a relational schema). This paper compares these strategies in relation to queries with temporary filters, queries targeting individual Allen relationships, and multi-link crawls. The incremental construction of a temporary network and derived TBZ objects is analyzed separately.

TBDs record the initial facts along with their truth intervals and provide tools for analyzing the relative location of events in time ^{[2, 11]}. TBPS extend this functionality: they include rules of logical inference, time constraints, and derived results that are based on basic facts. It is essential for the ISPR RV to preserve the relationship between the results of temporal reasoning and primary data, since the scenario component relies on this relationship when forming decision support situations ^{[12, 13]}. The formal basis is Allen's interval logic with 13 basic relations, inversion and composition operations ^[14]; deduction algorithms for extended versions of this logic are studied in detail in ^[15].

Two strategies are applicable to the implementation of TBD. In a compact structure, the time ratio is calculated along the boundaries of the intervals during query execution. In the extended structure, calculated dependencies are stored as separate typed relationships. This choice is associated with a compromise between the query time, storage volume, and the number of pre-stored temporary links ^[3-6].

The purpose of the work is to determine the conditions for using a compact and extended temporal graph structure when executing queries and incremental events. The research covers the construction of temporal relationships, consistency checking, comparison of graph and relational representations, the implementation of TBD rules and the work of the scenario component of the ISPR RV.

The scientific novelty lies in the experimental comparison of compact and extended representations of Allen interval relations in graph and relational models; identification of the multidirectional influence of pre-preservation of temporary relationships on different classes of queries; incremental formation of a temporary network, the results of triggering rules and decision support objects; determining the conditions for the use of a compact structure and a structure with pre-stored temporary relationships in the ISPR component RV.

The results obtained are of practical importance for the development of temporal components of graph databases and knowledge bases. When designing such a component, it is necessary to choose in advance what to store in the graph: only the boundaries of the intervals or also the calculated relationships between the intervals. The comparison shows for what purposes a compact structure is sufficient, and in which cases the preliminary preservation of temporary connections is justified. These conclusions are also used when choosing the package size, time window, and order of fixation of derived objects in the decision support component.

1. Organization of the temporal graph and experimental scheme

1.1. The initial set of contacts

The open set High School 2013 of the SocioPatterns project, containing student contacts registered by wearable sensors, was used as an experimental basis ^{[16, 17]}. The research was conducted within 5 working days. The source string includes the timestamp and the IDs of the participant pair. One observation corresponds to a twenty-second window of interaction. The set contains 188,508 rows and the data of 327 participants in nine classes (ID, gender, and class). The transformation of discrete observations into interval facts corresponds to the TBD representation of events with duration ^{[1, 2, 11]}.

1.2. Storage structures

Let there be a set of students, – a set of contacts, – a set of intervals, – a set of basic relations of Allen's logic. The interval is set by the boundaries where . For an ordered pair of intervals, one exact relation is determined ^[14].

In option A, a contact is represented by a CONTACT link between the Person nodes. The connection properties contain start_time, end_time, and duration. Option B uses separate Contact and Interval nodes. The participants are connected to the PARTICIPATES_IN Contact, and the contact is connected to the interval by the HAS_INTERVAL relation. The calculated time dependencies are stored as typed connections between Interval nodes. This separation of data and relationships corresponds to the TBD graph representation developed in ^{[1, 2]}, and is associated with a line of work on temporal graph models with attributes, where time is included in the data structure and query language ^[3-6]. The diagrams are shown in Fig. 1.

Fig. 1. Structures of graph representation of interval contacts

The relational analogue of option A contains the Person and Contact tables with temporary attributes. The extended relational schema is complemented by the AllenRelation table(interval_id_1, interval_id_2, relation_type), which stores the same set of time dependencies as option B. The comparison allows you to separate the impact of the storage model from the cost of calculating the time ratio. Unlike bitemporal graph models with attributes ^[4], the prototype captures the actual time of the interval contact and does not store a separate transactional time axis.

In a compact representation (both graphically and relational), the relation is determined by the boundaries of the intervals and directly during query execution. In the extended graph representation, the same result is stored as a type of directed connection between vertices and , and in the relational schema as an entry in the AllenRelation table.

1.3. Building time links and checking consistency

The ratio between the two intervals was calculated by the conditions above their boundaries corresponding to the 13 basic Allen relations ^[14]. The comparison was limited to one calendar day. If there were events per day, then the number of pairs being checked has an order , while the global pairwise comparison has an order . One directional link was created for each ordered pair of intervals. When considering the pair in the reverse order, the corresponding inverse type of relationship was preserved.

The problem of matching time constraints is represented by an interval algebra network (IA-network), the vertices of which are intervals, and the edges are mapped to a set of acceptable relations ^{[12, 15]}. Path matching checks each triple and clarifies the direct constraint through the composition of two adjacent constraints.:

The operation is repeated until a fixed point is reached. An empty set means a locally discovered contradiction. For a complete network of intervals , the upper time estimate is , and the storage volume of the constraints is of the order of magnitude .

In the implemented TBD, the interval boundaries are known, so each constraint is a single-element set of relations.: . Verification (1) boils down to checking whether a direct relation belongs to the result of the composition.:

With this formulation, the algorithm does not narrow down the set of acceptable relationships and does not derive an alternative scenario. It compares the type of direct relationship, feedback, and the result of the composition, so it detects errors in calculating the relationship, inconsistent inversion, incorrect entry in the composition table, or an error in saving the type of relationship.

Verification (2) is of a local nature. It does not solve a general problem with vague or disjunctive constraints, does not search for a matching scenario, and does not guarantee global consistency. Networks outside of solvable subclasses require multiple constraint propagation and, in the general case, backtracking ^[12]. The daily window excludes triples containing intervals of different calendar days.

1.4. Control temporal queries

The experimental set included queries on a time window, participant's history, a socio-temporal sample, overlapping intervals (Allen's ratio), a short chain through an intermediate participant, and an aggregated profile. These classes cover filtering, graph navigation, and aggregation used in TBD [1-6, 11]. The average time for ten measurements was compared with the same number of returned objects. The arithmetic mean, sample standard deviation, minimum and maximum time were recorded for each query; the time of data preparation and the construction of pre-stored relationships were taken into account separately. For queries based on stored relationships, the relationship type was used, and in compact schemes, the same condition was calculated using start_time and end_time.

1.5. Temporal knowledge base, rules and scenario layer

A validation-type TBZ is formed on top of the TBD. TBD stores the original contacts, intervals, participant attributes, and time dependencies, while TBZ adds rules and derived facts. Based on control queries, the rules of long-term contact, repetitive interaction of the couple, inter-class contact, high activity of the participant and intersection with the external scenario interval are implemented. The conditions of the rules are set by predicates over contact properties, aggregates, participant attributes, and stored temporary relationships. This layer differs from approaches to temporal knowledge graphs based on vector representations ^[7-9]: it preserves verifiable interval dependencies and the result of the rule operation in an explicit graph form.

The rule trigger is saved by the RuleResult node. It is a derived TBZ fact, not a service log entry. RuleResult contains the rule ID, the actual value of the metric, the threshold, the time of detection, and the connection to the source objects. The rules do not perform automatic transitive inference of new Allen relations and do not change the IA network; they verify the conditions over the TBD facts and record the verification result.

The scenario layer refers to the components of the ISPR RV that transform the results of reasoning into decision support objects ^[13]. The ScenarioEvent node sets the external time context: the control period, the monitoring mode, or the interval of the external event. The combination of ScenarioEvent and RuleResult forms a DecisionSituation with properties of the situation status, significance level, and direction of reaction or further verification. DecisionSituation is not an automatically made decision; it is a structured situation with a recommendation and a stored basis for formation.

The BASED_ON_RESULT and BASED_ON_EVENT links provide a trace from the situation to the derived TBD fact and an external event. The initial set does not contain management events, so the scenario intervals were set synthetically. This mode checks the interaction of TBD, TBZ and the scenario component of the ISPR RV, but does not assess the substantive validity of recommendations for a real organization.

1.6. Batch pipeline

In incremental processing, Python manages the sequential submission of contacts and the collection of metrics. Cypher performs loading and fetching, and APOC creates links with a dynamically set type. Package processing includes adding Contact and Interval, calculating local time relationships, running TBZ rules, creating RuleResult and DecisionSituation. This sequence corresponds to the separation of data, knowledge, and scenario objects in the prototype of the ISPR RV ^{[2, 13]}. Horizon limitation and subbatches refer to engineering means of controlling the cost of pre-maintaining temporary connections, which are close in formulation to the problem of built-in temporal support and storage of graph history ^{[4, 6]}.

The first launch used large packages and a single transaction for related operations. After stopping due to the transactional memory limit, the packet size was reduced, new intervals were processed in sub-batches, and the comparison was limited to the local time horizon within a calendar day. The window and transaction parameters act as limiters of the computing load during the incremental update of TBD and TBZ. The conveyor diagram is shown in Fig. 2.

Fig. 2. The pipeline of incremental processing of interval events

2. Experimental evaluation of graph representations

2.1. Hardware and software configuration of the experiment

All measurements were performed on the same computer. On the same configuration, data was loaded, temporary connections were built, control requests were launched, and batch processing was performed. The main parameters of the environment are given in Table 1.

Table 1. Hardware and software configuration of the experiment

2.2. Formation of intervals and basic structures

The identifiers of each pair were brought to the canonical order . The entries were sorted by pair and time. Consecutive windows were combined if the time gap did not exceed twenty seconds; with a larger gap, a new interval began. For each TBD fact, the beginning, ending, and duration were preserved.

After combining the elementary windows, 67,613 interval contacts were formed. The minimum duration is 20 seconds, the maximum is 7080 seconds, and the average is 55.76 seconds. Reducing the number of records relative to the original set is associated with combining consecutive observations of one pair.

Loading the basic structure took from 3,179 to 5,482 seconds. Option A and the Contact relational table had a similar volume. Option B, before creating links between intervals, took up more space due to the Contact, Interval, and service edges nodes. The technical loading parameters are shown in Table 2.

Table 2. Technical indicators for loading storage structures

2.3. Building temporary links and checking local consistency

There are 935,176,338 directional links stored in the daily windows, each of which corresponds to one exact Allen relation. Relational construction was performed 2.18 times faster than graph construction. The size of the structures was measured by the volume of the database files after the download and linking were completed. The AllenRelation table took about 85 GB, and the graph with typed links took about 30 GB. With the same number of facts, the graph representation turned out to be more compact than a flat relational table.

On the entire control set of intervals, triples were checked according to 39 composition rules (only direct relations were checked, since the reverse ones are conjugate). For each tested triple, the ratio was included in the set set by the composition; no empty intersection results were obtained.

The check confirmed the consistency of the relationship calculation, the composition table used, and the types of relationships stored in the control subgraph. The single-element constraints did not change, and no new relationships were derived. The result does not characterize networks with indeterminate boundaries, disjunctive constraints, day-to-day dependencies, or contradictions that are found only in a global search.

2.4. Execution of temporal queries

Before the measurement series, each query was performed twice to warm up. Then 10 measurement runs were carried out for four circuits. The time was measured on the side of the Python control script from sending the request to receiving the aggregated result. For Q1, the window was used on December 2, 2013 from 11:00 a.m. to 12:00 p.m., for Q2 – participant with ID 1, for Q3–Q6 – data for December 2, 2013. The maximum time gap in Q5 was 600 seconds. Statistical indicators of the execution time of control queries are given in Table 3 and in Fig. 3.

Table 3. Statistical indicators of the execution time of control queries for 10 measurements

Fig. 3. Average execution time of control queries and standard deviation in the log scale

Queries Q1–Q3 and Q6 consist of filtering, connecting with participants, and grouping. For Q1, the minimum average time is obtained in column A – 0.002111 s. In queries Q2, Q3, and Q6, the minimum values were obtained in relational schemas and were 0.000173, 0.007837, and 0.019979 s, respectively. The time ratio of graphs A and B depends on the query structure: graph B is slower in Q1 and Q2, but faster in Q3 and Q6. Therefore, additional transitions through the Contact and Interval nodes in scheme B do not determine the execution time independently of the rest of the query operations.

The Q4 query uses the same interval overlap condition. In column A, the ratio was calculated along the boundaries of the contact pairs in 7.859439 ± 0.080971 s. In column B, the sampling based on the stored OVERLAPS connection was performed in 0.017793 ± 0.007836 s. The average time ratio was 441.7 times in favor of the extended structure.

The Q5 query verifies a multi-link chain through an intermediate participant. In column A, the average time was 0.504094 ± 0.051499 s. In graph B, the path through Person, Contact, Interval, and time connections was completed in 241.576489 ± 8.178880 s. The average time ratio was 479.2 times in favor of the compact structure.

2.5. The results of the construction of temporal rules and the scenario layer

In the full run, TBZ generated 69,769 RuleResult nodes. Each node records a separate rule trigger and keeps in touch with the contact, interval, or participant for whom the condition was calculated. The actual value of the indicator and the applied threshold allow you to re-check the basis of the derived fact without referring to an external journal.

The ISPR RV scenario layer formed 191,997 DecisionSituation nodes. The number of situations does not match the number of RuleResult, since one derived fact can enter into several scenario contexts and be associated with several objects. The status, level of significance, recommendation, and basis of formation are preserved for each situation.

The BASED_ON_RESULT and BASED_ON_EVENT links preserved the path from DecisionSituation to the TBT fact and the external time context. The sequence of Contact/Interval, RuleResult, and DecisionSituation was performed during the processing of each package, so derived objects were created incrementally, and not after the download of the entire set was completed. Table 4 shows the results of constructing rules and scenario events.

Table 4. Formation of derived objects

2.6. Results of pipelined batch processing

The figures for the two launches are shown in Table 5.

Table 5. Batch processing results

The first launch showed the scale of the problem: the system tried to create 1,229,921 connections for one packet. A single transaction combined a package of contacts with temporary connections and derived objects, which led to the exhaustion of Neo4j transactional memory. After processing part of the set, the database stopped executing.

The second launch was structured differently: the package contained 100 contacts, connections were formed in sub-patches of 20 new intervals, and the time horizon was limited to 600 seconds within a day. This configuration made it possible to process the entire data set, although shortening the horizon reduced the number of candidates and the size of the transaction. At the same time, the dependencies between events spaced over a longer period of time fell out of the analysis.

3. Conditions of use and limitations of the study

Neo4j is chosen as a single graph platform in which relationships are represented by directional typed relationships and can contain properties. This allows you to compare the storage of interval boundaries in the contact properties with the representation of the interval by a separate node and the preservation of calculated time dependencies as relationships. Comparing graph databases is not part of the job; a fixed platform is used to evaluate two storage structures on the same dataset.

The compact TBD and its variant with pre-stored temporary connections solve different tasks. The first approach does not create a separate layer of links between intervals, which reduces the storage volume, eliminating an increase in the density of the time subgraph. This representation is suitable for temporary filters, aggregate calculations, and processing of short chains of dependencies. The second approach significantly reduces costs for repeated queries to a specific type of relationship and generates ready-made facts for the rules of the temporal knowledge base, but the computational load is transferred to the data preparation stage ^[1-6]. Relational databases show high efficiency in scenarios with simple filters and aggregates ^[11], whereas the expanded AllenRelation table eliminates the need to recalculate the time dependence, although its volume exceeds the size of the graph representation of similar facts. The choice between SQL and a graph database is determined by the nature of the queries, the allowable amount of storage, and the need to convert temporary relationships into derived knowledge.

The distinction between TBD and TBZ prevents the source data from being confused with the results of logical inference. RuleResult captures the verifiable derived fact, and DecisionSituation associates it with an external scenario and decision support parameters ^[13]. With this approach, the scenario layer keeps the initial intervals unchanged, does not introduce additional Allen relations, but forms an independent level of knowledge containing a recommendation along with a path to the basis of its formation.

The local horizon reduces the computational load, but limits the completeness of the temporary network. For TBZ rules that operate on events that are close in time, such a compromise is acceptable. Long-term dependencies require a different solution: a separate archive layer, background linking, or multiple windows of different widths. The size of the subbatch affects memory consumption, while maintaining the quadratic nature of the pairwise comparison inside the window.

The APOC library is used only to create a relationship with a type calculated from interval boundaries. The conditions of the 13 Allen relations, the limitation of the pairwise comparison area, the organization of packages and sub-matches, the verification of local consistency, the launch of TBZ rules and the formation of decision support situations are implemented in the developed software pipeline.

Consistency in the prototype is checked through single-element constraints calculated using known boundaries, which makes it possible to control the local compatibility of triples, however, this approach does not reveal all the contradictions of the overall SSO in cases where the network is locally consistent, and a global search is required for full verification. Working with TBZ containing incomplete or contradictory time information requires a different approach: each constraint must store a set of valid relationships, after which an iterative narrowing is performed, and a backtracking search is applied outside of the solvable subclasses ^{[12, 15]}. At the same time, verification is not able to correct erroneous initial timestamps, since a consistent network may well be built along incorrectly registered borders.

The prototype supports incremental batch processing that simulates the arrival of events in real time, but the logic of transactional time has not yet been implemented. The bitemporal expansion, covering both time layers, is planned as an independent stage in the development of the model ^[4]. Experimental results were obtained on a single data set with a fixed hardware configuration, which narrows the possibilities of transferring them to other operating conditions. Inter-day time connections were not built within the framework of this study. Scenario events were added artificially, since the initial data set does not include information about external management impacts on participants. The combination of these limitations outlines the boundaries of the applicability of the formulated recommendations and determines the directions of subsequent experiments.

The obtained ratios of time and storage volume relate to the network of the scale and density under consideration. For sets with a different distribution of the number of events over time windows, the cost of building relationships and executing queries may change.

Conclusion

The purpose of the work has been achieved: a graph TBD has been developed and investigated, combined with TBD and the scenario component of the ISPR RV. The comparison of storage structures made it possible to determine which operations should be performed along the boundaries of the intervals, and which rely on previously stored time relationships. Consistency checking is included in the prototype as a means of checking the local correctness of the exact relationships.

For a query with respect to OVERLAPS, the pre-stored relationship changed the average execution time from 7,859439 to 0.017793 seconds, that is, approximately 441.7 times. For multi-step traversal, the average time changed from 0.504094 to 241.576489 s, approximately 479.2 times in favor of compact storage. The graph with 935,176,338 typed temporary relationships took up about 30 GB, and the relational table with the same set of relationships took up about 85 GB. Relational connection construction was performed 2.18 times faster than graph construction.

A compact representation is recommended for temporary filters, aggregations, and short chains. The extended view is useful for repeated queries on a limited set of relationships, active TBD rules, and scenarios that require tracing back to the original facts. With the same number of stored time relationships, the extended graph representation turned out to be more compact than the extended SQL representation.

The result obtained is consistent with the general problem of temporal graph models with attributes: acceleration of time and route queries is associated with additional storage, indexing, or preliminary formation of historical links ^[3-6]. In streaming mode, the time horizon, packet size, and transaction volume must be set taking into account the allowable latency and memory.

It is possible to develop the system in several directions: support for transactional time, storage of sets of acceptable relationships, search for matching scenarios, adaptive choice of a time window and partial preservation of the most demanded types of relationships. A separate line of research is the integration of Allen's interval relations with the methods of reasoning and search in temporal knowledge graphs, where interval boundaries become part of logical inference ^[7-10]. Separating the operational and archive layers will allow combining local stream processing with long-term dependency analysis. The final limits of the prototype's applicability have yet to be clarified through experiments on other subject sets and hardware configurations.

Subsequent experiments should cover larger networks, sets of different densities, and additional hardware configurations.

The article is published in its final version as approved following the last positive peer review recommending acceptance for publication. It incorporates revisions made by the author in response to prior negative peer review reports that did not recommend publication. All peer review reports, including initial negative reviews, are published in open access alongside the article. All versions of the author’s revisions are archived in the publisher’s repository and may be made available upon reasonable request in accordance with Elsevier’s editorial policies and applicable data availability requirements.
Read all reviews on this article