Insert New Foreign Key Row for new Strings
Assuming someval is actually an auto-generated column like a serial.

In Postgres this data-modifying CTE (writeable CTE) would do the job:

WITH sel AS (
   SELECT r.someval, i.someval_str, i.machine
   FROM  (SELECT ?, ?) AS i(someval_str, machine)
   LEFT   JOIN new_data_someval_ref r USING (someval_str)
   )
, ins AS ( 
   INSERT INTO new_data_someval_ref (someval_str)
   SELECT DISTINCT someval_str FROM sel WHERE someval IS NULL
   RETURNING someval, someval_str
   )
INSERT INTO new_data (someval, machine)
SELECT COALESCE(sel.someval, ins.someval), sel.machine
FROM   sel
LEFT   JOIN ins USING (someval_str);


Everything standard SQL, not sure whether it's all implemented in SQL Server identically.

For a query with multiple input rows and ample explanation:


How do I insert a row which contains a foreign key?


There is a tiny chance for a race condition under heavy concurrent load. (Doing everything in a single statement minimizes the time window.) If that's the case:


Is SELECT or INSERT in a function prone to race conditions?