Jump to content

User:Hyeonjungko/GraphDatabases

From Wikipedia, the free encyclopedia
< User:Hyeonjungko
This is an old revision of this page, as edited by Hyeonjungko (talk | contribs) at 03:38, 22 October 2018 (editing). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Copied text has been bolded. Personal edits have been indicated with normal text and strikethroughs.

Graph Database

In computing, a graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges and properties to represent and store data. A key concept of the system is the graph (or edge or relationship), which directly relates data items in the store representation of relationships between nodes of data. The relationships allow data in the store to be linked together directly, and in many cases retrieved with one operation.

This contrasts with relational databases that, with the aid of relational database management systems, permit managing the data without imposing implementation aspects like physical record chains; for example, links between data are stored in the database itself at the logical level, and relational algebra operations (e.g. join) can be used to manipulate and return related data in the relevant logical format. The execution of relational queries is possible with the aid of the database management systems at the physical level (e.g. using indexes), which permits boosting performance without modifying the logical structure of the database.

Relationships can be visually represented simply using a graph databases, thus making it useful for heavily inter-connected data.[1]

Graph databases are part of the NoSQL databases created to address the limitations of the existing relational databases. Graph databases, by design, allow simple and fast retrieval[citation needed] of complex hierarchical structures that are difficult to model[according to whom?] in relational systems. Graph databases are similar to 1970s network model databases in that both represent general graphs, but network-model databases operate at a lower level of abstraction and lack easy traversal over a chain of edges.

The underlying storage mechanism of graph databases can vary. Some depend on a relational engine and “store” the graph data in a table (although a table is a logical element, therefore this approach imposes another level of abstraction between the graph database, the graph database management system and the physical devices where the data is actually stored). Others use a key-value store or document-oriented database for storage, making them inherently NoSQL structures. Most[according to whom?] graph databases based on non-relational storage engines also add the concept of tags or properties, which are essentially relationships having a pointer to another document. This allows data elements to be categorized for easy retrieval en masse.

Retrieving data from a graph database requires a query language other than SQL, which was designed for the manipulation of data in a relational system and therefore cannot “elegantly” handle traversing a graph. As of 2017, no single graph query language has been universally adopted in the same way as SQL was for relational databases, and there are a wide variety of systems, most often tightly tied to one product. Some standardization efforts have occurred, leading to multi-vendor query languages like Gremlin, SPARQL, and Cypher. In addition to having query language interfaces, some graph databases are accessed through application programming interfaces (APIs).

Background

Traditionally, databases have been designed with the relational model. In a relational model, data is normalized to support ACID transactions. The data normalization process removes any duplicate data within the database. Such data normalization is very efficient in preserving data consistency. The relational model enforces ACID transactions, separating data into many tables. This aspect of the relational model forces the client to perform join operations on the tables of data in order to view any sort of relationship between different data.

Graph databases, on the other hand, portrays the data as it is drawn conceptually. This is accomplished by transferring the data and its relationships into a graph.

Graph

A graph within Graph databases is are based on graph theory. It is a set of objects, either a node or an edge.

Graph databases employ nodes, properties, and edges.
  • Nodes represent entities or instances such as people, businesses, accounts, or any other item to be tracked. They are roughly the equivalent of the record, relation, or row in a relational database, or the document in a document-store database.
  • Edges, also termed graphs or relationships, are the lines that connect nodes to other nodes; they represent the representing the relationship between them. Meaningful patterns emerge when examining the connections and interconnections of nodes, properties, and edges. The edges can either be directed or undirected. In an undirected graph, an edge from a point to another have one meaning. In a directed graph, the edges connecting two different points have different meanings depending on their direction. Edges are the key concept in graph databases, representing an abstraction that is not directly implemented in other systems a relational model or a document-store model.
  • Properties are germane information to nodes. For example, if Wikipedia were one of the nodes, it might be tied to properties such as website, reference material, or words that starts with the letter w, depending on which aspects of Wikipedia are germane to a given database.

Usage

Because graph databases can intuitively represent many-to-many relationships between data, it is commonly employed in several distinct applications. Graph databases can assist the client in finding relationships between seemingly-unrelated pieces of data.

Knowledge-Based Applications

Main article: Knowledge-Based systems
Biology

Graph databases are utilized in understanding complex relationships among heterogeneous biological data.[1] It has been used to represent and query disease networks[2], effectively to improve the simulation of computational models of a biological system[3], and drug repositioning using gene-disease associations[4].

Transactional Data Applications

Graph databases are utilized in

Operations

Typical operations within a graph databases include finding the shortest path, graph traversal,

In Comparison: Relational Databases

Since Edgar F. Codd's 1980 paper on the relational model[5], relational databases have been the de-facto industry standard for large-scale data storage systems. However, relational model's requirement of a strict schema and data normalization imposed limitations on how relationships can be queried[6]. The increasing amount of data needed to be processed became an additional problem posed by the relational model.

Relational models enforce heavy data normalization in order to guarantee consistency. Problems arise with when there is a need to form complex relationships between the stored data. Although relationships can be analyzed with the relational model, complex queries performing many join operations on many different attributes over several tables are required.

The relational model gathers data together using information in the data. For example, one might look for all the "users" whose phone number contains the area code "311". This would be done by searching selected datastores, or tables, looking in the selected phone number fields for the string "311". This can be a time consuming process in large tables, so relational databases offer the concept of a database index, which allows data like this to be stored in a smaller subtable, containing only the selected data and a unique key (or primary key) of the record it is part of. If the phone numbers are indexed, the same search would occur in the smaller index table, gathering the keys of matching records, and then looking in the main data table for the records with those keys. Generally, the tables are physically stored so that lookups on these keys are fast.[7]

Relational databases do not inherently contain the idea of fixed relationships between records. Instead, related data is linked to each other by storing one record's unique key in another record's data. For example, a table containing email addresses for users might hold a data item called userpk, which contains the primary key of the user record it is associated with. In order to link users and their email addresses, the system first looks up the selected user records primary keys, looks for those keys in the userpk column in the email table (or more likely, an index of them), extracts the email data, and then links the user and email records to make composite records containing all the selected data. This operation, termed a join, can be computationally costly. Depending on the complexity of the query, the number of joins, and the indexing of the various keys, the system may have to search through multiple tables and indexes, gather lots of information, and then sort it all to match it together.[7]

In contrast, graph databases directly store the relationships between records. Instead of an email address being found by looking up its user's key in the userpk column, the user record has a pointer directly to the email address record. That is, having selected a user, the pointer can be followed directly to the email records, there is no need to search the email table to find the matching records. This can eliminate the costly join operations. For example, if one searches for all of the email addresses for users in area code "311", the engine would first perform a conventional search to find the users in "311", but then retrieve the email addresses by following the links found in those records. A relational database would first find all the users in "311", extract a list of the pk's, perform another search for any records in the email table with those pk's, and link the matching records together. For these types of common operations, a graph database (in theory at least) is significantly faster.[7]

The true value of the graph approach becomes evident when one performs searches that are more than one level deep. For example, consider a search for users who have "subscribers" (a table linking users to other users) in the "311" area code. In this case a relational database has to first look for all the users with an area code in "311", then look in the subscribers table for any of those users, and then finally look in the users table to retrieve the matching users. In contrast, a graph database would look for all the users in "311", then follow the back-links through the subscriber relationship to find the subscriber users. This avoids several searches, lookups and the memory usage involved in holding all of the temporary data from multiple records needed to construct the output. Technically, this sort of lookup is completed in O(log(n)) + O(1) time, that is, roughly relative to the logarithm of the size of the data. In contrast, the relational version would be multiple O(log(n)) lookups, plus more time to join all the data.[7]

The relative advantage of graph retrieval grows with the complexity of a query. For example, one might want to know "that movie about submarines with the actor who was in that movie with that other actor that played the lead in Gone With the Wind". This first requires the system to find the actors in Gone With the Wind, find all the movies they were in, find all the actors in all of those movies who were not the lead in Gone With the Wind, and then find all of the movies they were in, finally filtering that list to those with descriptions containing "submarine". In a relational database this will require several separate searches through the movies and actors tables, doing another search on submarine movies, finding all the actors in those movies, and then comparing the (large) collected results. In contrast, the graph database would simply walk from Gone With the Wind to Clark Gable, gather the links to the movies he has been in, gather the links out of those movies to other actors, and then follow the links out of those actors back to the list of movies. The resulting list of movies can then be searched for "submarine". All of this can be done via one search.[8]

Properties add another layer of abstraction to this structure that also improves many common queries. Properties are essentially labels that can be applied to any record, or in some cases, edges also. For example, one might label Clark Gable as "actor", which would then allow the system to quickly find all the records that are actors, as opposed to director or camera operator. If labels on edges are allowed, one could also label the relationship between Gone With the Wind and Clark Gable as "lead", and by performing a search on people that are "lead" "actor" in the movie Gone With the Wind, the database would produce Vivien Leigh, Olivia de Havilland and Clark Gable. The equivalent SQL query would have to rely on added data in the table linking people and movies, adding more complexity to the query syntax. These sorts of labels may improve search performance under certain circumstances, but are generally more useful in providing added semantic data for end users.[8]

Relational databases are very well suited to flat data layouts, where relationships between data is one or two levels deep. For example, an accounting database might need to look up all the line items for all the invoices for a given customer, a three-join query. Graph databases are aimed at datasets that contain many more links. They are especially well suited to social networking systems, where the "friends" relationship is essentially unbounded. These properties make graph databases naturally suited to types of searches that are increasingly common in online systems, and in big data environments. For this reason, graph databases are becoming very popular for large online systems like Facebook, Google, Twitter, and similar systems with deep links between records.

Properties

Compared with relational databases, graph databases are often faster for associative data sets[citation needed] and map more directly to the structure of object-oriented applications. They can scale more naturally[citation needed] to large data sets as they do not typically need costly join operations (here costly means when executed on databases with non-optimal designs at the logical and physical levels). As they depend less on a rigid schema, they are marketed as more suitable to manage ad hoc and changing data with evolving schemas. Conversely, relational database management systems are typically faster at performing the same operation on large numbers of data elements, permitting the manipulation of the data in its natural structure.

Graph databases are a powerful tool for graph-like queries. For example, computing the shortest path between two nodes in the graph. Other graph-like queries can be performed over a graph database in a natural way (for example graph's diameter computations or community detection).

History

In the pre-history of graph databases, in the mid-1960s Navigational databases such as IBM's IMS supported tree-like structures in its hierarchical model, but the strict tree structure could be circumvented with virtual records.[9][10]

Graph structures could be represented in network model databases from the late 1960s. CODASYL, which had defined COBOL in 1959, defined the Network Database Language in 1969.

Labeled graphs could be represented in graph databases from the mid-1980s, such as the Logical Data Model.[11][12]

Several improvements to graph databases appeared in the early 1990s, accelerating in the late 1990s with endeavors to index web pages.

In the mid-late 2000s, commercial atomicity, consistency, isolation, durability (ACID) graph databases such as Neo4j and Oracle Spatial and Graph became available.

In the 2010s, commercial ACID graph databases that could be scaled horizontally became available. Further, SAP HANA brought in-memory and columnar technologies to graph databases.[13] Also in the 2010s, multi-model databases that supported graph models (and other models such as relational database or document-oriented database) became available, such as OrientDB, ArangoDB, and MarkLogic (starting with its 7.0 version). During this time, graph databases of various types have become especially popular with social network analysis with the advent of social media companies.

References

  1. ^ a b Yoon, Byoung-Ha; Kim, Seon-Kyu; Kim, Seon-Young (2017-3). "Use of Graph Database for the Integration of Heterogeneous Biological Data". Genomics & Informatics. 15 (1): 19–27. doi:10.5808/GI.2017.15.1.19. ISSN 1598-866X. PMC 5389944. PMID 28416946. {{cite journal}}: Check date values in: |date= (help)CS1 maint: PMC format (link)
  2. ^ Lysenko, Artem; Roznovăţ, Irina A.; Saqi, Mansoor; Mazein, Alexander; Rawlings, Christopher J.; Auffray, Charles (2016). "Representing and querying disease networks using graph databases". BioData Mining. 9: 23. doi:10.1186/s13040-016-0102-8. ISSN 1756-0381. PMC 4960687. PMID 27462371.{{cite journal}}: CS1 maint: PMC format (link) CS1 maint: unflagged free DOI (link)
  3. ^ Henkel, Ron; Wolkenhauer, Olaf; Waltemath, Dagmar (2015). "Combining computational models, semantic annotations and simulation experiments in a graph database". Database: The Journal of Biological Databases and Curation. 2015. doi:10.1093/database/bau130. ISSN 1758-0463. PMC 4352687. PMID 25754863.{{cite journal}}: CS1 maint: PMC format (link)
  4. ^ Mullen, Joseph; Cockell, Simon J.; Woollard, Peter; Wipat, Anil (2016). "An Integrated Data Driven Approach to Drug Repositioning Using Gene-Disease Associations". PloS One. 11 (5): e0155811. doi:10.1371/journal.pone.0155811. ISSN 1932-6203. PMC 4873016. PMID 27196054.{{cite journal}}: CS1 maint: PMC format (link) CS1 maint: unflagged free DOI (link)
  5. ^ Codd, E. F. (1970-06-01). "A relational model of data for large shared data banks". Communications of the ACM. 13 (6): 377–387. doi:10.1145/362384.362685. ISSN 0001-0782.
  6. ^ Jaiswal, Garima (2013-08). "Comparative analysis of Relational and Graph databases". IOSR Journal of Engineering. 03 (08): 25–27. doi:10.9790/3021-03822527. ISSN 2278-8719. {{cite journal}}: Check date values in: |date= (help)
  7. ^ a b c d "From Relational to Graph Databases". Neo4j.
  8. ^ a b "Examples where Graph databases shine: Neo4j edition", ZeroTurnaround
  9. ^ Silberschatz, Avi (28 January 2010). Database System Concepts, Sixth Edition (PDF). McGraw-Hill. p. E-20. ISBN 0-07-352332-1.
  10. ^ Parker, Lorraine. "IMS Notes". vcu.edu. Retrieved 31 May 2016.
  11. ^ Cite error: The named reference Gutierrez was invoked but never defined (see the help page).
  12. ^ Kuper, Gabriel M (1985). The Logical Data Model: A New Approach to Database Logic (PDF) (Ph.D.). Docket STAN-CS-85-1069. Retrieved 31 May 2016.
  13. ^ "SAP Announces New Capabilities in the Cloud with HANA". 2014-10-22. Retrieved 2016-07-07.

Article Evaluation: Graph Database

The article contains decent information. However, the author(s) did not properly cite the sources for most of its work. There is no way for the readers to distinguish between the authors' opinions and facts from proper sources. There should also be more diagrams or images to help the reader understand the concepts of a graph database. The article is not categorized into subcategories to easily search through.

There are unnecessary comments that could be instead replaced with separate Wikipedia links. An example from the article is "that is, roughly relative to the logarithm of the size of the data." Many examples are written in good nature, but repetitive. The contrast between the relational databases and graph databases moves through the same differences with different examples.

Retrieved from "https://en.wikipedia.org/w/index.php?title=User:Hyeonjungko/GraphDatabases&oldid=865157370"