Query optimization for sequential execution of non-recursive queries has reached a high level of sophistication in commercial DBMS. The successful application of parallel processing for the evaluation of recursive queries will require a query optimizer of comparable sophistication. The groundwork for creating this new breed of query optimizer will consist of a combination of theoretical insight and empirical investigation. Restricting our attention to linear recursive queries, we illustrate this process by developing a family of query processing strategies and, through experiments on a parallel computer, obtaining the basic information needed for an optimizer's heuristics.