Chapter 01History

The history of graph databases can be traced back to foundational work in network models and the standardization of database languages. A notable early system was the Integrated Data Store (IDS), designed by Charles Bachman, which laid the groundwork for the network model of databases. This model was further formalized by the Conference on Data System Languages (CODASYL) through its Data Base Task Group (DBTG). In the late 1960s, CODASYL created DBTG, which issued influential reports in 1969 and 1971, proposing a standard sublanguage for database applications to be embedded in COBOL (North 1968).

In a parallel development, IBM introduced the Information Management System (IMS) in 1968, employing a hierarchical data model. IMS structured data into record types, each comprising a set of named fields with defined data types, where a subset of fields served as keys, uniquely identifying each record instance. This structure imposed a strict tree hierarchy, requiring each record (except the root) to have a single parent. Such a requirement created challenges, necessitating data duplication and limited support for certain cases. For instance, part information had to be repeated across suppliers, increasing the risk of inconsistency, while certain relationships, such as a part without suppliers, were not supported. These limitations highlighted the rigid nature of hierarchical models, spurring the exploration of more flexible structures (Klein et al. 2011).

CODASYL, recognizing the limitations of a strictly hierarchical approach, introduced a network data model in its 1971 and 1973 reports. This model abandoned the tree structure of IMS, allowing each record instance to have multiple parent records, thus forming a more interconnected network rather than a single-rooted hierarchy. In this model, connections were represented by “sets”, which defined 1-to-n relationships between an owner record type and its associated child record types. While referred to as sets, these structures were closer to directed relationships, where each owner could relate to multiple instances of a child record type. This network approach allowed for greater data flexibility, enabling a record to have multiple parents and eliminating the limitations imposed by hierarchical constraints (CODASYL. Systems Committee 1971).

Simultaneously, the American National Standards Institute (ANSI) played a pivotal role in creating a standardized framework for database languages. In 1978, ANSI formed the committee known as ANSI X3H2, now called INCITS DM32, or “H2”. This committee focused on developing a “Network Data Language” (NDL) based on the 1971 CODASYL DBTG report, aiming to establish a competitive and compatible market for database products. The work of ANSI and CODASYL significantly influenced the evolution of database technologies, setting the stage for more advanced data models that eventually led to the development of graph databases (Gorman 1978).

Amid these advancements, Conceptual Graphs (CGs) emerged as another significant innovation in graph-based knowledge representation. Proposed by John F. Sowa in the mid-1970s (Sowa 1976), CGs were formally introduced in his seminal book published in 1984 (Sowa 1984). Conceptual Graphs are designed to represent knowledge in a way that is intuitively understandable to humans while being efficiently processable by computers, acting as a bridge between natural language and machine languages. This form of representation plays a crucial role in the conceptual modeling of domains and enhances the semantic processing capabilities of information systems.

Parallel to the developments in traditional database models, Tim Berners-Lee envisioned the Semantic Web in the mid-1990s, shortly after initiating the development of the World Wide Web (Berners-Lee 1998). The concept was formalized by establishing the World Wide Web Consortium (W3C) and gained significant momentum with the publication of a vision in a 2001 Scientific American article (Hendler et al. 2001). Despite the ambitious visions, the Semantic Web had only been partially realized, with a limited portion of the web domains incorporating Semantic Web markup. SPARQL¹ (Seaborne and Prud’hommeaux 2008), introduced in 2004 and refreshed in 2008, emerged as a dedicated query language that facilitated the retrieval of data stored in the Resource Description Framework (RDF) (Carroll and Klyne 2004), offering capabilities such as “property paths”, which resemble features of regular path queries in graph databases.

The late 20th century saw significant research into graph query languages, with the introduction of regular path queries (RPQs) (Cruz et al. 1987) in 1987 and their extension into conjunctive regular path queries (CRPQs) (Consens and Mendelzon 1990) by 1990. These developments underscored the growing interest in efficiently querying complex graph structures beyond the limitations of Structured Query Language (SQL) and RDF for graph-related problems.

The Neo4j property graph database was launched in 2007 (Angles 2012; Hunger 2012), and in 2011 its Cypher query language was introduced (Francis et al. 2018; Lindaaker 2018), to allow declarative querying and manipulation of graph data. The property graph data model, as distinct from RDF, places records of properties (very similar to SQL rows) on both nodes and relationships, and is particularly aligned with the needs of modern applications such as knowledge graphs for artificial intelligence (AI) and data mesh architectures. The evolving standards continued with the recent introductions of SQL Property Graph Queries (SQL/PGQ) in 2023 (International Organization for Standardization 2023) and GQL in 2024 (ISO/IEC 2024), reflecting a trend toward formal standardization in graph query languages.

Standardization has been crucial in the database industry, ensuring interoperability and fostering a competitive market environment. As graph databases have grown in importance and are driven by AI and big data applications, developing standardized query languages such as GQL is essential. This facilitates technological innovation and supports scalable, efficient, and less complex data architectures, enabling businesses to leverage graph data effectively.

From the network models and NDL of CODASYL and ANSI’s early efforts to the sophisticated graph query languages like SPARQL and Cypher, the journey of graph databases reflects a broader evolution toward more structured, interoperable, and efficient data management practices. As these technologies continue to develop, they promise to underpin next-generation data infrastructures and applications.