The topic has been the source of heated discussions in Brussels for several years now, as the European commission first introduced a legislative proposal in 2011. In recent months, it once again took centre stage amid concerns jihadists were entering Europe.
No PNR legislation has so far been able to win parliament's support, and in April last year the European court of justice ruled that mass storage of private data without any time limit or justification was illegal.
Nevertheless, last December, EPP group member Roberta Metsola, who sits on parliament's civil liberties, justice and home affairs committee (LIBE), said, "having such a directive would increase security and with sufficient oversight, systems will be beneficial for citizens across the EU".
Members of parliament have heavily criticised PNR because, in their view, it is a violation of privacy and Europe needs effective data protection regulation before a system can be put in place.
However EPP group chair Manfred Weber rejected the idea, saying, "it would be a mistake to link PNR and EU data protection".
"The mass and indiscriminate retention of data without any concrete suspicion does not make Europe safer - the current debate is fuelled by populism rather than substance" - Jörg Leichtfried
ECR deputy Timothy Kirkhope, parliament's rapporteur on PNR, called for "an agreement that safeguards lives and liberties by offering stronger data protection rules while also making it much harder for a radicalised fighter to slip back into Europe undetected".
Last November, Birgit Sippel, S&D group spokesperson on civil liberties, justice and home affairs, warned that "as long as EU governments oppose the adoption of new rules on data protection, it will be impossible for the European parliament to pass a European PNR system".
She accused the commission's proposal of lacking "solid safeguards when it comes to data protection and other fundamental rights provisions".
S&D vice-president Jörg Leichtfried added, "the mass and indiscriminate retention of data without any concrete suspicion does not make Europe safer - the current debate is fuelled by populism rather than substance".
He stressed that the socialists "will not be rushed into a decision that has potentially severe consequences for civil liberties of EU citizens".
And indeed parliament has been taking its time, as the commission presented its first legislative proposal on the EU data protection regulation in January 2012, and rapporteur Jan Albrecht recently warned that there would likely be no agreement between parliament, commission and council until the end of the year.
The LIBE vice-chair has pointed the finger at EU home affairs ministers for "playing into terrorists' hands by demanding 'big brother' measures entailing blanket data retention without justification".
"It would be a mistake to link PNR and EU data protection" - Manfred Weber
He highlighted that "far-reaching data collection in France would not have prevented the odious attacks in Paris", as reports have suggested the perpetrators were known to the French authorities.
Albrecht called on the commission to "withdraw its proposal for a European air passenger data retention scheme and instead come forward with proposals and an action plan for better cooperation between police and security authorities in Europe".
However, there seem to be some disagreements within parliament's Greens/EFA group, as French deputy Yannick Jadot said, "I am in favour of a European PNR system - it needs to be useful and respectful".
In ALDE group president Guy Verhofstadt's view, the problem is that, "whereas more and more information is collected on citizens, sharing of information has been lagging behind".
He added, "instead of the Pavlov reflex of calling for more data collection, we should focus on better information exchange and better cooperation".
Sophie in 't Veld warned that there would be "no new powers without new safeguards", and requested the council adopt the directive on data protection at the same time as a directive on PNR.
Debate on the topic is likely to rage on throughout the parliamentary term, and Latvian prime minister Laimdota Straujuma, whose country's EU council presidency has just started, has promised to discuss it with MEPs.