--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -2301,38 +2301,40 @@ function needsTombstone(item) {
 // in the `moz_bookmarks_deleted` table, and only written for "NORMAL" items.
 // After each sync, `PlacesSyncUtils.bookmarks.pushChanges` drops successfully
 // uploaded tombstones.
 function insertTombstone(db, item, syncChangeDelta) {
   if (!syncChangeDelta || !needsTombstone(item)) {
     return Promise.resolve();
   }
   return db.executeCached(`
-    INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
-    VALUES (:guid, :dateRemoved)`,
+    INSERT INTO moz_bookmarks_deleted (guid, parentGuid, dateRemoved)
+    VALUES (:guid, :parentGuid, :dateRemoved)`,
     { guid: item.guid,
+      parentGuid: item.parentGuid,
       dateRemoved: PlacesUtils.toPRTime(Date.now()) });
 }
 
 // Inserts tombstones for removed synced items.
 function insertTombstones(db, itemsRemoved, syncChangeDelta) {
   if (!syncChangeDelta) {
     return Promise.resolve();
   }
   let syncedItems = itemsRemoved.filter(needsTombstone);
   if (!syncedItems.length) {
     return Promise.resolve();
   }
   let dateRemoved = PlacesUtils.toPRTime(Date.now());
   let valuesTable = syncedItems.map(item => `(
     ${JSON.stringify(item.guid)},
+    ${JSON.stringify(item.parentGuid)},
     ${dateRemoved}
   )`).join(",");
   return db.execute(`
-    INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
+    INSERT INTO moz_bookmarks_deleted (guid, parentGuid, dateRemoved)
     VALUES ${valuesTable}`
   );
 }
 
 // Bumps the change counter for all bookmarks with URLs referenced in removed
 // tag folders.
 var addSyncChangesForRemovedTagFolders = async function(db, itemsRemoved, syncChangeDelta) {
   if (!syncChangeDelta) {

--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -1106,18 +1106,26 @@ Database::InitSchema(bool* aDatabaseMigr
       }
 
       // Firefox 55 uses schema version 37.
 
       if (currentSchemaVersion < 38) {
         rv = MigrateV38Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
+
       // Firefox 56 uses schema version 38.
 
+      if (currentSchemaVersion < 39) {
+        rv = MigrateV39Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+      // Firefox 56 uses schema version 39.
+
       // Schema Upgrades must add migration code here.
 
       rv = UpdateBookmarkRootTitles();
       // We don't want a broken localization to cause us to think
       // the database is corrupt and needs to be replaced.
       MOZ_ASSERT(NS_SUCCEEDED(rv));
     }
   }
@@ -2320,16 +2328,35 @@ Database::MigrateV38Up()
     ));
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   return NS_OK;
 }
 
 nsresult
+Database::MigrateV39Up()
+{
+  MOZ_ASSERT(NS_IsMainThread());
+
+  nsCOMPtr<mozIStorageStatement> stmt;
+  nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
+    "SELECT parentGuid FROM moz_bookmarks_deleted"
+  ), getter_AddRefs(stmt));
+  if (NS_FAILED(rv)) {
+    rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+      "ALTER TABLE moz_bookmarks_deleted ADD COLUMN parentGuid TEXT NOT NULL"
+    ));
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  return NS_OK;
+}
+
+nsresult
 Database::GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                            nsTArray<int64_t>& aItemIds)
 {
   nsCOMPtr<mozIStorageStatement> stmt;
   nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
     "SELECT b.id FROM moz_items_annos a "
     "JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id "
     "JOIN moz_bookmarks b ON b.id = a.item_id "

--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -14,17 +14,17 @@
 #include "mozilla/storage/StatementCache.h"
 #include "mozilla/Attributes.h"
 #include "nsIEventTarget.h"
 #include "Shutdown.h"
 #include "nsCategoryCache.h"
 
 // This is the schema version. Update it at any schema change and add a
 // corresponding migrateVxx method below.
-#define DATABASE_SCHEMA_VERSION 38
+#define DATABASE_SCHEMA_VERSION 39
 
 // Fired after Places inited.
 #define TOPIC_PLACES_INIT_COMPLETE "places-init-complete"
 // This topic is received when the profile is about to be lost.  Places does
 // initial shutdown work and notifies TOPIC_PLACES_SHUTDOWN to all listeners.
 // Any shutdown work that requires the Places APIs should happen here.
 #define TOPIC_PROFILE_CHANGE_TEARDOWN "profile-change-teardown"
 // Fired when Places is shutting down.  Any code should stop accessing Places
@@ -298,16 +298,17 @@ protected:
   nsresult MigrateV31Up();
   nsresult MigrateV32Up();
   nsresult MigrateV33Up();
   nsresult MigrateV34Up();
   nsresult MigrateV35Up();
   nsresult MigrateV36Up();
   nsresult MigrateV37Up();
   nsresult MigrateV38Up();
+  nsresult MigrateV39Up();
 
   nsresult UpdateBookmarkRootTitles();
 
   friend class ConnectionShutdownBlocker;
 
   int64_t CreateMobileRoot();
   nsresult GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                             nsTArray<int64_t>& aItemIds);

--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -118,16 +118,17 @@
 // This table stores tombstones for bookmarks with SYNC_STATUS_NORMAL. We
 // upload tombstones during a sync, and delete them from this table on success.
 // If Sync is disconnected, we'll delete all stored tombstones. If Sync is
 // never set up, we'll never write new tombstones, since all bookmarks will stay
 // in SYNC_STATUS_NEW.
 #define CREATE_MOZ_BOOKMARKS_DELETED NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_bookmarks_deleted (" \
     "  guid TEXT PRIMARY KEY" \
+    ", parentGuid TEXT NOT NULL" \
     ", dateRemoved INTEGER NOT NULL DEFAULT 0" \
   ")" \
 )
 
 #define CREATE_MOZ_KEYWORDS NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_keywords (" \
     "  id INTEGER PRIMARY KEY AUTOINCREMENT" \
     ", keyword TEXT UNIQUE" \