Preference-based queries often referred to as skyline queries play an important role in cooperative query processing. However, their prohibitive result sizes pose a severe challenge to the paradigm's practical applicability. In this paper we discuss the incremental re-computation of skylines based on additional information elicited from the user. Ex-tending the traditional case of totally ordered domains, we consider preferences in their most general form as strict partial orders of attribute values. After getting an initial sky-line set our approach aims at incrementally increasing the system's information about the user's wishes. This additional knowledge then is incorporated into the preference information and constantly reduces skyline sizes. In particular, our approach also allows users to specify trade-offs between different query attributes, thus effectively decreasing the query dimensionality. We provide the required theoretical foundations for modeling preferences and equivalences, show how to compute incremented skylines, and proof the correctness of the algorithm. Moreover, we show that incremented skyline computation can take advantage of locality and database indices and thus the performance of the algorithm can be additionally increased.