Index: trunk/Nebulous-Server/lib/Nebulous/Server/SQL.pm
===================================================================
--- trunk/Nebulous-Server/lib/Nebulous/Server/SQL.pm	(revision 24637)
+++ trunk/Nebulous-Server/lib/Nebulous/Server/SQL.pm	(revision 24638)
@@ -217,5 +217,5 @@
     copy_instances_to_deleted => qq{
         INSERT INTO deleted 
-        SELECT NULL, vol_id, uri
+        SELECT vol_id, uri, NULL
         FROM instance
         WHERE
@@ -678,8 +678,9 @@
 
 CREATE TABLE deleted (
+    vol_id INT NOT NULL,
+    FOREIGN KEY(vol_id) REFERENCES volume(vol_id),
+    uri VARCHAR(255) NOT NULL,
     timestamp TIMESTAMP,
-    vol_id INT NOT NULL,
-    uri VARCHAR(255) NOT NULL,
-    PRIMARY KEY(timestamp),
+    PRIMARY KEY(vol_id, uri),
     KEY(vol_id),
     KEY(uri)