Magento – Magento 2: How to delete all categories at once

If you got orphan attribute values it means that there is something wrong with your database.
For example the table catalog_category_int has a constraint on the attribute_id column.

CONSTRAINT `FK_CAT_CTGR_ENTT_INT_ATTR_ID_EAV_ATTR_ATTR_ID` FOREIGN KEY (`attribute_id`) REFERENCES `eav_attribute` (`attribute_id`) ON DELETE CASCADE ON UPDATE CASCADE,

This means that if the attribute is deleted, all the values for the attribute from the table catalog_category_int will be deleted.
It's the same for the rest of the tables (catalog_category_*).

From experience I saw that usually constraints are lost during a migration process. You export the database but without the constraints. If this is the case then remember in the future to use System->Tools->Backupto create database dumps for migration.

[EDIT]
Here is the code I've used. I've created a simple extension that adds an attribute to the category entity, I edited a category and filled in a value for that attribute, then deleted the attribute through an upgrade script.
Here are the extension files:

app/etc/module/Easylife_Attr.xml - declaration file

<?xml version="1.0"?>
<config>
    <modules>
        <Easylife_Attr>
            <codePool>local</codePool>
            <active>true</active>
            <depends>
                <Mage_Catalog />
            </depends>
        </Easylife_Attr>
    </modules>
</config>

app/code/local/Easylife/Attr/etc/config.xml - the configuration file

<?xml version="1.0"?>
<config>
    <modules>
        <Easylife_Attr>
            <version>0.0.1</version>
        </Easylife_Attr>
    </modules>
    <global>
        <resources>
            <easylife_attr_setup>
                <setup>
                    <module>Easylife_Attr</module>
                    <class>Mage_Catalog_Model_Resource_Setup</class>
                </setup>
            </easylife_attr_setup>
        </resources>
    </global>
</config>

app/code/local/Easylife/Attr/sql/easylife_attr_setup/install-0.0.1.php - the install script

<?php

$this->addAttribute('catalog_category', 'dummy', array(
    'group'         => 'General',
    'input'         => 'textarea',
    'type'          => 'text', //can be any type
    'label'         => 'Custom attribute',
    'backend'       => '',
    'visible'       => true,
    'required'      => false,
    'visible_on_front' => true,
    'global'        => Mage_Catalog_Model_Resource_Eav_Attribute::SCOPE_GLOBAL
));

Now add a value for this dummy attribute for a category.
You should see it in the table catalog_category_entity_text.

After that create an upgrade script to remove the attribute. app/code/local/Easylife/Attr/sql/easylife_attr_setup/upgrade-0.0.1-0.0.2.php

<?php
$this->removeAttribute('catalog_category', 'dummy');

and change in config.xml the version from 0.0.1 to 0.0.2.

Refresh any page and look in the same table catalog_category_entity_text. The value that was added for the dummy attribute is gone. (at least for me).

The error is because the transaction is reaching its timeout period. If you did not set this in your my.cnf the default is 50 seconds I would highly recommend you look at your sever settings to ensure that they are optimized for your database using tools such as MySQLTuner

I have the innodb_lock_wait_timeout set to 7200 (2 hours) in a store with 500k products with 2 store views.

Example to add or change in my.cnf

innodb_lock_wait_timeout = 7200

DO NOT TRUNCATE.... yet

When you "moved around or reorganised a category" Magento will keep the references to these original links (hence the massive amount of links and 4 store views as well) and redirect them for visitors / bots / search engines that have book marked or indexed these pages.This can negatively affect your SEO, when you truncate they will receive a error 404 message. My personal recommendation is BEFORE doing major changes to the structure, ensure that nothing of the sort has been done for at least a month, then truncate then do your restructuring. This will cut down enormously on the size of your URL Rewrites

Since you've already re-arranged your categories, the best thing to do now is wait for a month to give visitors / bots / search engines the time to update the links --- then purge.

Also checkout:Magento core_url_rewrite table excessively large