I disagree with the notion that A Deepness in the Sky requires having read A Fire Upon the Deep. In fact, I would go so far as to say that each ends with an open question that is answered by the other, so that no matter which one you read first you will discover the answer in the second.