Exhibit 10.15

Form of Performance Based Restricted Stock Agreement

Under the Teradata 2007 Stock Incentive Plan

You have been awarded a number of restricted shares of Teradata common stock (the “Restricted Stock”) under the 2007 Stock Incentive Plan (the “Plan”) of Teradata Corporation (“Teradata”), as listed on the restricted stock grant information page on the website of Teradata’s third party Plan administrator, subject to the terms and conditions of this 2007 Performance Based Restricted Stock Agreement (this “Agreement”) and the Plan.

1. All, a portion, a multiple, or none of the Restricted Stock will become nonforfeitable (“Vested”) on the date (your “Vesting Date”) that the Compensation & Human Resource Committee of the Teradata Board of Directors (the “Committee”) determines that the performance goals set forth on Exhibit A (the “Performance Goals”) have been achieved during the period from [            ] through [            ] (the “Performance Period”) at the level described in Section 2 below, provided that (i) you are continuously employed by Teradata or any of its affiliate companies (referred to collectively herein as “Teradata”) until your Vesting Date, and (ii) the applicable performance measures described in Section 2 below are met.

2. Subject to your continued employment through the Vesting Date, in the event that Teradata achieves the Performance Goal during the Performance Period, you will become Vested on your Vesting Date in a designated percentage of the Restricted Stock awarded to you under this Agreement, as set forth on Exhibit A. The Performance Goal will be determined by the Committee, and will be communicated in your award letter.

3. If your employment with Teradata terminates prior to your Vesting Date due to (i) your death; (ii) cessation of active employment by Teradata as a result of a disability for which you qualify for benefits under the Teradata Long-Term Disability Plan or another long-term disability plan sponsored by Teradata (“Disability”); (iii) Retirement (defined as termination by you of your employment with Teradata at or after age 55 with the consent of the Committee, other than, if applicable to you, for Good Reason (as described below) following a Change in Control (as defined in the Plan)); or (iv) reduction-in-force; then, on your Vesting Date, and based upon the Committee’s determination of the Performance Goal, a pro rata portion of the Restricted Stock will become Vested. The pro rata portion will be determined by calculating the total number of shares you would have received (through vesting of Restricted Stock) if your Teradata employment had not terminated prior to your Vesting Date, and multiplying that number by a fraction, the numerator of which is the number of full and partial months of employment you completed after the date of grant of this award (the “Grant Date”), and the denominator of which is the number of months in the Performance Period. If your employment terminates prior to your Vesting Date for any reason other than as otherwise described in this Section 3, the Restricted Stock will automatically be forfeited and no shares will be issued.

Notwithstanding any provision in this Agreement to the contrary:

(i) in the event a Change in Control occurs on or prior to the first anniversary of grant and this restricted stock award is not assumed, converted or replaced by the continuing entity, the Restricted Stock shall vest immediately prior to the Change in Control (without regard to performance or pro-ration) at the “Target” level,

(ii) in the event a Change in Control occurs after the first anniversary of grant and this restricted stock award is not assumed, converted or replaced by the continuing entity, the Restricted Stock shall vest immediately prior to the Change in Control (without regard to performance after the Change in Control or pro-ration) based on actual performance through the end of the calendar year immediately preceding the date on which the Change in Control occurs,

(iii) in the event of a Change in Control on or prior to the first anniversary of grant wherein this restricted stock award is assumed, the Restricted Stock shall vest at the end of the Performance Period (without regard to performance or pro-ration) at the “Target” level, subject to your continued employment through the end of the Performance Period, and

(iv) in the event of a Change in Control after the first anniversary of grant wherein this restricted stock award is assumed, the Restricted Stock shall vest at the end of the Performance Period (without regard to performance after the Change in Control or pro-ration) based on actual performance through the end of the calendar year immediately preceding the date on which the Change in Control occurs, subject to your continued employment through the end of the Performance Period.

Notwithstanding the provisions of clause (iii) and (iv) to the contrary, if, during the 24 months following the Change in Control, you incur a Termination of Employment (as defined in the Plan) by the Company other than for Cause or Disability (as such terms are defined in the Plan) or, 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, to the extent not then-vested, the Restricted Stock shall vest immediately upon your Termination of Employment at the level specified in clause (iii) or (iv) as applicable.

4. 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 Restricted Stock will be forfeited if you violate the terms and conditions of this Section 4.

5. You will be the record owner of the Restricted Stock until such shares are forfeited, and as the record owner you will be entitled to all rights of a common stockholder of Teradata, including without limitation, voting rights and rights to cash and in-kind dividends, if any, on the Restricted Stock; provided, however, that the right to dividends will be subject to Section 8 below, and, prior to your Vesting Date, the Restricted Stock is not freely transferable. As soon as practicable after your Vesting Date, subject to Section 9 below, Teradata will instruct its Transfer Agent and/or third party Plan administrator to release the restrictions on your record account and the Restricted Stock will become freely transferable.

6. Prior to Vesting, the Restricted Stock 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.

2

7. Any regular cash dividends declared before your Vesting Date on the Restricted Stock shall not be paid currently, but shall be reinvested in shares of common stock of Teradata. Any shares resulting from such reinvestment (the “Dividend Shares”) will be considered Restricted Stock for purposes of this Agreement and will be subject to all of the terms, conditions and restrictions set forth herein. As of each date that Teradata would otherwise pay the declared dividend on the Restricted Stock (the “Dividend Payment Date”) in the absence of the reinvestment requirements of this Section 7, the number of Dividend Shares will be determined by dividing the amount of dividends otherwise attributable to the Restricted Stock but not paid on Dividend Payment Date by the Fair Market Value of Teradata’s common stock on the Dividend Payment Date. The Committee may, in its discretion, take such action as it deems appropriate regarding in-kind dividends or distributions with respect to the Restricted Stock prior to your Vesting Date, which actions may include, without limitation, current distribution or liquidation or reinvestment in Restricted Stock. Any securities or property so distributed may, in the Committee’s discretion, be subject to any or all of the forfeiture provisions set forth in this Agreement.

8. 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 Restricted Stock, any federal, state or local taxes required by the laws of the United States or any other country to be withheld or paid with respect to the Restricted Stock, 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 Restricted Stock vests, Teradata’s stock plan administrator will withhold or sell the number of shares of Restricted Stock from your award as Teradata, in its sole discretion, deems necessary to satisfy such withholding requirements. 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.

9. In exchange for the Restricted Stock, 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, (1) render services directly or indirectly to, or become employed by, any Competing Organization (as defined in this Section 9) 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; (2) 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 (3) 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 9, you agree that in addition to any liability you may have for damages arising from such breach, any unvested Restricted Stock will be immediately forfeited, and you will pay to Teradata the Fair Market Value of any Restricted Stock that Vested during the twelve (12) months prior to the date of termination of your

3

employment. Such Fair Market Value shall be determined as of the Vesting Date. If you breach the terms of this Section 9 prior to the end of the Performance Period but after your employment terminates due to the circumstances described in the first paragraph of Section 3, your award will be forfeited and you will not receive a pro rata portion of the Restricted Stock.

As used in this Section 9, “Competing Organization” means an organization identified by the Chief Executive Officer of Teradata as a Competing Organization 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 is maintained by the Teradata Law Department.

10. By accepting the Restricted Stock, you agree that, where permitted by local law, any controversy or claim arising out of your employment relationship with Teradata shall be resolved by arbitration. If you are employed in the United States, the arbitration shall be pursuant to the Teradata dispute resolution policy and the then current rules of the American Arbitration Association and shall be held in the city of the location of the headquarters of Teradata. 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. The Restricted Stock will be forfeited if the Committee determines that you engaged in misconduct in connection with your employment with Teradata.

Notwithstanding the preceding subparagraph, you acknowledge that if you breach Section 9, 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 9 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.

11. You may designate one or more beneficiaries to receive all or part of any Restricted Stock 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 Restricted Stock distributable hereunder that is subject to such a designation will be distributed to such beneficiary or beneficiaries in accordance with this Agreement. Any other Restricted Stock not designated by you will be distributable to your estate. If there is any question as to the legal right of any beneficiary to

4

receive a distribution hereunder, the Restricted Stock in question may be transferred to your estate, in which event Teradata will have no further liability to anyone with respect to such Restricted Stock.

12. 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.

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

14. 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.

5