In recent years, the database community has paid increasing attention to the formulation and treatment of preference queries. In this paper, we discuss a number of semantic and computational issues that preference queries raise. First, we examine the currently favored interpretation of such queries in database systems, showing that it is simply inappropriate semantically. Next, we suggest the ceteris paribus semantics as an appealing alternative that has long been accepted by economists and philosophers. Finally, we examine the computational problem of evaluating preference queries using the recently introduced operator BEST. We show that while BEST can be intractable given the ceteris paribus semantics, an appealing alternative, ORD, can be implemented efficiently for a wide class of preference queries.