Как записать полученный массив в базу данных PHP MySQL?

Что вы используете в качестве ORM?
Для начала можете почитать php.net/manual/ru/book.pdo.php

Как правильно объявить массив php?

Добрый день.
Дело в том, что, судя по всему, в массиве $cat нет индекса category_parent_id.
Массив $newArr у вас объявлен правильно, что бы избежать этих нотисов Вам стоит сделать следующее:

$newArr = array();
foreach ($cName as $cat) {
if (key_exist('category_parent_id', $cat) {
$newArr[$cat['category_parent_id']][] = $cat;
}
}