2.1. Relational Databases

Relational databases organize data into tables¹⁰ and model data relationships using key constraints and other constraints. PostgreSQL ¹¹ is the most advanced open source database server. It can handle large volume of data, including data storage, rapid data retrieval and complex data analysis.

Relational databases are highly inefficient at describing and traversing complex connections and relationships. Usually several tables must be joined to extract multiple relationships among entities. With the increasing complexity and heterogeneity of relationships in the real world, the number of joining tables in relational databases increases rapidly and unsustainably. Complex relational databases also have high maintenance costs and are difficult to evolve to continuously changing business needs.

2.2. NoSQL

Most NoSQL databases, whether key-value-, document-, or column-oriented, store sets of disconnected documents/values/columns¹². This makes it difficult to use them for connected data graphs. NoSQL is suitable for simple structured big data instead of data with plentiful properties and labels. If we add relationships to NoSQL data, aggregate joining operation are needed at the application level, which is prohibitively expensive for large data volumes.

2.3. Graph databases

With the increasing integration of components, the structure and characteristics of the power grid become more and more complicated. Many researchers have applied the complex network theory to study real networks,^13–16 mainly focusing on small size power grid network computing. They have made great progress in tracking, detection and control. Graph database is useful for power grids because of the continuously increasing scale of the power grid, extremely wide distribution of power station and high-performance requirement of power grid needed.

Neo4j¹⁷, an open source graph database written in Java and Scala, implements generic graph models with full database characteristics such as ACID transaction compliance, cluster support, runtime failover, and query language. It denotes the different roles by nodes with multiple labels, and represents the relationships by paths between nodes. Due to the path-oriented data model, path-based operations in Neo4j are highly efficient and suitable for use in production scenarios.

3.1. Architecture

The main components of Neo4j’s architecture are its REST-based API, cache, transaction log, and record files (Fig. 1). Neo4j provides GET, POST, and PUT calls to discover service information. The Traverser API allows users to traverse the graph using callbacks. Users can define an approach to search a graph or subgraph using specific rules and algorithms, such as depth-first or breadth-first. Neo4j also exposes certain core APIs that can be directly used by JVM-based languages for working with graphs.

Fig. 1.

Neo4j Architecture

Caching is one of the most important components in Neo4j because it directly affects read and write performance. Neo4j provides two different types of caching layers. One is the file buffer cache which uses off-heap memory to cache data stored on disk. The other is an object cache. All writes and reads are performed through these caches to improve throughput. All writes are written to the caches and data in these caches are flushed to durable storage only when the logical logs are rotated. Neo4j also improves write performance by batching small writes.

Transaction logs maintain all the events and operations that happen over a Neo4j database, which is helpful in scenarios where the database needs to be recovered from a crash.

Record files are files that store information on nodes, relationships and properties. Neo4j recommends using ext4 or ZFS to support features such as flush (fsync, fdatasync) that help guarantee ACID properties.

3.2. Scalability and Redundancy

Neo4j high availability (HA) uses a master-slave cluster architecture¹⁸. As the Fig. 2 illustrates¹⁹, there are two parts to each Neo4j instance. One part is the database itself, the other is the cluster management component. The cluster management component continuously stays in sync with all instances in the cluster, keeping track of any instances joining or leaving. When a master election becomes necessary, the cluster management component ensures that a new master is consistently elected. The database layer manages the rest of the system.

Fig. 2.

Neo4j Cluster Architecture

In a Neo4j HA cluster, the full graph is replicated to each instance in the cluster²⁰. Regardless of the number of instances that fail, all the data is kept safe as long as one instance remains available. One single instance of Neo4j can house at most 34 billion nodes, 34 billion relationships, and 68 billion properties.

3.3. Cypher

Cypher is a declarative graph database query language²¹. It is simple and expressive, closely resembling the natural way of representing patterns in graphs through ASCII art diagrams.

In this paper, we mainly use the Traverser and Core API. Cypher is mainly used for the Shortest Path function.

4.1. Data Augmentation

IEEE 118-bus system whose network data can be found in ²² is used for this study.

Fig. 3.

IEEE 118-bus system

The IEEE 118-bus system is expanded to 200 thousand, 2 million, 20 million and 200 million buses system respectively. Experiments are done separately to simulate the real power grid network environment.

Fig. 4 shows the process of expanding a single 118-bus system to 4n connected 118-bus system. In the expanded system, four 118-bus systems form a small highly connected unit and the expanded system consists of these units.

Fig. 4.

Expanding IEEE 118-bus system

4.2. Database Models

Currently most power grid network data are stored in relational database (RDBMS) with all information located in numerous complex correlated relational tables²³.

For the graph database structure, only two tables are used to build database. One is node table, and the other is connection table. In the node table, one row represents one node as well as its labels. As for the connection table, each row represents a connection and its corresponding properties. Fig. 5 gives a simple demonstration of information stored in these two tables.

Fig. 5.

Topology of Graph

Table on the top is a node table with two nodes, and the table on the bottom is the connection table with connection information between node 1 and node 2. As it shows in the figure, two nodes can have multiple relationships with different properties.

4.3. Initial Energization of Power Grid Network

System initial energization analysis is the process for determining what equipment has power if power is provided to certain nodes. Each node represents a physical bus. The inputs to energization analysis are the primary energized nodes. The output is a list of all the nodes that are connected to these starting nodes, through one or more paths.

In Fig. 6, orange nodes are energized, and green ones are not energized. Voltage for each bus is shown in the figure. Connections are either lines or transformers, with “IncomingSwitchOn” properties and “OutgoingSwitchOn” properties. Transformer is the connection between two nodes with different voltage, and line is the connection between two nodes with the same voltage. Assuming that the starting node is Bus1, the output energized nodes should be nodes {Bus4, Bus6, Bus7}. Other nodes {Bus2, Bus3, Bus5} are un-energized in that voltage of Bus2 is lower than that of Bus1 (affecting Bus2 and Bus3) or connection properties indicate either “IncomingSwithOn” or “OutcomingWitchOn” is off (affect Bus5).

Fig. 6.

Initial Energization Process

4.4. The Shortest Path Search

Breadth-First²⁴ search is the foundation of numerous classical graph algorithms, including Dijkstra’s algorithm²⁵. Dijkstra is used to find the shortest path between two nodes in a graph. It is very efficient because it computes only the lengths of a relatively small subset of the possible paths through the graph. When we have solved a node, the shortest path from starting node is then known, allowing all subsequent paths to safely build.

The A* algorithm²⁶ improves the classic Dijkstra algorithm with a best-first search and distance-plus-cost heuristic function, that finds the least-cost path from an initial node to a goal node. A* is particularly good for path finding and shortest path search over the graph. Neo4j provides APIs of A*.

4.5. Conditional Topological Search Analysis

The goal of system conditional topological search is to store the entire topological structure into graph database and perform conditional topological search.

The input of this model consists of a specified node (bus number), the path number to be traversed, and some termination conditions.

Common termination conditions include arriving at the input node, reaching the node with status “stop” or going through a connection with either “IncomingSwithOn” or “OutgoingWitchOn” off. The search will also be stopped when reaching to a bus in some specific area. In real power grid networks, some buses belong to a specific power station, such as central stations used for generating electricity. When reaching such buses, the search will be stopped.

Fig. 7 shows the Conditional Topological Search structure. In the end, this process returns all the paths and corresponding nodes as result.

Fig. 7.

Conditional Topological Structure

5.1. Energization

5.1.1. Initial Energization

Initial energization uses one node as the starting node, then applies Breadth-First search to this node to find all the adjacent nodes which satisfy energized conditions (Sec 4.3). The subtree for each node adjacent to the starting node is stored in a HashMap. Thus, the graph is divided into the starting node and a group of HashMap.

In each HashMap, we use Depth-First search to check the properties of connection and labels of nodes (‘IncomingSwitchOn’, ‘OutgoingSwitchOn’ and voltage) between two buses (Nodes), then add satisfied energized buses to the Energized Queue.

Fig. 8 shows the architecture of initial energization of power grid network. Before energizing a bus (node), we need to check whether this bus is in the Energized Queue or not. If this bus is already in queue, then there will be an early stop. This implementation is effective when testing on 10,000 nodes. However, when testing on 20,000,000 or more nodes, the search takes a long time. Because real-world power grid networks have over 200 million nodes, we must implement a more efficient initial energization approach.

Fig. 8.

Initial Energization of Power Grid Network

5.1.2. Multi-threading platform

In the former initial energization model (Sec 5.1.1), CPU occupancy is up to 90%, therefore, further improvement of the efficiency requires multicore processing. A multiple worker framework, which depends on the CPU number, is set up to boost the efficiency. Breadth-First search method is used to put all the buses into Breadth-First Queue. All the workers will automatic pull buses from Breadth-First Queue (each time 1000 buses). If the bus is not in the Energized Queue, then use Depth-First search to energized the remaining buses. After that, insert the bus into the Energized Queue as shown in Fig. 9.

Fig. 9.

Initial Energization on multi-threading

Depending on the data size, multi-threading or single thread searching can be implemented accordingly. Multi-threading is more suitable for data size over 20,000,000.

5.2. Shortest Path Search

Neo4j provides the shortest path function based on A* algorithm. We preprocess the power grid data and implement the shortest path query based on Cypher. For comparison, Dijkstra’s shortest path algorithm is also performed based on PostgreSQL using Java.

5.3. Conditional Search

Traversal API provided by Neo4j implements BreadthFirst function to go through all graph database. We also design a HashMap function which can save nodes from Traversal API. In addition, a REST API environment is get up to obtain all the nodes from HashMap. Fig. 10 demonstrates the data flow of the model.

Fig. 10.

Data Flow on Conditional Search

REST APIs provide GET and POST function for conditional search. These functions can be called either from PowerShell or directly from Neo4j client.

6.1. Test Environment

Hardware environment: CPU Intel(R) Core(TM) i5-4460 (3.20GHz), 4 Cores, installed memory (RAM) 12.0 GB. Software environment: using the Neo4j community version 3.1.0, Windows PowerShell version 5.0, Apache Maven 3.3.9, Java version 1.8.0_101, PostgreSQL version 9.5.

The basic model of test data is shown in Fig. 5. There is only one type of node: Bus with 20 labels, whereas two types of relations are presented: Line and Transformer, each with 20 properties.

6.2. Test Method

There are four different data sizes and two functions in test scenario 1, as shown in table 1.

As shown in Table 2, three conditional searches are performed in the test scenario 2.

All queries above have been executed 10 times where the first time is ignored since it warms up Neo4j caches. The values are averaged over 10 executions.

There are 3 different sizes of dataset and 2 functions running on Neo4j and PostgreSQL in these process, as shown in table 3.

All queries above have been executed 10 times. Each query time including the data warm up on Neo4j and PostgreSQL. The data warm up time is included since Read I/O (read from DB to caches) is also one of features in these databases. The values are average over 10 executions.

6.3. Test Results

6.3.1. Test Cases

• Test case 1: Fig. 11 and Fig. 12 show the running time comparison for the test on Neo4j: All datasets (data1-4) and energization. The time unit is milliseconds, and the results are shown in Fig. 11 and Fig. 12.

• Test case 2: Fig. 13 is the results for Data and Conditional Search in Table 2. Running time is recorded in milliseconds. The horizontal axis shows the different conditions and conditions combination.

• Test case 3: Fig. 14 and Fig. 15 present the testing results for Neo4j vs PostgreSQL Energization test in Table 3. Vertical axis represents time in milliseconds. The horizontal axis stands for results for different datasets. The blue bar is the time consumption for Neo4j, and the orange is runtime from PostgreSQL. Fig. 14 shows the single thread results, and Fig. 15 presents the 4-thread results of different databases.

• Test case 4: Fig. 16 and Fig. 17 demonstrate the result of Shortest Path test for Neo4j vs PostgreSQL. The horizontal axis in the plot represents different search conditions on datasets with different sizes.

Fig. 11.

Energization with Neo4j (small data size)

Fig. 12.

Energization with Neo4j (large data size)

Fig. 13.

Conditional Search Results

Fig. 14.

Neo4j vs PostgreSQL (Energization)

Fig. 15.

Neo4j vs PostgreSQL (Energization)

Fig. 16.

Neo4j vs PostgreSQL (the Shortest Path, 2 million dataset)

Fig. 17.

Neo4j vs PostgreSQL (the Shortest Path, 20 million datasets)

Fig. 18 shows the testing results of conditional search on dataset with different sizes. The blue bar and orange bar present the time consumption on Neo4j and PostgreSQL respectively.

Fig. 18.

Neo4j vs PostgreSQL (the Shortest Path)