Jump to content

Navigational database

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Mhkay (talk | contribs) at 10:29, 22 January 2018 (Start of a clean-up). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

A navigational database is a type of database in which records or objects are found primarily by following references from other objects. The term was popularized by the title of Charles Bachman's 1973 Turing Award paper, The Programmer as Navigator[1]. This paper emphasized the fact that the new disk-based database systems allowed the programmer to choose arbitrary navigational routes following relationships from record to record, contrasting this with the constraints of earlier magnetic-tape and punched card systems where data access was strictly sequential.

Although Bachman described the concept of navigation in abstract terms, the idea of navigational access came to be associated strongly with the procedural design of the CODASYL Data Manipulation Language. Writing in 1982, for example, Tsichritzis and Lochovsky[2] state that "The notion of currency is central to the concept of navigation." By the notion of currency, they refer to the idea that a program maintains (explicitly or implicitly) a current position in any sequence of records that it is processing, and that operations such as GET NEXT and GET PRIOR retrieve records relative to this current position.

Navigational database programming thus came to be seen as intrinsically procedural; and moreover to depend on the maintenance of an implicit set of global variables (currency indicators) holding the current state. As such, the approach was seen as diametrically opposed to the declarative programming style used by the relational model. The declarative nature of relational languages such as SQL offered better programmer productivity and a higher level of data independence (that is, the ability of programs to continue working as the database structure evolves.) Navigational interfaces, as a result, were gradually eclipsed during the 1980s by declarative query languages.

During the 1990s it started becoming clear that for certain applications handling complex data (for example, spatial databases and engineering databases), the relational calculus had limitations. At that time, a reappraisal of the entire database market began, with several companies describing the new systems using the marketing term NoSQL. Many of these systems introduced data manipulation languages which, while far removed from the CODASYL DML with its currency indicators, could be understood as implementing Bachman's "navigational" vision. Some of these languages are procedural; others (such as XPath) are entirely declarative. Offshoots of the navigational concept, especially the graph database, found new uses in modern transaction processing workloads.

Description

Navigational access is traditionally associated with the network model and hierarchical model of database interfaces, and some have even acquired set-oriented features.[3] Navigational techniques use "pointers" and "paths" to navigate among data records (also known as "nodes"). This is in contrast to the relational model (implemented in relational databases), which strives to use "declarative" or logic programming techniques that ask the system for what to fetch instead of how to navigate to it.

For example, to give directions to a house, the navigational approach would resemble something like "Get on highway 25 for 8 miles, turn onto Horse Road, left at the red barn, then stop at the 3rd house down the road", whereas the declarative approach would resemble "Visit the green house(s) within the following coordinates...."

Hierarchical models are also considered navigational because one "goes" up (to parent), down (to leaves), and there are "paths", such as the familiar file/folder paths in hierarchical file systems. In general, navigational systems will use combinations of paths and prepositions such as "next", "previous", "first", "last", "up", "down", "owner", etc.

"Paths" are often formed by concatenation of node names or node addresses. Example:

Sample database nodes: A labeled graph on 6 vertices and 7 edges. (Numbers are used for illustration purposes only. In practice more meaningful names are often used. Other potential attributes are not shown.)
 Node6.Node4.Node5.Node1

Or 

 Node6/Node4/Node5/Node1

If there is no link between given nodes, then an error condition is usually triggered with a message such as "Invalid Path". The path "Node6.Node2.Node1" would be invalid in most systems because there is no direct link between Node 6 and Node 2.

The usage of the term "navigational" allegedly is derived from a statement by Charles Bachman in which he describes the "programmer as navigator" while accessing his favored type of database.[4]

Except for hierarchical file systems (which some consider a form of database), navigational techniques fell out of favor by the 1980s. However, object oriented programming and XML have kindled a renewed, but controversial interest in navigational techniques.

Critics of navigational techniques view them as "unstructured spaghetti messes", and liken them to the "goto" of pre-structured programming. In other words, they are allegedly to data organization what goto's were to behavior flow. In this view, relational techniques provide improved discipline and consistency to data organization and usage because of its roots in set theory and predicate calculus.

Some also suggest that navigational database engines are easier to build and take up less memory (RAM) than relational equivalents. However, the existence of relational or relational-based products of the late 1980s that possessed small engines (by today's standards) because they didn't use SQL suggest this is not necessarily the case. Whatever the reason, navigational techniques are still the preferred way to handle smaller-scale structures.

A current example of navigational structuring can be found in the Document Object Model (DOM) often used in web browsers and closely associated with JavaScript. The DOM "engine" is essentially a light-weight navigational database. The World Wide Web itself and Wikipedia could potentially be considered forms of navigational databases, though they focus on human-readable text rather than data (on a large scale, the Web is a network model and on smaller or local scales, such as domain and URL partitioning, it uses hierarchies). In contrast, the Linked Data facet of the Semantic Web is specifically concerned with network-scale machine-readable data, and follows precisely the 'follow your nose' paradigm implied by the navigational idea.

A new kind of navigational databases[citation needed] has recently[when?] emerged, the graph databases. This category of databases is often included as one of the four family of the NoSQL databases.

Examples

See also

References

  1. ^ "The programmer as navigator". Portal.acm.org. doi:10.1145/355611.362534. Retrieved 2012-10-01.
  2. ^ Dionysios C. Tsichritzis and Frederick H. Lochovsky (1982). "Data Models". Prentice-Hall. p. 67. ISBN 0-13-196428-3.
  3. ^ Błażewicz, Jacek; Królikowski, Zbyszko; Morzy, Tadeusz (2003). Handbook on Data Management in Information Systems. Springer. p. 18. ISBN 3-540-43893-9.
  4. ^ "The programmer as navigator". Portal.acm.org. doi:10.1145/355611.362534. Retrieved 2012-10-01.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Navigational_database&oldid=821742687"