People and machines are collecting data at an unprecedented rate. Despite this newfound abundance of data, progress has been slow in sharing information for open science and other research initiatives. Many such efforts are stymied by privacy concerns and regulatory compliance issues. For example, many hospitals are interested in pooling their patient records for research, but none may disclose the individual tuples in their databases without violating patient confidentiality. It is in this context that we propose the Private Data Network (PDN), a federated database for querying over the collective data of mutually distrustful parties. In a PDN, member databases do not reveal their query inputs to one another or the query writer. Instead, the user submits their query to a honest broker that plans and coordinates its execution over multiple private databases using secure multiparty computation (SMC). When a PDN evaluates a query, each party’s computation is oblivious or agnostic to the inputs of others in its program counter and memory traces. We introduce a framework for executing PDN queries named smcql. This system rewrites SQL statements into SMC primitives to produce query results over the union of its source databases without revealing sensitive information about individual tuples to peer data providers or the honest broker. Only the honest broker and the querier receive the results of a PDN query. For fast secure query evaluation, we explore a heuristics-driven optimizer that minimizes the PDN’s use of secure computation and partitions its query evaluation into scalable slices.