As for protecting databases (and other things of dubious eligibility such as "business method"), I find the question is not whether it can be patented but how it can be patented. There is almost always a way to get through Section 101 for just about anything other than real abstract ideas, real natural phenomenon, etc. -- not technology that someone tried to cast as any of those exceptions.
Here's a quick test: imagine someone tells you that patenting a database is like patenting gravity.
If your answer is something like mine, "Huh? How so?", then there's a good chance you can get through Section 101 if you know what you're doing.
The line of cases that seem to be applied to things like databases (and data structures) is the "written matter" line of cases. In essence, novelty can't lie in the artistically expressive (or simply written) parts of a thing. The classic example is novel and non-obvious music or artwork stored on a CD. The CD itself or the functional aspects of anything stored on it or the manner in which the stuff stored on it is created or used is not novel at all (in this hypothetical -- it could be, but isn't here).
Of course, like all exceptions, there are exceptions to the exception. If "written matter" is functional (imagine a mark to which a use is to move a lever), it's cool. Is a database functional? Yes, of course it is.
Although, be prepared to include the relevant functional aspects of the database in the claims -- particularly inter-relationships and behavior driven by the database and, in particular, driven/enabled by these inter-relationships.
So, yes, patent protection can be had for a novel and non-obvious database.
As to whether you might infringe, you have to do that same analysis you'd do for any patent -- read the claims and see if any of the claims describe what you do. No cheating by dumbing the claim down to something ridiculous, like "hey, that's essentially claiming making a PB&J sandwich!" The actual language of the claim matters.
Regards.