SqlDependencyCache uses SqlDependency and SqlDependency deploys at runtime a set of services, queues and stored procedures in your database as part of its infrastructure. You can read this article on more details what really happens The Mysterious Notification.
When you create your site map provider, you provide a connection string. This connection string specifies either a SQL login and password, or it specifies that SSPI (or Trusted, or Integrated) Authentication should be used. When a user and password are provided then this user is used to log in into your application database (the ASP database). When SSPI is used then the conenction is made using the ASP thread identity, which is either the app pool identity or the impersonated user identity. Whichever login ends up being used, this login must have the priviledges necessary to deploy the SqlDependency infrastructure (create a queue, create a service, create a stored procedure). The simplest way is to simply make this login's user in the database member of the db_owner role (which is the correct wording for what the article calls 'dbo priviledges').
So depending on yoru connection string, your app pool identity and your impersonation settings, the database user that corresponds to the login used by the map provider must be added to the db_owner role. I can't tell what you need to do, because it all depends on the variable factors enumerated above.