US Patent 8086598 Query optimizer with schema conversion

Methods, program products and systems for determining, for a database query that does not represent a snowflake schema, a graph comprising vertices each representing a table joined in the query, a directed edge between each pair of vertices of which a first vertex represents a first table and a second vertex represents a second table that is joined in the query with the first table, each of the edges representing one of an outer join and an inner join. Further determining, for the graph, a directed spanning tree that represents an ordering of joins in the query and includes all outer join edges in the graph.