Navigational database
 | This article needs additional citations for verification. (July 2007) |
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, and conventionally describes data manipulation APIs in which records (or objects) are processed one at a time, iteratively. The essential characteristic as described by Bachman, however, is finding records by virtue of their relationship to other records: so an interface can still be navigational if it has set-oriented features.[3] Navigational access by following named relationships can be contrasted with the relational model (implemented in relational databases), which uses "declarative" or logic programming techniques that ask the system what to fetch rather than how to reach 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....".
Most criticisms of navigational APIs fall into one of two categories:
- Usability: application code quickly becomes unreadable and difficult to debug
- Data independence: application code needs to change whenever the data structure changes
For many years the primary defence of navigational APIs was performance. Database systems that support navigational APIs often use internal storage structures that contain physical links or pointers from one record to another. While such structures may allow very efficient navigation, they have disadvantages because it becomes difficult to reorganize the physical placement of data. It is quite possible to implement navigational APIs without low-level pointer chasing (Bachman's paper envisaged logical relationships being implemented just as in relational systems, using primary keys and foreign keys), so the two ideas should not be conflated. But without the performance benefits of low-level pointers, navigational APIs become harder to justify.
Hierarchical models often construct primary keys for records by concatenating the keys that appear at each level in the hierarchy. Such composite identifiers are found in computer file names (/usr/david/docs/index.txt), in URIs, in the Dewey decimal system, and for that matter in postal addresses. Such a composite key can be considered as representing a navigational path to a record; but equally, it can be considered as a simple primary key allowing associative access.
As relational systems came to prominence in the 1980s, navigational APIs (and in particular, procedural APIs) were criticized and fell out of favour. The 1990s, however, brought a new wave of object-oriented databases that often provided both declarative and procedural interfaces. One explanation for this is that they were often used to represent graph-structured information (for example spatial data and engineering data) where access is inherently recursive: the mathematics underpinning SQL (specifically, first-order predicate calculus) does not have sufficient power to support recursive queries, even those as simple as a transitive closure.
A current example of a popular navigational API can be found in the Document Object Model (DOM) often used in web browsers and closely associated with JavaScript. The DOM is essentially an in-memory hierarchical database with a navigational API. 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 database[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
- ^ "The programmer as navigator". Portal.acm.org. doi:10.1145/355611.362534. Retrieved 2012-10-01.
- ^ Dionysios C. Tsichritzis and Frederick H. Lochovsky (1982). "Data Models". Prentice-Hall. p. 67. ISBN 0-13-196428-3.
- ^ Błażewicz, Jacek; Królikowski, Zbyszko; Morzy, Tadeusz (2003). Handbook on Data and Management in Information Systems. Springer. p. 18. ISBN 3-540-43893-9.
External links
- DB-Engines Ranking of Navigational DBMS by popularity, updated by month