That wouldn't be hard at all. There's already a concept of "provides". e.g., mysql56-client and mysql60-client "provide" mysql-client, so you make a package depend on "mysql-client" and the solver will be satisfied with either.

They could have been doing this for over 10 years