Puoi salvare l'entità genitore in una relazione uno-a-molti nel framework di entità?

Ho una relazione semplice, uno-a-molti, tra due entità.

public class Contact
{
    public string Id { get; set; }
    public string FirstName { get; set; }
    // the children
    public List<Message> Messages { get; set; }
}

public class Message
{
    public string Id { get; set; }
    public string ContactId { get; set; }
    public string Source { get; set; }
    // the parent
    public Contact Contact { get; set; }
}

Ecco come si presenta la migrazione

migrationBuilder.CreateTable(
                name: "Contact",
                columns: table => new
                {
                    Id = table.Column<string>(nullable: false),
                    FirstName = table.Column<string>(nullable: true)
                },
                constraints: table =>
                {
                    table.PrimaryKey("PK_Contact", x => x.Id);
                    table.UniqueConstraint("UK_Id", x => x.Id);
                });

            migrationBuilder.CreateTable(
                name: "Message",
                columns: table => new
                {
                    Id = table.Column<string>(nullable: false),
                    ContactId = table.Column<string>(nullable: true),                        
                    Source = table.Column<string>(nullable: true)
                },
                constraints: table =>
                {
                    table.PrimaryKey("PK_Message", x => x.Id);
                    table.UniqueConstraint("UK_Id", x => x.Id);
                    table.ForeignKey(
                        name: "FK_Message_Contact_ContactId",
                        column: x => x.ContactId,
                        principalTable: "Contact",
                        principalColumn: "Id");
                });

Ora, posso creare un nuovo Contact , aggiungere un nuovo Message alla proprietà Messages e salvare senza problemi. Se carico quel contatto, ottengo tutti i messaggi ad esso associati, nessun problema.

Quello che mi chiedo è come farlo al contrario. Voglio creare un nuovo messaggio (che non esiste ancora nel database), impostare la proprietà Contact su un nuovo oggetto contatto e salvare. Finisco con un vincolo di chiave esterna (che ha senso. Impossibile salvare il messaggio fino a quando il contatto non è stato salvato). Ma pensavo che il framework delle entità fosse abbastanza intelligente da capire le relazioni e sapere di inserire il contatto prima del messaggio. Sto configurando qualcosa di sbagliato?

Aggiornare

Ecco il test unitario che sto cercando di passare

    [TestMethod]
    public void ShouldSaveEntityParentRelationshipsCorrectly()
    {
        var message = new Message
        {
            Id = "2848"
            , IsUrgent = true
            , MessageType = MessageType.Inbox
            , Note = "One ring to rule them all"
            , Contact = new Contact
            {
                Id = "454545"
                , FirstName = "Frodo"
                , LastName = "Baggins"
            }
        };

        service.Save(message); //Foreign key constraint error

        var entity = service.Find<Message>()
            .Include(c => c.Contact)
            .First(p => p.Id == "2848");

        Assert.AreEqual("Frodo", entity.Contact.FirstName);
        Assert.AreSame(entity, message, "Messages are not the same");

        Assert.IsNotNull(entity.Contact);

        Assert.AreSame(message.Contact, entity.Contact, "Contacts are not the same");
    }

Ecco cosa service.Save fa sotto il cofano

public virtual void Save<T>(T entity) where T : class, IEntity
    {
        var context = Context();
        var entry = context.Entry(entity);
        var state = entry.State;

        if (state == EntityState.Detached)
            Add(entity);
        else if (state == EntityState.Deleted)
            Remove(entity);
        else
            Update(entity);

        SaveChanges();
    }

    public virtual void SaveChanges()
    {
        try
        {
            Context().SaveChanges();
        }
        catch (DbUpdateConcurrencyException ex)
        {
            Logger.Current.Log(ex);
            throw ex;
        }
    }

    public T Add<T>(T entity) where T : class, IEntity
    {
        return Context().Set<T>().Add(entity).Entity;
    }