I'm designing a HATEOAS API for internal data at my company, but have been having troubles with the discovery of links. Consider the following set of steps for someone to retrieve information about a specific employee in this system:

1. User sends GET to http://coredata/ to get all available resources, returns a number of links including one tagged as rel = "http://coredata/rels/employees"
2. User follows HREF on the rel from the first request, performing a GET at (for example) http://coredata/employees

The data returned from this last call is my conundrum and a situation where I've heard mixed suggestions. Here are some of them:

1. That GET will return all employees (with perhaps truncated data), and the client would be responsible for picking the one it wants from that list.

2. That GET would return a number of URI templated links describing how to query / get one employee / get all employees. Something like:

   "_links": {
       "http://coredata/rels/employees#RetrieveOne": {
           "href": "http://coredata/employees/{id}"
       },
       "http://coredata/rels/employees#Query": {
           "href": "http://coredata/employees{?login,firstName,lastName}"
       },
       "http://coredata/rels/employees#All": {
           "href": "http://coredata/employees/all"
       }
   }
   

I'm a little stuck here with what remains closest to HATEOAS. For option 1, I really do not want to make my clients retrieve all employees every time for the sake of navigation, but I can see how using URI templating in example two introduces some out-of-band knowledge.

My other thought was to use the RetrieveOne, Query, and All operations as my cool URLs, but that seems to violate the concept that you should be able to navigate to the resources you want from one base URI.

Has anyone else managed to come up with a good way to handle this? Navigation is dead simple once you've retrieved one resource or a set of resources, but it seems very difficult to use for discovery.