Rick James's answer is the more general answer that other users should refer to for the problem referenced in the heading.
Though for the specifics of my problem, this is how I ultimately went about doing it.
The locations I store aren't just strings containing addresses, but are rather objects with multiple properties. For now, I store a main_text (a short address as a quick reference) and address (complete address to be used to identify the specific location) value. So I created a location table with a place id, booking id as the foreign key, main_text, and address. The origin and destination in the booking table then reference places in this this table.
The waypoints are stored in a separate table. They too are places, and so need to reference a place in the place table. So it's composed of a place id as the primary key and foreign key, booking id, and relative position in the ordering of waypoints.
What was slightly tricky when dealing with these cross-dependencies was figuring out how to cascade deletes. I initially set it up such that the booking id on both the waypoint and place table was used to cascade deletions for both tables, but I found that this didn't work. Instead, I ended up setting this cascade deletion constraint on the booking id of the place table, and then used the same constraint on the waypoint table, but instead on the place id. So when deleting a booking, it deletes all its places and waypoints.
The final schema looks like this:
| booking | CREATE TABLE `booking` (
`id` varchar(255) NOT NULL,
`user_id` varchar(255) DEFAULT NULL,
`created_at` int DEFAULT NULL,
`updated_at` int DEFAULT NULL,
`origin_id` varchar(255) DEFAULT NULL,
`destination_id` varchar(255) DEFAULT NULL,
`num_passengers` int DEFAULT NULL,
`arrival_datetime` datetime DEFAULT NULL,
`return_datetime` datetime DEFAULT NULL,
`num_vehicles` int DEFAULT NULL,
`return_trip` tinyint(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `user_ind` (`user_id`),
CONSTRAINT `fk_user_id` FOREIGN KEY (`user_id`) REFERENCES `user` (`id`) ON DELETE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
| place | CREATE TABLE `place` (
`main_text` varchar(255) DEFAULT NULL,
`address` varchar(1000) DEFAULT NULL,
`id` varchar(255) NOT NULL,
`booking_id` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `booking_ind` (`booking_id`),
CONSTRAINT `place_ibfk_1` FOREIGN KEY (`booking_id`) REFERENCES `booking` (`id`) ON DELETE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci |
| waypoint | CREATE TABLE `waypoint` (
`place_id` varchar(255) NOT NULL,
`booking_id` varchar(255) NOT NULL,
`position` int NOT NULL,
PRIMARY KEY (`place_id`),
UNIQUE KEY `place_id` (`place_id`),
KEY `place_ind` (`place_id`),
KEY `booking_ind` (`booking_id`),
CONSTRAINT `waypoint_ibfk_1` FOREIGN KEY (`place_id`) REFERENCES `place` (`id`) ON DELETE CASCADE,
CONSTRAINT `waypoint_ibfk_2` FOREIGN KEY (`booking_id`) REFERENCES `booking` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
--- UPDATE --- I removed the booking_id from the waypoint, and instead made it such that it's exclusively a child of a place. I actually was forced to do this because the ORM I'm using enforced it, but in retrospect, it makes sense to not store the booking id in the waypoint when the place already stores that information.
waypoint
table with the correct foreign key. What is your hesitation in normalizing this properly?