Sachverhalt: A. Am 9. Januar 2014 ging A._ nach malischem Recht die polygame Ehe mit dem malischen Staatsangehörigen C._ ein, welcher bereits mit zwei Frauen verheiratet war. Dadurch hat sie die malische Staatsangehörigkeit erworben. Mit Entscheid vom 10. April 2014 hat die Cour d'appel de Bamako, Tribunal de Première Instance de la Commune V du District de Bamako (Mali) die gemeinschaftliche Adoption des am 1. Juli 2012 in Bamako geborenen B._ durch die vorgenannten Ehegatten ausgesprochen. B. In der Folge beantragte A._ die Anerkennung und Eintragung dieser Adoption im Schweizerischen Zivilstandsregister. Mit Verfügung vom 18. November 2014 wies das Zivilstandsamt Basel-Stadt das Begehren mit Hinweis auf den Ordre public ab. Den hiergegen erhobenen Rekurs wies das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt ab. In teilweiser Gutheissung des hiergegen erhobenen Rekurses anerkannte das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht mit Urteil vom 12. Januar 2016 das malische Adoptionsurteil vom 10. April 2014 für das Mutter-Kind-Verhältnis und wies das Zivilstandsamt an, die betreffende Adoption im Zivilstandsregister einzutragen; es erhob keine Verfahrenskosten, sprach aber auch keine Parteientschädigung zu (Urteil VD.2015.116). C. Mit Beschwerde vom 25. Februar 2016 verlangen A._ und B._, in entsprechender Aufhebung des diesbezüglich abweisenden appellationsgerichtlichen Urteils sei ihnen für die kantonalen Rechtsmittelinstanzen eine Parteientschädigung von Fr. 30'065.20 (Fr. 14'390.90 und Fr. 15'674.30) zuzusprechen und im departementalen Verfahren sei überdies die Verfahrensgebühr zu erlassen. Es wurden keine Vernehmlassungen, aber die Akten eingeholt.