Implement foreign key in database or application?

Answer 1

Why not use both?

Foreign keys, check constraints etc are known as "Declarative Referential Integrity" for a reason. They protect your data. What if you add a bulk load next month, or you have to run a SQL script to change data?

Another point would be that the database engine is the correct tool for this.

Answer 2

Since it's a many-to-many relationship, you'll want a cross-reference table rather than a simple foreign key column.

So the Category table does not have a FK to Classified, and Classified does not have a FK to Category. Instead you can have a new table :

XrefCategoryClassified
  FK to Category NOT NULL
  FK to Classified NOT NULL

This is a typical way to implement a many-to-many relationship. And now, instead of worrying about NULLable fields if two records aren't related, you simply care about the existence or non-existence of a xref record

Answer 3

Absent compelling reasons to do otherwise, I'd enforce referential integrity at the database level; after all that's (partly) what an RDBS is good for.

And since you'll likely have some sort of mapping table to define the many-to-many relationship between Category and Classified, it seems like a no-brainer to put your constraints there. Your queries will thank you for it later.