What kind of database should I use?
It'd help more if you could be more specific about what you're modeling, as it's hard to picture at the moment, for me at least.

For tree structures, in SQL, any database that supports Recursive Common Table Expressions is a good choice (any major one other than MySQL).

For historical data, the History Table pattern has proven to be effective. For table foo, make a table foo_history and copy-on-write from foo to foo_history. An example.

IBM's DB2 supports SQL:2011 Temporal, which lets you have foreign keys based on time, and is the only db that supports it that I know of.