Sachverhalt:
A. A.a Mit Bundesgesetz vom 13. Juni 2008 über die Neuordnung der Pflegefinanzierung wurde u.a. ein neuer <ref-law> eingeführt, welcher die Pflegeleistungen bei Krankheit regelt. Danach leistet die obligatorische Krankenpflegeversicherung einen vom Bundesrat festzulegenden Beitrag an die Pflegeleistungen (Abs. 1, 3 und 4). Von den nicht von Sozialversicherungen gedeckten Pflegekosten dürfen der versicherten Person höchstens 20 Prozent des höchsten vom Bundesrat festgesetzten Pflegebeitrags überwälzt werden (Abs. 5 Satz 1). Die Kantone regeln die Restfinanzierung (Abs. 5 Satz 2). Die Gesetzesänderung trat am 1. Januar 2011 in Kraft.
A.b Zur Umsetzung der neuen Pflegefinanzierung erliess der Regierungsrat des Kantons Basel-Stadt am 23. November 2010 eine Änderung der Verordnung über die Krankenversicherung im Kanton Basel-Stadt vom 25. November 2008 (KVO/BS; Syst. Nr. 834.410). Diese Änderung wurde am 27. November 2010 im Kantonsblatt publiziert und auf den 1. Januar 2011 in Kraft gesetzt. Sie enthält u.a. einen neuen § 8d mit dem Titel "Restfinanzierung durch den Kanton in Anwendung von <ref-law>". Abs. 1 enthält für jede der zwölf Pflegestufen (vgl. Art. 7a Abs. 3 der Krankenpflege-Leistungsverordnung vom 29. September 1995 [KLV; SR 832.112.31]) die Pflegekosten pro Tag. Gemäss Abs. 2 entspricht die Höhe der Restfinanzierung der Differenz zwischen den anerkannten Pflegekosten und den Leistungen der Krankenversicherer gemäss <ref-law> sowie dem maximalen Eigenbeitrag der versicherten Person gemäss § 8. In der Folge lautet § 8d Abs. 4 KVO/BS sodann:
"Für die Erfassung des Pflegebedarfs der Bewohnerinnen und Bewohner gilt für die Pflegeheime, welche auf der kantonalen Pflegeheimliste aufgeführt sind, das Bedarfserfassungssystem RAI/RUG in der Version CH-Index 2011 (Anhang)."
Anhang 1 führt Folgendes aus:
Pflegestufe
Pflegeaufwand in Minuten pro Tag
CH-Index 2011
Original-RUG's
1
bis 20
0.095
PA0
2
21-40
0.285
PA1
3
41-60
0.476
BA1, PA2
4
61-80
0.666
IA1, BA2
5
81-100
0.856
PB1, PB2, BB1
6
101-120
1.046
CA1, IB1, PC1, BB2, PC2
7
121-140
1.237
IA2, IB2, CA2
8
141-160
1.427
PD1, PD2, CB1, RMA, RLA
9
161-180
1.617
CB2, SSA, RMB, CC1
10
181-200
1.807
SSB, PE1, RLB, CC2, PE2
11
201-220
1.998
SSC, SE1
12
ab 221
2.188
RMC, SE2, SE3
B. Am 6. Dezember 2010 erhoben der Verein santésuisse sowie 81 Krankenversicherer gemeinsam Beschwerde beim Appellationsgericht des Kantons Basel-Stadt (als Verfassungsgericht) mit dem Antrag, § 8d Abs. 4 sowie der entsprechende Anhang KVO/BS gemäss Teilrevision vom 23./27. November 2010 seien aufzuheben.
Mit Urteil vom 17. Februar 2012 wies das Appellationsgericht die Beschwerde ab.
C. Der Verein santésuisse sowie 79 der vorinstanzlich beteiligten Krankenversicherer erheben Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das angefochtene Urteil sei aufzuheben und § 8d Abs. 4 KVO/BS samt Anhang sei als bundesrechtswidrig und ungültig zu erklären. Eventuell sei die Sache an die Vorinstanz zurückzuweisen.
Das Appellationsgericht und das Gesundheitsdepartement des Kantons Basel-Stadt (in Vertretung des Regierungsrates) beantragen Abweisung der Beschwerde. Das Bundesamt für Gesundheit beantragt Gutheissung der Beschwerde und Zurückweisung an das Appellationsgericht.
Die Beschwerdeführer äussern sich mit Stellungnahme vom 8. Oktober 2012 zu den eingegangenen Vernehmlassungen.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den kantonal letztinstanzlichen Entscheid in einem Verfahren der abstrakten Normenkontrolle ist zulässig (Art. 82 lit. b, Art. 86 Abs. 1 lit. d i.V.m. <ref-law>). Die Krankenversicherer machen geltend, die angefochtene Regelung führe für sie zu einer Mehrbelastung, und sind daher zur Beschwerde legitimiert (<ref-law>; vgl. Urteil 2C_856/2011 vom 18. Januar 2012 E. 3.2 und 3.3), ebenso der Verein santésuisse, der als Verband die Interessen der Krankenversicherer vertritt (<ref-ruling> E. 1.1; zit. Urteil 2C_856/2011 E. 3.4).
2. Die angefochtene Verordnungsbestimmung steht systematisch in einem Paragrafen, welcher die Restfinanzierung durch den Kanton regelt. Dies könnte zur Annahme führen, dass § 8d Abs. 4 KVO/BS nur für die Bemessung der kantonalen Leistung (gemäss <ref-law>) massgebend ist, nicht für die Leistungspflicht der Krankenversicherer, welche sich nach Art. 25a Abs. 1, 3 und 4 KVG richtet. Die Verfahrensbeteiligten sind sich aber einig, dass entgegen dieser systematischen Stellung mit der angefochtenen Bestimmung auch die Ermittlung desjenigen Pflegebedarfs geregelt werden soll, der nach <ref-law> durch die Krankenversicherer zu übernehmen ist. Von dieser Auslegung ist auszugehen.
3. 3.1 Unter der bis Ende 2010 geltenden Regelung waren ärztlich angeordnete Pflegemassnahmen in Pflegeheimen grundsätzlich Pflichtleistungen der obligatorischen Krankenpflegeversicherung (<ref-law> in der bis 31. Dezember 2010 gültig gewesenen Fassung) und unterstanden an sich dem Tarifschutz gemäss <ref-law>. Die Tarife wurden in Tarifverträgen (<ref-law>) oder - beim Fehlen von solchen - in von den Kantonsregierungen festgelegten Tarifen (<ref-law>) festgelegt. Nach den verbindlichen Feststellungen der Vorinstanz wurde im Kanton Basel-Stadt für die Finanzierung von Pflegeleistungen der "Basler Index" angewendet, ein zwölfstufiges System, welches nicht auf die Anzahl Pflegeminuten, sondern auf das jeweilige Behandlungsbild und damit die Pflegediagnose der Heimbewohner abstellte.
3.2 Auf den 1. Januar 2011 trat das Bundesgesetz über die Neuordnung der Pflegefinanzierung in Kraft (AS 2009 3517, 6847), wodurch namentlich der neue <ref-law> aufgenommen wurde. Nach <ref-law> leistet die obligatorische Krankenpflegeversicherung (OKP) einen Beitrag an die Pflegeleistungen, welche aufgrund einer ärztlichen Anordnung und eines ausgewiesenen Pflegebedarfs u.a. in einem Pflegeheim (Art. 35 Abs. 2 lit. k und Art. 39 Abs. 3 KVG) erbracht werden (vgl. auch <ref-law>, in der neuen Fassung). Der Bundesrat bezeichnet die Pflegeleistungen und regelt das Verfahren der Bedarfsermittlung (<ref-law>). Der Bundesrat setzt die Beiträge differenziert nach dem Pflegebedarf in Franken fest. Massgebend ist der Aufwand nach Pflegebedarf für Pflegeleistungen, die in der notwendigen Qualität, effizient und kostengünstig erbracht werden. Die Pflegeleistungen werden einer Qualitätskontrolle unterzogen. Der Bundesrat legt die Modalitäten fest (<ref-law>). Gemäss Art. 33 lit. b, h und i der Verordnung vom 27. Juni 1995 über die Krankenversicherung (KVV; SR 832.102; in der Fassung vom 24. Juni 2009, in Kraft seit 1. Januar 2011) bezeichnet das Eidgenössische Departement des Innern die Leistungen (u.a.) nach <ref-law>, das Verfahren der Bedarfsermittlung sowie den in Art. 25a Abs. 1 und 4 des Gesetzes vorgesehenen und nach Pflegebedarf differenzierten Beitrag an die Pflegeleistungen. Das Departement hat die zu übernehmenden Leistungen in <ref-law> (SR 832.112.31) festgelegt. Sodann hat es in <ref-law> (in der Fassung vom 24. Juni 2009, in Kraft seit 1. Januar 2011) für die in Pflegeheimen erbrachten Pflegeleistungen die von der obligatorischen Krankenpflegeversicherung zu übernehmenden Kostenbeiträge in zwölf Stufen (von Fr. 9.- bis Fr. 108.- pro Tag) festgelegt, abhängig vom täglichen Pflegebedarf in Minuten. Gemäss <ref-law> (in der Fassung vom 24. Juni 2009, in Kraft seit 1. Januar 2011) erfolgt die Bedarfsabklärung in Pflegeheimen durch die Ermittlung des Pflegebedarfs gemäss Art. 9 Abs. 2; der vom Arzt oder von der Ärztin bestimmte Pflegebedarf gilt als ärztliche Anordnung oder als ärztlicher Auftrag. Nach <ref-law> (in der Fassung vom 24. Juni 2009, in Kraft seit 1. Januar 2011) müssen die Leistungen nach Art. 7 Abs. 2 der Pflegeheime nach dem Pflegebedarf in Rechnung gestellt werden.
Die Übergangsbestimmungen zur Gesetzesänderung vom 13. Juni 2008 lauten wie folgt (AS 2009 3520):
1 Die Beiträge an die Pflegeleistungen gemäss Artikel 25a Absatz 1 sind erstmals so festzulegen, dass sie der Summe der Vergütungen für die im dem Inkrafttreten vorangehenden Jahr ambulant und im Pflegeheim erbrachten Pflegeleistungen entsprechen. Kann diese Regelung im ersten Jahr nach Inkrafttreten dieser Gesetzesänderung nicht eingehalten werden, so nimmt der Bundesrat in den nachfolgenden Jahren die erforderlichen Anpassungen vor.
2 Die bei Inkrafttreten dieser Änderung geltenden Tarife und Tarifverträge sind innert drei Jahren an die vom Bundesrat festgesetzten Beiträge an die Pflegeleistungen anzugleichen. Die Kantonsregierungen regeln die Angleichung.
4. Umstritten ist, nach welcher Methode der Pflegebedarf zu ermitteln ist, der als Grundlage für die Einstufung in die zwölf Pflegestufen nach <ref-law> dient.
4.1 Die Vorinstanz hat erwogen, der Bund habe von seiner Kompetenz, das Verfahren der Bedarfsermittlung zu regeln (<ref-law>), bisher keinen Gebrauch gemacht, weshalb dafür weiterhin die Kantone zuständig seien, weil andernfalls eine entsprechende Regelung überhaupt fehlen würde. In der Schweiz bestünden verschiedene Einstufungssysteme, die zu unterschiedlichen Ergebnissen führten. Im bisher in Basel-Stadt verwendeten RAI-System ("Resident Assessment Instrument") hätten sich die tiefsten Werte ergeben. In der RAI/RUG ("Ressource Utilization Groups"), in der Version gemäss CH-Index 2011, seien diese Werte angepasst und den Werten der anderen Systeme angenähert worden. Ein gemeinsames Vorgehen der Tarifparteien sei bisher nicht möglich gewesen; es sei daher nicht zu beanstanden, dass die Kantonsregierung das anwendbare System festlege. Dieses sei auch methodisch und inhaltlich nicht zu beanstanden. Dass dadurch die Minutenwerte um rund 16 % erhöht würden, sei nicht bundesrechtswidrig, habe doch der Bundesgesetzgeber Preiserhöhungen in einzelnen Bereichen in Kauf genommen; zudem erfolge mit der angefochtenen Neuregelung sogar eine Entlastung der obligatorischen Krankenversicherung, wenn auch nicht in dem Ausmass, wie von den Versicherern gewünscht.
4.2 Die Beschwerdeführer bringen vor, der Bund habe mit <ref-law>, <ref-law> und <ref-law> das Verfahren der Bedarfsermittlung abschliessend festgelegt, so dass kein Raum für eine kantonale Regelung verbleibe. Eine kantonal unterschiedliche Festlegung des Pflegebedarfs hätte zur Folge, dass für den gleichen Pflegeaufwand sowohl die Leistungen der obligatorischen Krankenpflegeversicherung als auch die Beiträge der Versicherten (<ref-law>) je nach Kanton unterschiedlich ausfallen, was bundesrechtswidrig sei. Die einseitige Festlegung des Verfahrens durch die Kantonsregierung verletze zudem das im KVG festgelegte Tarifvertragsprinzip. Das Instrument RAI/RUG sei sodann auch inhaltlich nicht gesetzmässig, weil es auf hinterlegten Normzeiten anstatt auf effektiv geleisteten Zeiten beruhe. Die Version 2011 des CH-Index erfülle auch die Vorgaben bezüglich Effizienz und Kostengünstigkeit nicht und verstosse damit gegen <ref-law> und <ref-law>. Die Vorinstanz habe weder das Effizienz- noch das Kostengünstigkeitskriterium geprüft. Ohne schweizweit einheitliche Erfassung des Pflegebedarfs sei auch <ref-law> nicht umsetzbar. Schliesslich sei die rechtssatzmässige Vergabe eines Pflegebedarfssystems eine öffentliche Beschaffung i.S.v. Art. 5 des Bundesgesetzes vom 6. Oktober 1995 über den Binnenmarkt (BGBM; SR 943.02); die dort enthaltenen Vorgaben seien nicht eingehalten worden.
4.3 Das Gesundheitsdepartement des Kantons Basel-Stadt bringt vor, <ref-law> lasse sich nicht entnehmen, nach welchem System der Pflegebedarf zu ermitteln sei. Der Bundesrat und das Eidgenössische Departement des Innern hätten bisher bewusst darauf verzichtet, ein schweizweit einheitliches System zu etablieren, so dass dies nach wie vor kantonale Zuständigkeit sei. Die Bemessung der Beiträge der obligatorischen Krankenpflegeversicherung an die Leistungen der Pflegeheime sei der Tarifautonomie entzogen; zudem wäre gemäss <ref-law> subsidiär die Kantonsregierung zuständig zur Festlegung des Tarifs. Da das bisher im Kanton Basel-Stadt verwendete System nicht mehr bundesrechtskonform sei und eine schweizweite Regelung nicht bestehe, sei der Regierungsrat verpflichtet gewesen, ein anderes System festzulegen. <ref-law> sei auf die Neuordnung der Pflegefinanzierung nicht unbesehen anwendbar.
4.4 Das Bundesamt für Gesundheit ist der Auffassung, <ref-law> und <ref-law> seien nicht so zu verstehen, dass der Bundesrat bzw. das Eidgenössische Departement des Innern die Bedarfsermittlungssysteme festsetzen müsse. Auch die Verordnung vom 3. Juli 2002 über die Kostenermittlung und die Leistungserfassung durch Spitäler, Geburtshäuser und Pflegeheime in der Krankenversicherung (VKL; SR 832.104) sehe kein spezifisches Pflegeerfassungssystem vor. Eine durch Vertreter der Kantone, des Bundes, der Leistungserbringer und der Versicherer gebildete Projektgruppe habe im Sinne einer Kalibrierung der Systeme BESA (nach der Rechtschreibung der Herausgeberschaft "BewohnerInnen EinStufungs- und Abrechnungssystem") und RAI/RUG Lösungen erarbeitet und eine Empfehlung erlassen. Grundsätzlich dürften die Kantone die Bedarfsermittlungssysteme regeln; sie müssten sich dabei jedoch an die Vorgaben des KVG halten. Dieses sehe vor, dass die Neuregelung für den Pflegeheimbereich gesamtschweizerisch kostenneutral erfolgen müsse. Würden in einzelnen Kantonen einseitig die Minutenwerte und damit die zu leistenden Vergütungen erhöht, müssten gesamtschweizerisch die vom Bundesrat festgesetzten Beiträge nach unten korrigiert werden. Anpassungen in der Anwendung der Bedarfsermittlungssysteme müssten daher koordiniert erfolgen; die vom Kanton Basel-Stadt einseitig vorgenommene Änderung der Parameter sei mit den Grundsätzen der Pflegefinanzierung nicht vereinbar. BAG, Curaviva und santésuisse würden der Erhöhung der Minutenwerte im System RAI/RUG um 16,2 % nicht ohne weiteres zustimmen, zumal nicht belegt sei, dass BESA in diesem Umfang höhere Werte ausweise. Es könne nicht davon ausgegangen werden, dass nur die Werte gemäss BESA korrekt seien und diejenigen gemäss RAI/RUG daher dem BESA-System anzupassen seien. Dadurch würde der Grundsatz der Kostenneutralität rechnerisch verletzt. Die Nationale Steuerungsgruppe Tarifstrukturen sehe daher vor, dass die Minutenwerte der BESA-Instrumente um 8,45 % reduziert und diejenigen der RAI/RUG um 9 % erhöht werden. Die vom Regierungsrat festgelegte Erhöhung der Minutenwerte führe dazu, dass die obligatorische Krankenpflegeversicherung nicht um rund 7,8 Mio. Franken, sondern nur um ca. 1,7 Mio. Franken entlastet werde.
5. 5.1 Gemäss <ref-law> geht Bundesrecht entgegenstehendem kantonalem Recht vor. Der Grundsatz der derogatorischen Kraft des Bundesrechts schliesst in Sachgebieten, welche die Bundesgesetzgebung abschliessend regelt, eine Rechtsetzung durch die Kantone aus. In Sachbereichen, die von Bundesrechts wegen in nicht abschliessender Weise geordnet sind, dürfen die Kantone Normen erlassen, soweit sie nicht gegen Sinn und Geist des Bundesrechts verstossen und überdies dessen Zweck nicht beeinträchtigen (<ref-ruling> E. 3.4 S. 174 f., 31 E. 4.1 S. 41; <ref-ruling> E. 6.1 S. 224; <ref-ruling> E. 2.1 S. 108). Auch wenn sich eine Bundesregelung in einem bestimmten Sachbereich an sich als abschliessend darstellt, ist eine kantonale Lösung nicht ausgeschlossen, falls sie ein anderes Ziel verfolgt, als dies das Bundesrecht tut. Kantonales Recht ist überdies zulässig, wenn es im Bereich abschliessenden Bundesrechts dessen Sinn und Zweck unterstützt (<ref-ruling> E. 3.4 S. 174 f.; <ref-ruling> E. 4.1 S. 116). Schliesslich gilt, dass die Kantone ihrer Möglichkeit zur Gesetzgebung lediglich dann vollends benommen sind, soweit Bundesrecht in einem bestimmten Bereich kantonales Recht insgesamt untersagt. Dies schliesst sämtliches Recht der Kantone aus, selbst wenn es den Bestimmungen der bundesrechtlichen Lösung nicht widerspricht oder es mit ihr im Einklang steht (<ref-ruling> E. 3.4 S. 174 f.; <ref-ruling> E. 4.1 S. 116).
5.2 <ref-law> beauftragt den Bundesrat, das Verfahren der Bedarfsermittlung zu regeln. Der Bundesrat hat in <ref-law> diese Aufgabe an das Eidgenössische Departement des Innern delegiert. <ref-law>, der sich gemäss seinem Titel u.a. mit der Bedarfsabklärung befasst, regelt deren Verfahren für Pflegeheime indessen nicht: Die Abs. 2 und 3 befassen sich, wie sowohl aus der Systematik des Artikels als auch aus dem Inhalt dieser Absätze hervorgeht, nur mit der Bedarfsabklärung für Leistungen der Pflegefachfrauen und Pflegefachmänner sowie der Organisationen der Krankenpflege und Hilfe zu Hause (Art. 7 Abs. 1 lit. a und b KLV), nicht mit derjenigen in Pflegeheimen (<ref-law>). Abs. 3bis bezieht sich auf die Akut- und Übergangspflege gemäss <ref-law>. <ref-law> sodann wiederholt (wie auch <ref-law>) in seinem ersten Satz bloss die Aussage von <ref-law>; Satz 2 spricht vom ärztlich bestimmten Pflegebedarf, legt aber nicht fest, nach was für Verfahren dieser zu bestimmen ist. Das Verordnungsrecht des Bundes hat somit bisher kein Verfahren der Bedarfsermittlung festgelegt. Diese Frage ist daher nicht - jedenfalls nicht abschliessend - bundesrechtlich geregelt, sodass insoweit eine kantonale Zuständigkeit verbleibt.
5.3 Sodann sind sich die Verfahrensbeteiligten einig, dass die bis Ende 2010 im Kanton Basel-Stadt angewendete Methode nicht mehr bundesrechtskonform ist, weil sie nicht auf den Pflegebedarf in Minuten, sondern auf die Pflegediagnose abstellte.
5.4 Mangels einer bundesrechtskonformen bisherigen und einer bundesrechtlichen neuen Regelung hat daher der Regierungsrat mit Recht eine kantonale Regelung erlassen. Dass dies zur Folge haben kann, dass die basel-städtische Regelung anders ist als die in anderen Kantonen angewendete, ist die logische Folge des Föderalismus und der kantonalen Zuständigkeit (Urteil 8C_44/2012 vom 31. August 2012 E 5.1, zur Publ. bestimmt); dies verstösst grundsätzlich weder gegen die Rechtsgleichheit (<ref-law>) noch gegen die derogatorische Kraft des Bundesrechts (<ref-law>). Ein Kanton kann nicht eine für die ganze Schweiz geltende Regelung erlassen, auch wenn eine solche als wünschbar erscheinen mag. Umgekehrt kann dem Regierungsrat auch nicht vorgeworfen werden, die Entstehung einer gesamtschweizerischen Regelung nicht abgewartet zu haben, da irgendeine Lösung festgelegt werden muss. Die angefochtene Bestimmung präjudiziert auch nicht den Inhalt der angestrebten gesamtschweizerischen Regelung; wenn eine solche zustande kommt, kann sie die jetzt angefochtene kantonale ersetzen.
5.5 Die obligatorische Krankenpflegeversicherung vergütet die Leistungen nach KVG grundsätzlich nach Tarifen (<ref-law>), die primär tarifautonom durch die Tarifvertragspartner festgelegt werden (<ref-law>). Im Bereich der Pflegefinanzierung ist dieses System jedoch ersetzt worden durch bundesrechtlich festgelegte Frankenbeträge (Art. 25a Abs. 1 und 4 KVG; <ref-law>). Das sonst im Bereich des KVG geltende Tarifvertragssystem gilt für die Finanzierung dieser Pflegeleistungen somit nicht mehr. Zudem machen die Beschwerdeführer selber nicht geltend, eine vertragliche Regelung zwischen Leistungserbringern und Krankenversicherern sei in der hier zu beurteilenden Frage auf nationaler oder kantonaler Ebene erfolgt. Entsprechende Arbeiten auf schweizerischer Ebene sind im Gange, haben aber noch nicht zu einem Ergebnis geführt. Selbst soweit die Tarifbestimmungen des KVG anwendbar wären, wäre somit die Kantonsregierung zuständig, um eine Regelung zu erlassen (<ref-law>).
5.6 Als genereller Grundsatz gilt im ganzen Bereich der obligatorischen Krankenpflegeversicherung der Grundsatz der Wirtschaftlichkeit der Leistungen (Art. 32 Abs. 1 und Art. 56 Abs. 1 KVG). Es ist einzuräumen, dass die vom Regierungsrat offenbar befolgte Methode, die tiefsten Minutenwerte einfach an die höchsten anzugleichen, methodisch fragwürdig ist. Umgekehrt legen aber auch die Beschwerdeführer nicht hinreichend substantiiert dar, inwiefern das Wirtschaftlichkeitsprinzip verletzt sein soll. Insbesondere überzeugt ihre Kritik nicht, die Methode RAI/RUG basiere auf Normzeiten und nicht auf effektiv erbrachten Leistungen; denn indem das Gesetz den ausgewiesenen Bedarf als massgebend erklärt (<ref-law>), bezieht es sich gerade im Sinne des Wirtschaftlichkeitsprinzips nicht ohne weiteres auf das Mass der effektiv erbrachten Leistungen, sondern auf eine normative Bewertung dieses Ausmasses. Auch der blosse Umstand, dass eine für die Krankenversicherer günstigere Regelung denkbar wäre, lässt die angefochtene Bestimmung noch nicht als bundesrechtswidrig erscheinen; denn es ist nicht unbedingt immer diejenige Regelung massgebend, welche für die Versicherung die geringsten Kostenfolgen hat (vgl. z.B. <ref-ruling> E. 2).
5.7 Das BAG verweist mit Recht auf die Übergangsbestimmungen zur Gesetzesänderung vom 13. Juni 2008 (vorne E. 3.2), welche für die neue Pflegefinanzierung die Kostenneutralität der Gesetzesrevision für die obligatorische Krankenpflegeversicherung vorgeben. Diese Kostenneutralität bezieht sich auf die ganze Schweiz. Dem BAG ist aber zuzustimmen, dass darin implizit auch eine Vorgabe an die einzelnen Kantone enthalten ist: Wenn nämlich ein Kanton eigenmächtig die Kosten zulasten der obligatorischen Krankenpflegeversicherung erhöht und dies zur Folge hat, dass die Kostenneutralität gesamtschweizerisch nicht eingehalten wird, muss der Bundesrat die in <ref-law> festgelegten Beiträge reduzieren, was alle anderen Kantone tangieren würde. Vorliegend kann allerdings diese Überlegung nicht dazu führen, dass die angefochtene Regelung zu beanstanden wäre: Wie nämlich die Vorinstanz festgestellt hat und die Beschwerdeführer selber vorbringen, führt die neue Regelung im Kanton Basel-Stadt zu einer Entlastung der obligatorischen Krankenpflegeversicherung gegenüber dem vorherigen Zustand, nämlich um rund 1,7 Mio. Franken pro Jahr oder rund 3 %. Dem Kanton kann demnach nicht vorgeworfen werden, er habe in seinem Zuständigkeitsbereich den Grundsatz der Kostenneutralität verletzt. Daran ändert nichts, dass mit einer anderen Methode die Krankenversicherung noch mehr entlastet worden wäre. Unter diesen Umständen wäre auch <ref-law> nicht verletzt, soweit er überhaupt auf die hier zu beurteilende Regelung anwendbar wäre.
6. Die Beschwerdeführer rügen schliesslich, die angefochtene Verordnungsänderung verletze <ref-law>, weil ohne Berücksichtigung submissionsrechtlicher Vorgaben ein bestimmtes Pflegebedarfserfassungssystem vorgeschrieben werde.
6.1 Das Gesundheitsdepartement beantragt, auf diese Rüge nicht einzutreten, da sie vor der Vorinstanz nicht erhoben worden sei. Gemäss <ref-law> sind vor Bundesgericht neue Begehren nicht zulässig. Das neue Begehren bezieht sich auf den Streitgegenstand; dieser darf vor Bundesgericht nicht mehr ausgeweitet werden. Zulässig sind hingegen im Rahmen des Streitgegenstandes neue rechtliche Begründungen, soweit sie sich auf einen vorinstanzlich festgestellten oder aktenkundigen Sachverhalt stützen; unzulässig ist eine neue rechtliche Argumentation, soweit sie sich auf neue Tatsachen stützt, die aufgrund von <ref-law> nicht zulässig sind (<ref-ruling> E. 3.4 und 4.1; <ref-ruling> E. 4.5; vgl. auch <ref-ruling> E. 2.4).
6.2 Nach <ref-law> richten sich die öffentlichen Beschaffungen durch Kantone, Gemeinden und andere Träger kantonaler oder kommunaler Aufgaben nach kantonalem oder interkantonalem Recht. Diese Vorschriften und darauf gestützte Verfügungen dürfen Personen mit Niederlassung oder Sitz in der Schweiz nicht in einer Weise benachteiligen, welche <ref-law> widerspricht (Abs. 1). Kantone und Gemeinden sowie andere Träger kantonaler und kommunaler Aufgaben sorgen dafür, dass die Vorhaben für umfangreiche öffentliche Einkäufe, Dienstleistungen und Bauten sowie die Kriterien für Teilnahme und Zuschlag amtlich publiziert werden. Sie berücksichtigen dabei die vom Bund eingegangenen staatsvertraglichen Verpflichtungen (Abs. 2). Nach <ref-law> sind Beschränkungen des freien Zugangs zum Markt, insbesondere im Bereich des öffentlichen Beschaffungswesens, in einer anfechtbaren Verfügung zu erlassen.
Eine nähere Definition des Begriffs "Beschaffung" enthält das BGBM nicht. Nach Lehre und Rechtsprechung ist kennzeichnend für das Beschaffungsrecht, dass der Staat als Nachfrager Waren oder Dienstleistungen gegen eine Gegenleistung beschafft, um damit seine Aufgaben wahrzunehmen (<ref-ruling> E. 6b; <ref-ruling> E. 2d/bb, 128 I 136 E. 4.1; <ref-ruling> E. 4.3.2; MARTIN BEYELER, Der Geltungsanspruch des Vergaberechts, 2012, Rz. 604 und 620; GALLI/MOSER/LANG/CLERC, Praxis des öffentlichen Beschaffungsrechts, 2. Aufl. 2007, S. 45 Rz. 107; FRANÇOIS BELLANGER, La notion de "marché public", une définition sans concession? in: Les droits de l'homme et la constitution, 2007, S. 400 f., 407 f.; DANIEL KUNZ, Verfahren und Rechtsschutz bei der Vergabe von Konzessionen, 2004, S. 161, 166 f.; CASPAR ZELLWEGER/ANNATINA WIRZ, Das öffentliche Beschaffungsrecht des Kantons Basel-Stadt, in: Denise Buser [Hrsg.], Neues Handbuch des Staats- und Verwaltungsrechts des Kantons Basel-Stadt, 2008, S. 577; RHINOW/SCHMID/BIAGGINI/ UHLMANN, Öffentliches Wirtschaftsrecht, 2. Aufl., 2011, § 19 Rz. 5). Das Bundesgericht hat in <ref-ruling> E. 6b S. 214 sowie im Urteil 2P.19/2001 vom 16. Mai 2001 E. 1a/cc, in: RDAT 2001 II N. 96 S. 405, die Beschaffung der Ware oder Dienstleistung durch das Gemeinwesen mittels eines privatrechtlichen Vertrags als wesentliches Element der öffentlichen Beschaffung bezeichnet. Später hat es präzisiert, dass nicht bloss auf die Rechtsnatur des abgeschlossenen Vertrags, sondern auf eine funktionale Betrachtung abzustellen ist, damit die Anwendung des Vergaberechts nicht durch Wahl einer besonderen Rechtskonstruktion umgangen werden könne (BGE <ref-ruling> E. 4.4 S. 56; vgl. auch die oben zitierten Literaturhinweise).
6.3 Eine Beschaffung im Sinne von <ref-law> würde somit vorliegen, wenn der Kanton oder ein anderer Träger kantonaler oder kommunaler Aufgaben von einem bestimmten Anbieter eine bestimmte Ware oder Dienstleistung kauft, um damit den Pflegebedarf zu messen. In diesem Fall könnten die Anforderungen von Art. 5 und 9 BGBM nicht dadurch umgangen werden, dass die Beschaffung rechtssatzmässig, durch Verordnung, festgelegt wird. Werden jedoch durch Rechtssatz bloss Anforderungen an ein bestimmtes Produkt festgelegt, das prinzipiell von mehreren Anbietern angeboten werden kann, so liegt keine öffentliche Beschaffung vor (vgl. dazu auch <ref-ruling> E. 3.3.1 und 3.5).
6.4 Gerichtsnotorisch gibt es private Unternehmen, welche auf dem Markt Produkte anbieten, mit welchen der Pflegebedarf nach der Methode RAI/RUG ermittelt werden kann. Hingegen ist weder vorinstanzlich festgestellt noch aktenkundig, dass das in der angefochtenen Verordnungsbestimmung festgelegte Bedarfserfassungssystem RAI/RUG in der Version gemäss CH-Index 2011 nur von einer einzigen Unternehmung angeboten wird, sodass mit der Verordnung unzulässigerweise eine bestimmte Beschaffung vorgeschrieben würde. Dergleichen wird von den Beschwerdeführern auch nicht behauptet. Unter diesen Umständen fehlt eine sachverhaltliche Grundlage für die gerügte Rechtsverletzung (vgl. E. 6.1), sodass eine Verletzung des Submissionsrechts jedenfalls nicht rechtsgenüglich dargetan ist.
7. Die Beschwerde erweist sich damit als unbegründet. Bei diesem Ausgang tragen die Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens (<ref-law>), wobei sie solidarisch haften (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 5'000.- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3. Dieses Urteil wird den Parteien, dem Appellationsgericht des Kantons Basel-Stadt als Verfassungsgericht und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Lausanne, 5. November 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Kocher