Can EF automatically delete data that is orphaned, where the parent is not deleted?

It is actually supported but only when you use Identifying relation. It works with code first as well. You just need to define complex key for your ChildObject containing both Id and ParentObjectId:

modelBuilder.Entity<ChildObject>()
            .HasKey(c => new {c.Id, c.ParentObjectId});

Because defining such key will remove default convention for auto incremented Id you must redefine it manually:

modelBuilder.Entity<ChildObject>()
            .Property(c => c.Id)
            .HasDatabaseGeneratedOption(DatabaseGeneratedOption.Identity);

Now calling to parentObject.ChildObjects.Clear() deletes dependent objects.

Btw. your relation mapping should use WithRequired to follow your real classes because if FK is not nullable, it is not optional:

modelBuilder.Entity<ParentObject>().HasMany(p => p.ChildObjects)
            .WithRequired()
            .HasForeignKey(c => c.ParentObjectId)
            .WillCascadeOnDelete();

Update:

I found a way that doesn't need to add navigational properties from the child to the parent entity or to set up a complex key.

It's based on this article which uses the ObjectStateManager to find the deleted entities.

With a list ObjectStateEntry in hand, we can find a pair of EntityKey from each, which represents the relationship that was deleted.

At this point, I couldn't find any indication of which one had to be deleted. And contrary to the article's example, simply picking the second one would get the parent deleted in cases where the child had a navigation property back to the parent. So, in order to fix that, I track which types should be handled with the class OrphansToHandle.

The Model:

public class ParentObject
{
    public int Id { get; set; }
    public virtual ICollection<ChildObject> ChildObjects { get; set; }

    public ParentObject()
    {
        ChildObjects = new List<ChildObject>();
    }
}

public class ChildObject
{
    public int Id { get; set; }
}

The other classes:

public class MyContext : DbContext
{
    private readonly OrphansToHandle OrphansToHandle;

    public DbSet<ParentObject> ParentObject { get; set; }

    public MyContext()
    {
        OrphansToHandle = new OrphansToHandle();
        OrphansToHandle.Add<ChildObject, ParentObject>();
    }

    public override int SaveChanges()
    {
        HandleOrphans();
        return base.SaveChanges();
    }

    private void HandleOrphans()
    {
        var objectContext = ((IObjectContextAdapter)this).ObjectContext;

        objectContext.DetectChanges();

        var deletedThings = objectContext.ObjectStateManager.GetObjectStateEntries(EntityState.Deleted).ToList();

        foreach (var deletedThing in deletedThings)
        {
            if (deletedThing.IsRelationship)
            {
                var entityToDelete = IdentifyEntityToDelete(objectContext, deletedThing);

                if (entityToDelete != null)
                {
                    objectContext.DeleteObject(entityToDelete);
                }
            }
        }
    }

    private object IdentifyEntityToDelete(ObjectContext objectContext, ObjectStateEntry deletedThing)
    {
        // The order is not guaranteed, we have to find which one has to be deleted
        var entityKeyOne = objectContext.GetObjectByKey((EntityKey)deletedThing.OriginalValues[0]);
        var entityKeyTwo = objectContext.GetObjectByKey((EntityKey)deletedThing.OriginalValues[1]);

        foreach (var item in OrphansToHandle.List)
        {
            if (IsInstanceOf(entityKeyOne, item.ChildToDelete) && IsInstanceOf(entityKeyTwo, item.Parent))
            {
                return entityKeyOne;
            }
            if (IsInstanceOf(entityKeyOne, item.Parent) && IsInstanceOf(entityKeyTwo, item.ChildToDelete))
            {
                return entityKeyTwo;
            }
        }

        return null;
    }

    private bool IsInstanceOf(object obj, Type type)
    {
        // Sometimes it's a plain class, sometimes it's a DynamicProxy, we check for both.
        return
            type == obj.GetType() ||
            (
                obj.GetType().Namespace == "System.Data.Entity.DynamicProxies" &&
                type == obj.GetType().BaseType
            );
    }
}

public class OrphansToHandle
{
    public IList<EntityPairDto> List { get; private set; }

    public OrphansToHandle()
    {
        List = new List<EntityPairDto>();
    }

    public void Add<TChildObjectToDelete, TParentObject>()
    {
        List.Add(new EntityPairDto() { ChildToDelete = typeof(TChildObjectToDelete), Parent = typeof(TParentObject) });
    }
}

public class EntityPairDto
{
    public Type ChildToDelete { get; set; }
    public Type Parent { get; set; }
}

---

Original Answer

To solve this problem without setting up a complex key, you can override the SaveChanges of your DbContext, but then use ChangeTracker to avoid accessing the database in order to find orphan objects.

First add a navigation property to the ChildObject (you can keep int ParentObjectId property if you want, it works either way):

public class ParentObject
{
    public int Id { get; set; }
    public virtual List<ChildObject> ChildObjects { get; set; }
}

public class ChildObject
{
    public int Id { get; set; }
    public virtual ParentObject ParentObject { get; set; }
}

Then look for orphan objects using ChangeTracker:

public class MyContext : DbContext
{
    //...
    public override int SaveChanges()
    {
        HandleOrphans();
        return base.SaveChanges();
    }

    private void HandleOrphans()
    {
        var orphanedEntities =
            ChangeTracker.Entries()
            .Where(x => x.Entity.GetType().BaseType == typeof(ChildObject))
            .Select(x => ((ChildObject)x.Entity))
            .Where(x => x.ParentObject == null)
            .ToList();

        Set<ChildObject>().RemoveRange(orphanedEntities);
    }
}

Your configuration becomes:

modelBuilder.Entity<ParentObject>().HasMany(p => p.ChildObjects)
            .WithRequired(c => c.ParentObject)
            .WillCascadeOnDelete();

I did a simple speed test iterating 10.000 times. With HandleOrphans() enabled it took 1:01.443 min to complete, with it disabled it was 0:59.326 min (both are an average of three runs). Test code below.

using (var context = new MyContext())
{
    var parentObject = context.ParentObject.Find(1);
    parentObject.ChildObjects.Add(new ChildObject());
    context.SaveChanges();
}

using (var context = new MyContext())
{
    var parentObject = context.ParentObject.Find(1);
    parentObject.ChildObjects.Clear();
    context.SaveChanges();
}