In this paper, we describe data support in an information system to support contextual, online negotiation of privacy contracts for e-commerce on the Semantic Web. Context is important to the user as one user rule about any single private data item may not fit all situations. For privacy negotiation, we introduce a usage concept consisting of a triple of P3P-defined elements (purpose, recipient, retention) upon which both users and businesses can usefully negotiate. Further we propose a negotiation terminology model to support subdivision of complex user rules into sub-preferences and business? data requests into smaller sub-requests. We also exploit the disjoint data set types in the P3P schema for fast determination of whether negotiation may be useful. We utilize an ontological representation of the P3P data schema in a novel approach to finding relevant substitute data for counteroffers within a negotiation session. A prototype Web system is running.