I just saw a presentation on Franz's Allegro-graph - a system that stores triples up to the billions with very advanced query abilities: We are seriously considering using this: (they have a free java version that supports up to 50,000,000 triples) http://agraph.franz.com/allegrograph/