We settle a number of questions concerning definability with
an extra predicate for classes of semi-linear sets. These
questions are motivated by the constraint database model for
representing spatial data. We give new results both on the
positive and negative side: we show that in first-order logic one
can not query a semi-linear set as to whether or not it contains a line or whether two points are reachable on a line through the set. However, we show that some of these queries become definable if
one makes small resetrictions on the semi-linear sets considered. We also define query languages that allow limited second-order qunatification, and prove bounds on the expressive power of these richer languages.
