The main target of all solutions is the data integrity and efficiency.

Main idea is storing all documents in database and add some flags to documents. Flags, for ex., can be "is_current_version", "is_deleted". Deletion of document in this case is very simple and fast operation - change the flag in database to 'Y'.
Changing the version take a little bit more work - set flag "is_current_version" and reset this flags in previous document. Version number is max()+1.

So, the solution can looks as in below.
1. In table xwikidoc add few fields:
xwd_id number – existing field, document ID, unique identifier, primary key.
xwd_guid number – the global ID. The common ID of the documents within a single version branch. Initially, it is equals xwd_id.
is_deleted char(1) default 'Y' – deletion flag
is_current_version char(1) default 'Y' – flag of current version
xwd_varsion varchar(255), – existing field equals version label
xwd_version_number number, – the sequenced number of version. XWD_ID will change together with version number.
xwd_expire_date date, – the expiration date - after this date document must be marked as "deleted" (is_deleted='Y')
xwd_purge_date date – after this date document must be deleted from database

2. Actual document can be found with this query
select * from xwikidoc where is_deleted='N' and is_current_version='Y' and xwd_guid=<ID>
Deleted document (in trash) can be found with this:
select * from xwikidoc where is_deleted='Y' and xwd_guid=<ID>

3. All referenced objects like attachments should have two foreign keys - first using GUID, second using ID. If attachments does not have versioning, second foreign key can be omitted. Actual attachment also should have flag "is_current_version". Will attachments duplicate when parent document was changed ? No. Never. But actual attachment will continue refer to previous version of document.

4. Actual attachments can be found with this:
select * from xwikiattachment where is_current_version='Y' and doc_guid=<doc GUID>

5. How to find attachments for previous version of document ?
select * from xwikiattachment where doc_id <= <referenced doc id>
Of course, this work well if ID is sequenced. But in xwiki using hash-derived ID In current version of xwiki this query looks more complicated.

7. Maintenance procedure can purge old documents from database and mark expired docs as deleted.

8. Productivity. Indexes are very important.
Do not care about numerous of recored in tables - the databases exist specially for this. Don't remember the indexes.

• create XWikiRecycleBinStoreInterface to store/restore deleted documents
• add XWiki.deleteDocument(XWikiDocument doc, boolean totrash, XWikiContext context)
• modify delete.vm: add link to move to recycle bin.
• delete logic in DeleteAction
• modify deleted.vm: add link to restore and delete.
• redirect to deleted.vm, if document in recycle bin.

• XWiki.deleteDocument(XWikiDocument doc, boolean totrash, XWikiContext context) should be only in com.xpn.xwiki.XWiki
• com.xpn.xwiki.api.XWiki.deleteDocument should not have the boolean parameter, should always call the privileged method with "true"
• If admins want to completely remove the document, bypassing the recycle bin, they can do this using programming rights. However, it shouldn't be easy to bypass the recycle bin, as this is a security mechanism that prevents attackers from emptying the wiki
• I think that allowing admins to bypass the minimum time restriction should be configurable, defaulting to "yes"

On another problem, that of deleting a document more than once, the RecycleBin table should also have a "number" property, identifying the instance of the document in the recycle. Deleting a document when there's already one or more instances in the RecycleBin should create a new instance with a different number.

• When restoring a document, the user should be able to select which version he wants to restore.
• If there is only one version in the database, skip the above question, just restore the only trashed version
• This solves another problem, that of restoring a document that was re-created. If trying to restore an existing document, give a notice that the document already exists, and it should be moved to the recycle bin before restoring an older version.

• to delete To recycle bin user need to be owner of document or admin
• to delete From recycle bin user need be admin (as semantic of "delete" right)
• to restore From recycle bin user need to have new "undelete" right or need to be admin.
  we can change semantic of "delete" right to allow granting "delete" right to not admins.