Many modern Relational Database Management Systems automatically support referential integrity, i.e. when you try to delete a tuple which has a reference (in the form of foreign key, for example), the DBMS doesn't complete the operation and brings an error.
Consider a database where every table has an attribute, which indicates if a tuple is deleted or not. So no data is actually deleted from the database, but is marked as deleted instead. If a tuple is marked as deleted, all its references need to be marked as deleted too or an error should occur. How can this be supported?
Is performing additional checks (programmatically or with triggers) before deleting a tuple the only way to have referential integrity? Are there any accepted practices or algorithms?
Edit: This flag is mostly used for statistics, and partially for data recovery after a long period of time. It is filter with a special meaning, and right now when queries are made, referential integrity is checked right in the query, which is extremely error prone and not reliable at all.