Algorithm for identifying correct subset My raw data is composite, but for simplicity sake let's say they consist of three elements. One might consider a sample set thusly.

[A,a,1]
[A,b,1]
[B,b,1]
[B,b,2]
[C,b,3]
[A,c,3]


I need to create a subset that satisfy two key criteria.


All combinations of the two last columns is represented (lower case and numeric)
All upper case (first column) is represented at least once.


... in as few rows as possible. The data is not evenly distributed, meaning that e.g 80 percent of the rows in the input data may have b,1. 
If that was the case, it would be wasteful to include  A,b,1 row, because I would have to include A,a,1 as well in order to make sure that a,1 combination is represented.

Though large data, the data is in memory. Accessing and iterating is relatively cheap. The data is static and may be processed over multiple passes .

Language is C#.

I'm not too happy about the title of this question, so if there is any key term that better describes this problem, feel free to comment/edit.
You can solve this by looking for a maximum cardinality matching in a bipartite graph, then covering remaining vertices arbitrarily.

Make a bipartite graph:


In the left part of the graph, make a vertex for every capital letter.
In the right part of the graph, make a vertex for every combination of lowercase letter and number.
For each record, make an edge (which necessarily goes from a vertex on the left to one on the right) corresponding to the two vertices covered by the record.


Now run an algorithm for finding a maximum cardinality matching in a bipartite graph, such as the Hopcroft-Karp maximum flow algorithm.  This picks a subset of edges (records) that together cover the most possible distinct combinations of capital letter and (lowercase letter + number).  That is, each chosen record hits both a capital letter, and a (lowercase letter + number) pair that are not hit by any other chosen record.

If the matching saturates (touches) every vertex, you have a "perfect" solution!  Otherwise, for each remaining vertex, you need to pick a record incident on that vertex -- it doesn't matter which record you pick, because it definitely won't be incident on any untouched vertices on the other side (if it was, then it would have been included in the matching already).