Use case:
We are working on a project where entities are cross linked. My question is how would it be the best to store these relations.
Entities:
-person
-company
-skill
-job
Relations:
Friends:
person < - > person
CV:
person < - > skill
Working at:
person < - > company
Jobs available:
job < - > company
Skills needed for a job:
job < - > skill
Problem/Motivation
to find the best matching job (that require skills that you have) from the companies where your friends and friends-of-friends work at.
Proposed resolution
1. approach:
Using the Relation Module (https://www.drupal.org/project/relation) but change / rewrite / extend the storage to Neo4j
2. approach:
Use Search API (https://www.drupal.org/project/search_api) to index into neo4j. Write a backend that allows to persist into it.
See this: https://www.drupal.org/node/2286293
Open for discussion. Propose your solution.
MySQL is out of question since there are too many entities and too much hops in the query.

Comments
Three different concepts
Your task contains three different concepts.
First, it's about maintaining the relationships and persisting them. Relation is a good fit here. You might also use other regular building blocks from Drupal.
Then, you have the concept of matching. For this, you need a matching engine. Native SQL is not a good match. You should go through an indexing service and put the data stored into a database that is optimised for matching. Solr or Graph databases.
Search API is a perfect backend to maintain indexes.
Defining how to map these things into the index should go into the field / facet configuration of search API.
You might need to write own data processors / mappings in case search API is not mature enough. But it provides a framework to make these things easy and clean.
Finally, matching is perfoming a query in that specific database domain leveraging its technology.
In most cases, this query needs to be manually written anyway. It has nothing to do with the relationship or Search API. You will directly access the index in neo4j or solr with pretty high probability.
With Solr though, defining boos functions is already a good start...
I strongly recommend not to try to find one solution that solves all these problems at the same time.