It's pretty rare to actually delete data from a database. It's almost always flagged in a way that the system is supposed to ignore.
But even if you've never had a Facebook account, they create a shadow profile by tracking you through the share on Facebook buttons on websites.