Even with procedural generation, you will still need a permanent record for every star once it has been visited.
Sure, you can seed a stars base data as a single compressed long byte, but once that seed is expanded you'll need to track who, what, where, how much etc...
A Database will choke over 10 Billion Records, much less 400 Billion.
In principle I don't think you would necessarily need a permanent record for every star, but I'd certainly agree it would be better to have one for gameplay reasons. But, in reality, who is going to visit 10 billion star systems? I doubt many gamers would get beyond a few thousand. Even a few million should be "doable" in database terms.
They do plan on having multiplayer, though, and I'm not sure how many players might be in each game. Even then, I don't know whether the players could get beyond the database limits.
Anyway, I don't want to end up as some kind of Elite Dangerous Warrior. I was really just intending to report what the developers said they were hoping to achieve. I do have my doubts about whether they will achieve it. In fact, they originally said they planned a release date of March 2014 (which I thought ambitious) and they're now talking in terms of an extended beta somewhat beyond March 2014.
I do agree with Canute that 99.9% (probably more) of the galaxy would be uninteresting for most players, including me. But it's kind of nice to know it's there ...