It all starts with the constellation of Boötes. Known since antiquity, it was usually depicted as a mighty herdsman bearing a club or a crooked staff. One famous example is Germanicus‘s 1st century AD Latin translation of famously incoherent Phenomena, 3rd century BC atronomical/astrological poem by Aratus (based in turn on two prose works by 4th century BC astronomer Eudoxus of Cnidus). Several extant medieval copies are known, including the lavishly illuminated Leiden Aratea (circa 816):
Somewhat less sophisticated, early 11th century Limoges Aratea gives the image both separately and in context:
In the great Ptolemy’s treatise Almagest some of the constellation’s stars were specifically described as representing the club (Greek, Κολλοροβος) of Boötes. 9th century Assyrian scholar Johannitius didn’t know the word, so he translated it using a similar-looking Arabic word, arriving at العصى ذات الكلاب, al-`aşā dhāt al-kullāb, meaning “spearshaft with a hook”. You can get an idea of what he meant from this illustration, from a 1010 copy of Azophi‘s 964 Book of Fixed Stars:
In the first half of the 12th century, several decades after Alfonso VI conquered Toledo and ended more than two centuries of Moorish occupation, Italian scholar Gerard of Cremona found Almagest in one of the city’s many libraries and translated it into Latin, thus bringing the text back to the Western Civilization. Not a native speaker of Arabic, he mixed up the words kullāb (hook) and kilāb (dogs), and so the mysterious “hastile habens canes” (spearshaft with dogs) was born.
Finally, in 1687 Johannes Hevelius, best known as an early lunar cartographer, published Uranographia, proposing ten new constellations, most of them still being used today. One of them was Canes Venatici; amusingly, he also named the dogs, Asterion (Greek, “little star”) and Chara (“joy”):