Everything in a computer's memory is related by existing in a uniform address space.
Key-value relationships can be ordered implicitly or explicitly, either by describing an algorithm to sort the keys, or an algorithm that creates a new indexing by comparing the values.
Caching data creates a relationship with manually defined logic.
I think the right question is "how formalized are the relationships?" and a related one is "how reflective is the data?" Programmers have plenty of ways to access data both formally and informally - the informal methods are often closer to the machine, but remove context that would help to automate and verify the process. You can also have data that doesn't say much about its context, and data that is very heavily cross-referenced.
NoSQL, to me, seems to be mostly about relaxing the heavy formalization of SQL - to shortcut to simpler or even incomplete descriptions of data, and deal with the resulting fallout later, in the same way that dynamic languages eschew static checking. Good if your needs are simple, potentially dangerous if your data becomes complex.