Within an application according to JPA2/Hibernate/Oracle+Spring+Wicket, I personally use the next model:

public class Item {
 private String name;
 private Set<Application> apps;
 private ...
}

public class Application {
 private String applicant;
 private Item item;
 private Status status;
 private ...
}

The mapping between Item and Application is the fact that every item has numerous programs, every application indicates only one item.

Now I wish to look for Programs that satisfy an intricate group of criteria and it would be great when the result set was some pairs < Item, List< Application >> (it can't be just Set< Item >, because usually merely a subset of programs for any particular item would fulfill the criteria).

Would you recommend us a way how to get this done? My first idea ended up being to query first for pairs < ItemID, AppID > after which iterate with these and convey the end result set by hand, however it appears quite cumbersome and ineffective.

If you wish to express it in one query (so, you utilize JOIN to convey criteria around the Applications), querying for pairs is the only method to get it done - that's how relational databases work.

I' suggest using JPA2 criteria queries with tuples and subqueries. Something within the type of (pseudocode):

CriteriaBuilder cb = entityManager.getCriteriaBuilder();
CriteriaQuery<Tuple> crit = cb.createTupleQuery();
Subquery<Application> subquery = cb.subquery(Application.class);
subquery.where(...);
subquery.correlate(...);
crit.select(cb.tuple(cb.from(Item.class), subquery);

It's pseudocode because I not have the exact syntax for subqueries in your mind at this time with no Eclipse to give it a try, sorry. There is a nice summary of subqueries in Keith, Schincariol. Pro JPA 2: Mastering the Java Persistence API.