In all my years with database systems, I have never heard of the term "problem space". I even went back to my old textbooks from when I studied database systems in graduate school and we never used that term there either. On the web, I did find the term "problem space" defined here:
From the above website, basically the problem space is the list of rules, tasks, and outcomes needed to solve a problem. Moving this definition into the database world, I would add that the problem space also contains the entities and attributes needed to help solve the problem, or solve the business needs the database needs to support.
This was first published in March 2008