2012 PERFORMANCE-BASED RESTRICTED STOCK UNIT AGREEMENT (Teradata Corporation 2007 Stock Incentive Plan)

Exhibit 10.11.9

2012 PERFORMANCE-BASED RESTRICTED STOCK UNIT AGREEMENT

(Teradata Corporation 2007 Stock Incentive Plan)

You have been awarded the contingent right to receive a credit of stock units (the “Stock Units”) under the Teradata Corporation 2007 Stock Incentive Plan (the “Plan”), upon the terms and subject to the conditions of this 2012 Performance-Based Restricted Stock Unit Agreement (this “Agreement”) and the Plan. Please refer to the stock unit information page on the website of Teradata’s third party Plan administrator for your “Target Number of Stock Units.”

1. Crediting of Stock Units.

(a) In General. Your right to receive a credit of all, a portion, or a multiple of the Target Number of Stock Units shall be contingent upon the extent to which Teradata Corporation (the “Company”) achieves the two equally weighted performance goals set forth below (the “Performance Goals”) for the performance period commencing January 1, 2012 and ending December 31, 2012 (the “Performance Period”), in accordance with the payout levels set forth on the attached Exhibit A (the “Performance Metrics”). For purposes of this Agreement, the Performance Goals are (i) revenue of the Company for the Performance Period, as determined in accordance with Generally Accepted Accounting Principles in the United States (“GAAP”) in effect at the time the revenue target is established, without regard to any change in accounting standards that may be required by the Financial Accounting Standards Board after the target is established, and (ii) earnings per share of the Company for the Performance Period, on a fully diluted basis, as reported on a non-GAAP basis, excluding stock compensation expense. The Compensation and Human Resource Committee of the Company’s Board of Directors (the “Committee”) may establish special adjustments that will be applied in calculating the extent to which the Performance Goals have been satisfied, provided that the adjustments are set forth in writing no later than 90 days after the beginning of the Performance Period.

(b) Crediting to Account. After the end of the Performance Period, the Committee shall determine in writing the extent, if any, to which each of the Performance Goals has been satisfied and shall determine the percentage, if any, of the Target Number of Stock Units that shall be credited to a book entry account established on your behalf (the “Account”), based on the payout level identified in the Performance Metrics. Each Stock Unit credited to your Account under this Section 1(b) shall represent the contingent right to receive one share of the Company’s common stock (a “Share”) and shall at all times be equal in value to one Share.

(i) If, upon the conclusion of the Performance Period, the Company achieves less than 25% of the target level of a Performance Goal, then you shall not receive a credit of any Stock Units with respect to that Performance Goal, and if the Company achieves less than 25% of the target level for both Performance Goals, this Agreement shall terminate immediately without further action or notice.

(ii) If, upon the conclusion of the Performance Period, the Company achieves 25% or more of the target level of a Performance Goal, then you shall be credited with a number of Stock Units with respect to such Performance Goal, effective on the day in which the Committee certifies the achievement of the Performance Goal as provided in this Section 1(b) (the “Crediting Date”), equal to the product of (A) your Target Number of Stock Units,

multiplied by (B) the combined weighted average of the payout levels for both Performance Goals as identified in the Performance Metrics (subject to such rounding conventions as may be implemented from time-to-time by Teradata’s third party Plan administrator).

(c) Forfeiture of Stock Units. Except as otherwise provided in Section 3, your right to receive a credit of Stock Units shall be forfeited automatically without further action or notice in the event that you cease to be employed by the Company or any of its affiliate companies (referred to collectively herein as “Teradata”) through the end of the Performance Period.

2. Vesting, Forfeiture and Payment of Stock Units.

(a) Vesting. The Stock Units, if any, credited to your Account in accordance with Section 1 above shall be subject to the following vesting schedule:

(i) One-third of the Stock Units shall vest on each of the following dates (subject to such rounding conventions as may be implemented from time to time by Teradata’s third party Plan administrator): (A) the Crediting Date, (B) the first anniversary of the Crediting Date, and (C) the second anniversary of the Crediting Date (each a “Vesting Date”), provided that you are continuously employed by Teradata until the applicable Vesting Date.

(ii) If you cease to be employed by Teradata due to (A) your death, or (B) your Disability (defined by reference to Teradata’s long-term disability plan that covers you), in either case after the end of the Performance Period but prior to a Vesting Date, then the Stock Units shall become fully vested upon such termination.

(iii) If you cease to be employed by Teradata prior to a Change in Control (as defined in the Plan) due to (A) your Retirement (defined as termination by you of your employment with Teradata at or after age 55 with the consent of the Committee); or (B) a reduction-in-force, in either case after the end of the Performance Period but prior to a Vesting Date, then a portion of the Stock Units credited to your Account that have not yet vested shall become fully vested upon such termination, determined by multiplying (I) the number of unvested Stock Units credited to your Account on the date of termination that would have vested on the next Vesting Date had you remained employed with Teradata through such date, by (II) a fraction, the numerator of which is the number of full and partial months of employment you completed commencing with the Vesting Date that occurred immediately prior to your termination, and the denominator of which is 12 months (with the resulting product rounded to the nearest whole number); provided that if your termination occurs during the period commencing immediately after the end of the Performance Period but prior to the Crediting Date, the fraction described above shall be deemed to be 12/12. The remaining number of Stock Units shall be forfeited without further action or notice.

(iv) If a Change in Control occurs after the end of the Performance Period and prior to a Vesting Date, and the Stock Units are not assumed, converted or replaced by the continuing entity, then the Stock Units shall vest upon the Change in Control.

(v) If a Change in Control occurs after the end of the Performance Period and prior to a Vesting Date, and the Stock Units are assumed, converted or replaced by

the continuing entity, then the Stock Units shall continue to vest in accordance with Section 2(a)(i); provided, however, that if you cease to be employed by Teradata due to (A) termination of your employment by Teradata without Cause (as such term is defined in the Plan), (B) termination of your employment with Teradata on account of death, Disability, Retirement, or a reduction-in-force, or (C) if you are a participant in the Teradata Change in Control Severance Plan, a Teradata Severance Policy or a similar arrangement that defines “Good Reason” in the context of a resignation following a Change in Control (a “CIC Plan”), termination of your employment with Teradata for “Good Reason” as defined in the CIC Plan within the two-year period commencing on the Change in Control, then the Stock Units credited to your Account that have not yet vested shall vest in full upon such termination.

(b) Forfeiture. The Stock Units credited to your Account that have not yet vested pursuant to Section 2(a) shall be forfeited automatically without further action or notice if you cease to be employed by Teradata prior to a Vesting Date other than as provided in Sections 2(a)(ii), (iii) or (v).

(c) Payment. Except as otherwise provided in Section 3 or Section 4 of this Agreement, the Company shall deliver the Shares underlying the vested Stock Units credited to your Account in accordance with this Agreement within seventy (70) days after the earlier of (i) the applicable Vesting Date(s), or (ii) your termination of employment.

3. Certain Events During Performance Period.

(a) Certain Terminations. If during the Performance Period you cease to be employed by Teradata prior to a Change in Control (as defined in the Plan) due to death, Disability, Retirement or a reduction-in-force, then the Company shall credit to your Account a pro-rated number of Stock Units, which shall be fully vested, and which shall be calculated by multiplying (i) the actual number of Stock Units that would have been credited to your Account in accordance with Section 1 of this Agreement had you continued in employment throughout the Performance Period, determined based on the actual performance of the Company during such Performance Period, by (ii) a fraction, the numerator of which is the number of full and partial months of employment you completed commencing with January 1, 2012, and the denominator of which is 36 months (subject to such rounding conventions as may be implemented from time-to-time by Teradata’s third party Plan administrator). Except as otherwise provided in Section 4 of this Agreement, the Company shall deliver to you the Shares underlying the pro-rated number of Stock Units within seventy (70) days after the end of the Performance Period.

(b) Change in Control.

(i) If a Change in Control occurs during the Performance Period, and this award is not assumed, converted or replaced by the continuing entity, then the Target Number of Stock Units shall be credited to your Account, as of the date of the Change in Control, and the units shall be fully vested at that time. The Company shall deliver to you the Shares underlying the Target Number of Stock Units within 30 days after such Change in Control. Notwithstanding the foregoing, to the extent that your right to receive such Shares constitutes a “deferral of compensation” within the meaning of Section 409A of the Code

(“Section 409A”), the Company shall deliver to you the Shares underlying the Target Number of Stock Units within seventy (70) days after the earlier of (i) the end of the Performance Period, or (ii) your termination of employment (except as otherwise provided in Section 4 of this Agreement).

(ii) If a Change in Control occurs during the Performance Period, and this award is assumed, converted or replaced by the continuing entity, then the Target Number of Stock Units shall be credited to your Account, as of the date of the Change in Control, and the Stock Units shall continue to vest in accordance with Section 2(a)(i); provided, however, that if you cease to be employed by Teradata due to (A) termination of your employment by Teradata without Cause (as such term is defined in the Plan), (B) termination of your employment with Teradata on account of death, Disability, Retirement, or a reduction-in-force, or (C) if you are a participant in a CIC Plan, termination of your employment with Teradata for “Good Reason” as defined in the CIC Plan within the two-year period commencing on the Change in Control, then the Stock Units credited to your Account that have not yet vested shall vest in full upon such termination. If the Target Number of Stock Units credited to your Account in accordance with this Section 3(b)(ii) becomes vested by reason of a termination of your employment that occurs on or prior to the end of the Performance Period, then, except as otherwise provided in Section 4 of this Agreement, the Company shall deliver to you the Shares underlying the Target Number of Stock Units within seventy (70) days after the end of the Performance Period. If the Target Number of Stock Units credited to your Account in accordance with this Section 3(b)(ii) becomes vested after the end of the Performance Period, then except as otherwise provided in Section 4 of this Agreement, the Company shall deliver the Shares underlying the vested Target Number of Stock Units credited to your Account within seventy (70) days after the earlier of (x) the applicable Vesting Date(s), or (y) your termination of employment.

4. Section 409A Compliance. The intent of the parties is that payments under this Agreement comply with Section 409A of the Code or are exempt therefrom and this Agreement shall be interpreted, administered and governed in accordance with such intent.

(a) Termination of Employment. To the extent that you are a U.S. taxpayer, a termination of employment shall not be deemed to have occurred for purposes of any provision of this Agreement providing for the payment of Shares subject to Section 409A upon or following a termination of employment unless such termination is also a “separation from service” within the meaning of Section 409A and you are no longer providing services (at a level that would preclude the occurrence of a “separation from service” within the meaning of Section 409A) to Teradata as an employee or consultant, and for purposes of any such provision of this Agreement, references to a “termination,” “termination of employment” or like terms shall mean “separation from service” within the meaning of Section 409A.

(b) Payment Delay for Specified Employees. If you are a “specified employee,” as determined under the Company’s policy for identifying specified employees on the date of termination, then to the extent required in order to comply with Section 409A, all payments made under this Agreement that constitute a “deferral of compensation” within the meaning of Section 409A that are provided as a result of a “separation from service” within the meaning of Section 409A for any reason other than your death and that would otherwise be paid or provided during the first six months following such separation from service shall be

accumulated through and paid within 30 days after the first business day that is more than six months after the date of your separation from service (or, if you die during such six-month period, within 30 days after your death).

(c) Acceleration of Payment. Notwithstanding anything to the contrary contained in this Agreement, the Committee shall have the right, at any time in its sole discretion, to accelerate the time of a payment under this Agreement to a time otherwise permitted under Section 409A in accordance with the requirements, restrictions and limitations of Treasury Regulation Section 1.409A-3(j).

5. Confidentiality. By accepting this award, unless disclosure is required by applicable law or regulation, you agree to keep this Agreement confidential and not to disclose its contents to anyone except your attorney, your immediate family, or your financial consultant, provided such persons agree in advance to keep such information confidential and not disclose it to others. The Stock Units will be forfeited if you violate the terms and conditions of this Section 5.

6. Transferability. At all times before payment, the Stock Units may not be sold, transferred, pledged, assigned or otherwise alienated, except by beneficiary designation, will or by the laws of descent and distribution upon your death. Any purported transfer or encumbrance in violation of the provisions of this Section 6 shall be void, and the other party to any such purported transaction shall not obtain any rights to or interest in such Stock Units.

7. Dividend Equivalents. From and after the Crediting Date and until the earlier of (a) the time when the Stock Units are paid in accordance with this Agreement or (b) the time when your rights in the Stock Units are forfeited in accordance with Section 2(b) hereof, on the date that Teradata pays a cash dividend (if any) to holders of Shares generally, you shall receive additional Stock Units equal to (x) the number of Stock Units held by you as of the date of record for such dividend, provided that the record date occurs on or after the Crediting Date; multiplied by (y) the per Share cash dividend amount; divided by (z) the Fair Market Value per Share on the dividend payment date. The additional Stock Units shall be subject to the same terms and conditions as the Stock Units covered by this Agreement, including without limitation the forfeiture provisions of Section 2(b) of this Agreement; provided, however, that for purposes of Section 2(a)(i) of this Agreement (i) any such additional stock units issued between the Crediting Date and the first anniversary of the Crediting Date shall vest in two equal installments on the first anniversary of the Crediting Date and the second anniversary of the Crediting Date, provided that you are continuously employed by Teradata through each such date, and (ii) any such additional stock units issued between the first anniversary of the Crediting Date and the second anniversary of the Crediting Date shall vest on the second anniversary of the Crediting Date, provided that you are continuously employed by Teradata through such date.

8. Misconduct. Your rights under this Agreement shall be forfeited if the Committee determines that you engaged in misconduct in connection with your employment with Teradata.

9. Withholding. Teradata has the right to deduct or cause to be deducted from, or collect or cause to be collected, with respect to the taxation of any Stock Units, any federal, state,

local, foreign or other taxes required by the laws of the United States or any other country to be withheld or paid with respect to the Stock Units, and you or your legal representative or beneficiary will be required to pay any such amounts. By accepting this award, you consent and direct that, if you are paid through Teradata’s United States payroll system at the time the Stock Units are settled, Teradata’s stock plan administrator will withhold or sell the number of Shares underlying the Stock Units as Teradata, in its sole discretion, deems necessary to satisfy such withholding requirements; provided, however, that if Teradata is required to withhold any taxes prior to settlement of the Stock Units, then you agree that Teradata may satisfy those withholding obligations by withholding cash from your compensation otherwise due to you or by any other action as it may deem necessary to satisfy the withholding obligation. In no event shall the Fair Market Value of the Shares of common stock to be surrendered pursuant to this section to satisfy applicable withholding taxes exceed the minimum amount of taxes required to be withheld or such other amount that will not result in a negative accounting impact. If you are paid through a non-United States Teradata payroll system, you agree that Teradata may satisfy any withholding obligations by withholding cash from your compensation otherwise due to you or by any other action as it may deem necessary to satisfy the withholding obligation.

10. Restrictive Covenants. In exchange for the Stock Units, you agree that during your employment with Teradata and for a period of twelve (12) months after the termination of employment (or if applicable law mandates a maximum time that is shorter than twelve months, then for a period of time equal to that shorter maximum period), regardless of the reason for termination, you will not, without the prior written consent of the Chief Executive Officer of Teradata, (a) render services directly or indirectly to, or become employed by, any Competing Organization (as defined in this Section 10 below) to the extent such services or employment involves the development, manufacture, marketing, sale, advertising or servicing of any product, process, system or service which is the same or similar to, or competes with, a product, process, system or service manufactured, sold, serviced or otherwise provided by Teradata to its customers and upon which you worked or in which you participated during the last two (2) years of your Teradata employment; (b) directly or indirectly recruit, hire, solicit or induce, or attempt to induce, any exempt employee of Teradata to terminate his or her employment with or otherwise cease his or her relationship with Teradata; or (c) solicit the business of any firm or company with which you worked during the preceding two (2) years while employed by Teradata, including customers of Teradata. If you breach the terms of this Section 10, you agree that in addition to any liability you may have for damages arising from such breach, any unvested Stock Units will be immediately forfeited, and you agree to pay to Teradata the Fair Market Value of any Stock Units that vested and that were paid during the twelve (12) months prior to the date of termination of your employment. Such Fair Market Value shall be determined as of the date that the Stock Units become vested. If you breach the terms of this Section 10 prior to the end of the Performance Period but after you incur a termination described in Section 3(a) of this Agreement, your award will be forfeited and you will not receive the pro-rata portion of the Stock Units.

As used in this Section 10, “Competing Organization” means an organization identified as a Competing Organization by the Chief Executive Officer of Teradata for the year in which your employment with Teradata terminates, and any other person or organization which is engaged in or about to become engaged in research on or development, production, marketing, leasing, selling or servicing of a product, process, system or service which is the same or similar to or

competes with a product, process, system or service manufactured, sold, serviced or otherwise provided by Teradata to its customers. The list of Competing Organizations identified by the Chief Executive Officer is maintained by the Teradata Law Department.

11. Arbitration. By accepting this award, you agree that, where permitted by local law, any controversy or claim arising out of or related to your employment relationship with Teradata shall be resolved by first exhausting any Teradata internal dispute resolution process and policy, and then by arbitration pursuant to such policy. If you are employed outside the United States, where permitted by local law, the arbitration shall be conducted in the regional headquarters city of the business unit in which you work. The arbitration shall be held before a single arbitrator who is an attorney knowledgeable in employment law. The arbitrator’s decision and award shall be final and binding and may be entered in any court having jurisdiction. For arbitrations held in the United States, issues of arbitrability shall be determined in accordance with the federal substantive and procedural laws relating to arbitration; all other aspects shall be interpreted in accordance with the laws of the state in which the headquarters of Teradata is located. Each party shall bear its own attorney’s fees associated with the arbitration and other costs and expenses of the arbitration shall be borne as provided by the rules of the American Arbitration Association for an arbitration held in the United States, or similar applicable rules for an arbitration held outside the United States.

Notwithstanding the preceding subparagraph, you acknowledge that if you breach Section 10, Teradata will sustain irreparable injury and will not have an adequate remedy at law. As a result, you agree that in the event of your breach of Section 10 Teradata may, in addition to any other remedies available to it, bring an action in a court of competent jurisdiction for equitable relief to preserve the status quo pending appointment of an arbitrator and completion of an arbitration. You stipulate to the exclusive jurisdiction and venue of the state and federal courts located in the location from which Teradata’s equity programs are administered, for any such proceedings.

12. Compensation Recovery Policy. By accepting this award, you acknowledge and agree that, notwithstanding any other provision of this Agreement to the contrary, you may be required to forfeit or repay any or all of the Stock Units pursuant to the terms of the Teradata Corporation Compensation Recovery Policy (or a successor policy), as the same may be amended to comply with the Dodd-Frank Wall Street Reform and Consumer Protection Act or any rules or regulations issued by the Securities and Exchange Commission or applicable securities exchange.

13. Beneficiaries; Successors.

(a) Without limiting Section 6 of this Agreement, you may designate one or more beneficiaries to receive all or part of any Stock Units to be distributed in case of your death, and you may change or revoke such designation at any time. In the event of your death, any Stock Units distributable hereunder that are subject to such a designation will be distributed to such beneficiary or beneficiaries in accordance with this Agreement. Any other Stock Units not designated by you will be distributable to your estate. If there is any question as to the legal right of any beneficiary to receive a distribution hereunder, the Stock Units in question may be transferred to your estate, in which event Teradata will have no further liability to anyone with respect to such Stock Units.

(b) The provisions of this Agreement shall inure to the benefit of, and be binding upon, your successors, administrators, heirs, legal representatives and assigns, and the successors and assigns of the Company.

14. Severability. The provisions of this Agreement are severable. If any provision of this Agreement is held to be unenforceable or invalid by a court or other tribunal of competent jurisdiction (including an arbitration tribunal), it shall be severed and shall not affect any other part of this Agreement, which will be enforced as permitted by law.

15. Amendment. The terms of this award of Stock Units as evidenced by this Agreement may be amended by the Teradata Board of Directors or the Committee.

16. Adjustments. The number of Stock Units and the number and kind of shares of stock covered by this Agreement shall be subject to adjustment as provided in Section 3 of the Plan.

17. Plan Governs. In the event of a conflict between the terms and conditions of this Agreement and the terms and conditions of the Plan, the terms and conditions of the Plan shall prevail, except that with respect to matters involving choice of law, the terms and conditions of Section 10 of this Agreement shall prevail.

18. Dividend; Voting Rights. You shall not possess any incidents of ownership (including, without limitation, dividend and voting rights) in the Shares underlying the Stock Units credited to your Account until such Shares have been delivered to you in accordance with Section 2, Section 3 or Section 4 hereof. The obligations of the Company under this Agreement will be merely that of an unfunded and unsecured promise of the Company to deliver Shares in the future, and your rights will be no greater than that of an unsecured general creditor. No assets of the Company will be held or set aside as security for the obligations of the Company under this Agreement.

19. No Employment Contract. Nothing contained in this Agreement shall confer upon you any right with respect to continuance of employment by Teradata, nor limit or affect in any manner the right of Teradata to terminate your employment or adjust your compensation.

20. Non-U.S. Employees. Notwithstanding any provision herein, if your employment with Teradata is subject to the rules and regulations of one or more non-United States jurisdictions, then your participation in the Plan shall be subject to any special terms and conditions as set forth in any appendix for your country (the “Appendix”). Moreover, if you relocate to one of the countries included in the Appendix, the special terms and conditions for such country will apply to you, to the extent the Company determines that the application of such terms and conditions is necessary or advisable in order to comply with local law or facilitate the administration of the Plan. The Appendix constitutes part of this Agreement.

21. Acceptance of Terms. By accepting any benefit under this Agreement, you and each person claiming under or through you shall be conclusively deemed to have indicated their acceptance and ratification of, and consent to, all of the terms and conditions of this Agreement and the Plan and any action taken under this Agreement or the Plan by the Committee, the Board or Teradata, in any case in accordance with the terms and conditions of this Agreement.

22. Electronic Delivery. Teradata may, in its sole discretion, decide to deliver any documents related to current or future participation in the Plan by electronic means. You hereby consent to receive such documents by electronic delivery and agree to participate in the Plan through an on-line or electronic system established and maintained by Teradata or a third party designated by Teradata.

APPENDIX

Form of 2012 Performance-Based Restricted Stock Unit Agreement

For Non-U.S. Employees

Under the Teradata Corporation 2007 Stock Incentive Plan

Terms and Conditions

This Appendix includes additional terms and conditions that govern the Stock Units granted to you under the Plan if you reside in one of the countries listed below. Certain capitalized terms used but not defined in this Appendix have the meanings set forth in the Plan and/or the Agreement.

Notifications

This Appendix may also include information regarding exchange controls and certain other issues of which you should be aware with respect to your participation in the Plan. The information is based on the securities, exchange control and other laws in effect in the respective countries as of November 2008. Such laws are often complex and change frequently. As a result, the Company strongly recommends that you not rely on the information in the Appendix as the only source of information relating to the consequences of your participation in the Plan because the information may be out of date at the time that your Stock Units vest or you sell Shares acquired under the Plan.

In addition, the information contained herein is general in nature and may not apply to your particular situation and the Company is not in a position to assure you of any particular result. Accordingly, you are advised to seek appropriate professional advice as to how the relevant laws in your country may apply to your situation.

Finally, if you are a citizen or resident of a country other than the one in which you are currently working, the information contained herein may not be applicable to you.

AUSTRALIA

Settlement of Stock Units. Notwithstanding any discretion in the Plan or anything to the contrary in the Agreement, the grant of Stock Units does not provide any right for you to receive a cash payment and the Stock Units are payable in Shares only.

Securities Law Information. If you acquire Shares under the Plan and you offer such Shares for sale to a person or entity resident in Australia, the offer may be subject to disclosure requirements under Australian law. You should obtain legal advice on your disclosure obligations prior to making any such offer.