I'm struggling with this same issue and have run into problems with Taxonomy. The organization of database records you describe indicates several different many-to-many relationships. Although Taxonomy supports this, the issues come up when you try to build views without duplicate records.
Taxonomies provide a comma-separated list of terms assigned to posts. If you have people assigned to multiple roles and also multiple departments, it's difficult, if not impossible to easily display either a list of departments the user is assigned to, and under each, the roles they have in each department. Conversely, it's as difficult to display a list of roles to which a user is assigned and, under each role, the department in which they perform that role.
You'll need to find each instance where the taxonomy terms match between users, departments, and roles. That means creating some custom code that can accept the list of taxonomy terms assigned to each post, and match those to the terms assigned to each child post - assuming your posts are organized that way.
Although it means more nesting of views, I've found it more versatile to create Custom Post Types (CPTs) to link between each many-to-many relationship.
You would have:
People
People-to-Department links
Department
Department-to-Role links
Role
If you need it, you can also have People-to-Role links.
The linking post types have no editor, title, or admin menu. All they do is store the post ID of the 2 posts they relate. The linking post types are configured to be children of the 2 post types they link.
Then, you search Roles, for example. For each found role, you search the linking db for each child of the current Role. For each found record, you search for all the parent posts in Department to display all of the related departments.
I've needed to use a pen and paper to sketch the structure of each view, as it gets really, really confusing without a lot of practice, but, this approach provides the most robust structure. You can change People, Roles and Departments at any time and the database stays organized.
When editing any CPT, the related links interface is available, which makes managing the data on the backend relatively straightforward - not particularly fast, but intuitive.
The other significant problem is that Users is not treated like a standard CPT in WP-Types. That means that standard WP users are not as easy to integrate into views of other CPTs. That's probably for security reasons, but, I don't think it's a necessary restriction.
I like to use the WP-Users type whenever possible because it provides all of the lost password functionality, email notification and session management stuff that would otherwise have to be built by hand.
What I do to make this all work with users is to create a "Pseudo-User" CPT. There are one of these Pseudo-User records for each WordPress user, and the WP user is the author of their own, individual Pseudo-User post. Now, I can use the Pseudo-User CPT in my views just like any other CPT, and I can access user information, like email, display name, etc., but displaying the author post-meta within the Views editor.
I have requested that WP-Types incorporate this functionality into Views. A checkbox in the settings should just enable this pseudo-post-type, and just maintain one post for each WP user, but keep the pseudo-type completely hidden. Just provide easier access to user info within the Views editor.
Until then, this work around does make things work, but can be time consuming to set up if you have lots of users initially.
I'll keep watching this post to see if you have success using Taxonomy, otherwise, feel free to keep in touch and I'll help you as I can. It seems that I can more clearly understand what I'm working on if I try to explain it to others in a similar situation.