SQL Server - Relación entre tablas-->borrado lento

Hola a todos :
Tengo una tabla "MUCHOS" que implementa una relación muchos a muchos entre las tablas A y B. Tanto A como B sólo tienen un campo cada una que indique su clave primaria, PKA varchar(30) para la tabla A y PKB varchar(10) para la tabla B. La tabla MUCHOS tiene como clave primaria los dos campos , PKA varchar(30) y PKB varchar(10) aparte de algunos otros. Ninguna de las tres tablas tiene más indices definidos.
Esta tabla MUCHOS, a su vez se relaciona con varias tablas (aproximadamente 20) que requiren la presencia en cada uno de sus registros de un par que aparezca en la tabla MUCHOS. Hasta aquí nada raro y todo funciona correctamente y rápido (inserciones, borrados, etc..). Mis problemas surgen cuando, realizando unas pruebas de estres, varias de estas 20 tablas se completaron con aproximadamente 500.000 registros cada una.
Con esta situación cuando intento borrar un registro de la tabla MUCHOS el tiempo de espera para que las relaciones comprueben si se puede borrar y luego se borre se eleva a más de 1 minuto (1.30 en algunos casos) directamente desde SQLSERVER (Administrador corporativo o analizador de consultas). Si elimino la relación entre la tabla MUCHOS y las que tienen tantos registros, entonces el tiempo de borrado es aceptable.
¿Cómo se puede resolver el problema?. Por favor, necesito ayuda ya que el volumen de datos que he puesto será lo que me encuentre en producción.
GRACIAS DE ANTEMANO. Espero vuestras respuestas.
Uso SQL SERVER 70 sobre W2000 server .
Jesús Corbí.

Crea índices en las tablas y sobre todo en la tabla de la que queres borrar los registros. No me estoy refiriendo a restricciones (foreign keys) sino a índices (CREATE INDEX) que aumentan la velocidad.

Apoyo a Cecilia, ademas te sugiero que asignes los indices forzosamente con:

Select CAMPO1,CAMPO2
from TABLA1 (INDEX = PK_INDICE1 ),
TABLA2 (INDEX = IDXU_INDICE2 )
WHERE TABLA1.CAMPOA = TABLA2.CAMPOA

Haz prueba, yo tengo unas relaciones complicadas con una tabla de 240,000 registros y asi logre tiempos aceptables.

atte: Amigo de Sonora,Mexico.

Gracias por tu consejo Victor. Lo probaré.
Jesús.

Amigo de Alicante, España.

hola!!! antes que nada mis saludos a un posible futuro colega (si llego a terminar la carrera de ing informatica que es la que estoy estudiando ahora)
con respecto a tu consulta del borrado de tablas, eso de eliminar las relaciones es lo mas conveniente en funcion del tiempo. es decir que si quieres que la cosa sea rapida, eso es lo que debes hacer (elimiar relacion, borrar registro, reestablecer relacion) ya que debido al volumen de registros con que cuenta tu tabla, es normal que se tome ese tiempo, ya que debido a eso que dices (5000 registros) es relativamente poco!!.
espero te haya servido de algo esta pequeña ayudita.
Exitos!!
PAOLA

Gracias por tu aportación. Espero que termines tu carrera lo antes posible. Cuando lo hagas y te enfrentes al desarrollo en la vida real, verás que hay factores que no te enseñan en la Universidad. No se pueden deshabilitar relaciones de integridad así como así ya que se trata de un BD multiusuario a la que acceden muchos (pero muchos) usuarios por lo que no se puede eliminar la integridad referencial ni un milisegundo. Tampoco puedo bloquear la tabla/s implicada/s tanto tiempo como tarda el borrado. GRACIAS de todos modos y suerte.

Quizas debes reconsiderar el diseño de la estructura de la BBDD para que sea mas operativa si las operaciones de borrado/ actualizacion son frecuentes y el volumen de registros es muy gande.
Si tienes tantas relaciones entre las tablas es normal que se tome su tiempo revisando la integridad.

Gracias por tu consejo. ¿Podrías particularizar un poco más con lo de reconsiderar el diseño? . Tengo tantas relaciones como son necesarias para mantener la integridad referencial (aun falta alguna que otra que algún torpe se ha dejado sin crear). En una tabla de clientes no creo que se deba permitir poner un código de tarifa que no exista en una tabla de tarifas ( por poner un ejemplo) y así con muchas FK que tengo definidas. Si te puedes explicar un poco más te estaría muy agradecido.
Jesús.