Different Taxonomy Values for Each Post

I would implement this as such:

Album is a Custom Post Type (CPT). Release date, stores, and store details are post meta-data for the Album CPT.

Meta-data can be structured, so one option would be to store all of an album’s store data as an array of associative arrays similar to the following:

// You would build this array from user-entered data collected from a form in a metabox
$album_stores = [
  [
    "name" => "Amazon",
    "url" => "https://amazon.com/album-name",
    "price_usd" => "23.95"
  ],
  [
    "name" => "Google Play",
    "url" => "https://play.google.com/music/album-name",
    "price_usd" => "22.50"
  ]
]

update_post_meta( $post->ID, "album_stores", $album_stores );
update_post_meta( $post->ID, "album_release_date", $release_date );

If you would like to be able to search or sort albums by store, a store custom taxonomy would be convenient, and could automatically be applied when an Album is published or updated based on the presence of the relevant meta-data. Otherwise, search could also be implemented by modifying or creating search queries to query Album CPT meta-data (this would also allow you to search based on store details like price, or some such).

Register a custom meta-box to the Album CPT in order to provide the user interface for editing the store and release date meta-data.