Navigational Database

A term sometimes used to describe NetworkDatabase (a.k.a. "Codasyl database) and HierarchicalDatabase systems and techniques. This is because one often has to "navigate" from node to node (object-to-object or record-to-record) by "pointer hopping" or "reference hopping". The navigation is characterized by:

Explicit directional instructions like "next", "previous", "nextChild", "toParent", etc.,
Paths (like file paths)
Common use of explicit (imperative) loops to traverse the structure(s) for aggregate calculations or finding/filtering.

This is in contrast to RelationalDatabase techniques which tend to use set notation, LogicProgramming-like or FunctionalProgramming-like techniques, and the concept of a "table" to logically describe what you want rather than how to navigate to get it. In other words, "give me results which satisfy the following expressions(s) or condition(s)". Although this may be possible with navigational "records", a navigational database's lack of "table constraints" makes it more difficult.

See comparisons at http://unixspace.com/context/databases.html

(Perhaps this should be called NavigationalStructures?, because code-centric techniques can also resemble NavigationalDatabases.)

Fans of relational technology use this term pejoratively to describe any non-relational means of data organization or persistence.

see NavigationalDatabaseCodeword?

Why does it have to be pejorative? If you like navigational techniques, then wear it as a badge of honor. I would be interested to see it defended. -- A RelationalWeenie

It's not just a matter of subjective preference - both approaches have distinct advantages and disadvantages. And the term "navigational" is used pejoratively with the relational crowd because in the "classical" domain of databases - long-term storage of enterprise data, used by many applications - navigational databases are a kind of "proven antipattern". They tie the application-independent, long-lived core data too closely to application-dependent, shorter-lived navigational patterns. See DecoupleDataAndNavigationalInformation.

The problem, of course, is this negative connotation is extrapolated beyond the realm of enterprise data to other areas, where navagational data structures (one can, of course, have both navigational and relational sturctures independent of a database) are entirely appropriate.

Some stuff moved to NavigationalVsRelational

Text Indexing

WikiWiki is a NavigationalDatabase of sorts. Sort of. There are certain commonalities between each "record" (topic) such as the reverse index when you click the title, and most information retrieval is done by hopping across links.

If you tried to do Wiki relationally, you'd wind up storing the "reverse index" and then piecing the results together on each hit. For performance, you'd probably tell your RDBMS to keep an index, which is itself a hidden secret navigational database.

I will agree that most RDBMS engines are not very efficient at indexing text. However, that is mostly an implementation issue. Note that if I redid Wiki the way I wanted it, it would use more relational-friendly features. I could perhaps use a separate text indexing tool for non-topic text searches. How relational fits in with text queries is an interesting topic to ponder.

Re: an index, which is itself a hidden secret navigational database

True, but that is a low-level implementation detail to most application developers. It also uses 1's and 0's, but that does not mean that humans should also. We use low level things like binary and navigational structures to build higher-level things, like relational protocols. (I know, a MyAbstractionIsHigherThanYours? HolyWar.)

Plus, it's functionally transparent. You can add or remove indexes from a relational database, and the applications that use the database will still work (just with different performance characteristics). The same is not true for navigational databases - remove a navigational structure from the database, and the applications that use it will break. Want to write a new application that traverses the data in a different way? With navigational databases, you have to touch the database, with relational databases, you don't.

IMHO, and as far as I understand the conversation here navigational databases are more apt for certain purposes (such as directories with hierarchical natures (LDAP, etc)). So, a new application that traverses data stored in a navigational database in a new manner in fact needs a new database altogether, and is in fact a whole different app from the original. If it were on a relational database, yes, you wouldn't need to touch the database, but that would be in fact kludging the data for a new purpose. But why would you want to, say rewrite the telephone directory? Unless you understand the purpose of the data in the first place, you should use the proper tool. Relational databases are for data that have intrinsic relations, while navigational databases are for data with intrinsic structure. So, don't kludge a hierarchical directory into a relational db nor kludge something like a purchasing, sales, inventory system into a hierarchical db.

(Of course, I might be completely wrong on this point. My two cents, correct me if I'm wrong) -JmIbanez

What's the difference beteween data with "intrinsic structure" and data with "intrinsic relations"? Is there some objective standard that one can use to tell the difference?

My experience is that relational databases are the best solution for fast ad hoc queries. If you know that you don't know all of the ways data will be queried, use a relational database as soon as possible. Navigational databases can be faster, but you need to know how the data will be queried up front. -- EricHodges

AreRdbmsSlow

Some databases labeled as NavigationalDatabases actually are not pure navigational. IBM's IMS database had "segments", which are sort of a primitive type of table structure, and within a segment you could issue constraint-based (WhereAndAnd) queries roughly resembling "Amount greater than 40 and state is Arizona". It thus had a foot in the relatioinal door. I wonder if this influenced DrCodd?

I think the "segments" are based on the punched card concept. You have fixed-sized columns and hoped that the cards you used fit the column convention you needed.

It is possible that the term "navigational database" originated in speeches given by Dr. Bachman, a competitor to DrCodd's ideas. A quote from ModernDinosaur:

"Bachman talked about "programmer as navigator" in the sense that database accesses is essentially navigation from one record to another along the edges of the Network or Hierarchical data model"

DocumentObjectModel (DOM) is a smaller example of a NavigationalDatabase. DOM is mostly, but not entirely a HierarchicalDatabase, since lower leaves can reference higher leaves. It would be interesting to contrast it to a relational version (NonOopGuiMethodologies).

DocumentObjectModel (DOM) and XML remind me of IMS the proprietary hierarchical IBM database. ??

These sorts of contrasts have been made, altough only informally, as in this very page. In general, socalled "semi-structured" data seems to be best served with a navigational model.

I'm in the process of creating bases for a formal analysis of this issue, see the UntypedNetworkHypothesis.

--MariusAmadoAlves

I am curious to see your opinion on "dynamic relational", as described in MultiParadigmDatabase.

"dynamic relational" not found there.--MariusAmadoAlves

It is an alias for what is being described there.

I have generally concluded that navigational structures are essentially webs of dictionary arrays (maps) with pointers to other maps. Perhaps they should be called "map-based databases". -- top

I think of navigational databases (and I like top's "map-based databases") for SemiStructuredData? collections, where you don't really know, beforehand, what it's shape is going to be, or what you're going to need.

If I was going to model my understanding of the world, I'd do it with a NavigationalDatabase.

A RelationalDatabase, on the other hand, strikes me as appropriate for large collections of regular data that you have a pretty good idea of how you're structuring it, for efficient retrieval.

I can see situations where I would take something that was semi-structured, and, as the data in it began to take on a uniform form, turn it into structured, relational data.

When I think of the SemanticWeb, I envision it as a mixture of the loose semi-structured data (navigational based) and large blocks of relational data.

If I were to remake the ResourceDescriptionFramework (RDF) in light of this thought, I'd have two basic forms: tabular, and nodal -- and I would consider a sort of glue for connecting them together, across the network, as NetworkedData? / LinkedData?.

-- LionKimbro

My preference of tools would look something like this:

Unstructured - MultiParadigmDatabase
Semi-Structured - DynamicRelational
Structured - "Typical" RDBMS

As we go down the list, more constraints are added. But, the one thing that may be the dividing line between "navigational" and "relational" is the requirement that each row belong to one and only one "table" and that there be multiple tables. This makes sense because "relational" is a mathematical term for "table" (and not "key links", as is a common misconception). In the MultiParadigmDatabase, tables (entities) are optional, so out-of-the-box it is "navigational".

But, what separates MultiParadigmDatabase from many navigational databases is that one can do predicate filtering (WHERE clause) on the rows (maps) instead of having to just follow pointers. I am not sure whether predicate filtering affects the classification of a database. Perhaps we need a more sophisticated DB classification system. Predicates and one-table-per-node may be orthogonal features. But then again, I've never seen a non-predicate one-table-per-node database. Whether this is just a historical habit or there is some natural relationship between the two requires more pondering.

-top

CategoryClassification, CategoryDataStructure