If I'm using a custom post type for a Movie or a TV show episode, I may use a taxonomy for "actors" and assign all the actors related to the work to it, but I'm not sure how, besides of that, I can also add the character the actor is playing in said work. The characters themselves may or may be not a taxonomy, as sometimes one also needs extra space for adding notes, like "John Doe (voice)" or "John Smith (via stock footage). I can figure something like a metabox with columns for each thing, yet I'm not sure how to make it harmonious (or do it at all).
You could simply use the "pods"-plugin (for WordPress) from Matt Gibs and Scott Kingsley Clark. It's exactly what you searching for. Take a look at the doku and look specificaly at "pick columns". Aside from that it has a nice and ajax driven interface and builds it's database tables next to wordpress and doesn't make use of the default tables (there's nothing wrong with adding new tables). It really converts Wordpress to a full CMS system. I tried it in some projects and was easily able to achieve everything i wanted. A big plus is the irc-chat where you find a nice, friendly and helpful croud and the developers. An here goes another plus: When you feel comfortable with pods, then add pods UI to your weaponary. :)
Wish you best!
even though the evolution from blog to CMS is somehow naturally (as Matt Mullenweg expressed it once), it does not mean that wordpress is a CMS that can express complex data structures.
You might wonder about what actually is complex in your question. Well, what you are basically try to do in wordpress terms is to add a taxnomoy on to a taxonomy. Such a thing does not exists in worpdress. You can add a taxonomy to posts and that's it. It's not reciprocal.
But what you can do with wordpress is to mutate through slugs. Which can mean: You can combine datatypes over a common named slug value, which is a simplified, normalized value of a taxonomy or post title that is already used in the resolution of content (query of something by URL, also known as permalinks in wordpress).
So to say for a simple solution: The taxnonomy of actor shares the same slug for the actor name as posts for the actor do. Those posts (which are of a custom type) do have a custom taxonomy which represent a roles name (to add the character the actor is playing in a work). Next to that, you add a taxonomy of work to this post typeto query both: Actor->Role and Actor->Play While Play->Role is still maintained.
It's not really optimal, but this is WordPress™ and you asked for it here, it's at least some way you could do it.
If this sounds too complicated, look for a CMS that is offering own content types in which you can just represent the data you want to express. One that ships with database abstraction and a form generator is Kajona3, which still is pretty lighweight and mature. LGPL license. But to that's more or less out of the scope of this site.