Copyright ACM, 2000

DISTRIBUTED QUERY PROCESSING

USING ACTIVE NETWORKS

 

 

Zhili Zhang

Tibco Corporation

zhili@tibco.com

 

William Perrizo

North Dakota State University

perrizo@plains.nodak.edu

 

KEYWORDS

 

query, active-network, distributed, latency, join.

 

ABSTRACT

 

In this paper, we present an efficient method for implementing distributed query processing on high speed wide area active networks. A discussion of the characteristics of high-speed wide area networks, traditional low speed networks, their differences and active networks is presented. A set of design criteria for distributed database systems over high speed WANs is derived based on these characteristics and differences. A distributed domain vector acceleration method is extended for distributed multi-way joins in this environment based on these design criteria. We develop a cost model to estimate response time and then compare the response time of our new method to that of a theoretical lower bound. We show that the response time cost for this method is very close to the theoretical lower bound. We further show that active networking can reduce the bandwidth requirement for distributed query meta-data processing by an order of magnitude compared to that of non-active processing.

 

  1. INTRODUCTION

 

In this paper, we compare transmission delay with latency and show why design strategies for query processing should be re-examined based on this comparison. In conventional networks, transmission delay is regarded as the dominant factor in the communication cost function. For that reason, many distributed query processing algorithms are devised to minimize the amount of data transmitted over the network. However, in high speed networks, latency (as well as local processing time and disk I/O) becomes significant cost factors. To see how the reversal of transmission delay and latency takes place [PVZ+96], we look at an example (see figure 1). The

approximate delay to transmit a 1 Mbit file across the United States on a gigabit network will be 20 milliseconds latency and an additional 1 millisecond

 

 

 

 

 

for transmission time (figure 1 (b)). In a conventional

network of 50 kbps, though the latency remains 20 milliseconds, the transmission delay to transmit a 1Mbit file across the US is now 20 seconds (figure 1 (a)). It can be clearly seen that in the high speed network, the transmission delay, in this case 1 millisecond, is small when compared to the latency delay of 20 milliseconds, whereas, in the low speed network, the transmission delay of 20 seconds is large relative to the 20 millisecond latency delay. We note that latency delay is independent of network speed (depends only on the distance and speed of light, which is constant).

 

  1. (b)

 

Figure 1. Data Transfer Time

 

From this example we can see that for relatively small messages, latency dominates transmission delay in high speed wide area networks. When the message is very large, data reduction may still be needed before transmitting over the network.

 

    1. Bandwidth-on-Demand
    2.  

      Bandwidth-on-Demand (BoD), long talked about, is now becoming a reality in the commercial market place. High Speed network protocols such as ATM are fundamentally connection-oriented [ALL95] and a virtual circuit must be set up across the ATM network prior to any data transfer. There are two possible ways that this circuit can be set up. A permanent virtual circuit (PVC) can be set up in advance for all connections or switched virtual circuit (SVC) connections can be set up and torn down on demand as needed. To set up a SVC connection, the source ATM end-system initiates ATM signaling. The signaling is routed through the network, from switch to switch, setting up the connection identifiers as it goes, until it reaches the destination end system. The destination site can either accept and confirm the connection request, or can reject it, clearing the connection. ATM circuit connection setup is complicated and involves at least one round trip message between the two end systems. This will be an extra delay cost in the response time of a query compared with connection-less networks, unless it can be hidden in the algorithm through parallelism. If PVCs are assumed, the setup costs are amortized over the long term, however, if SVCs are used, we must factor in their setup and tear down costs as part of the query.

       

    3. Multicast
    4.  

      Multicast is implemented using a point to multi-point unidirectional connection mechanism. It requires that each end point in the point to multi-point connection be set up individually. Most current protocols, particularly those developed for LANs, implicitly assume a network infrastructure that is a shared-medium, connectionless technology with implicit broadcast mechanisms. ATM alters all of these assumptions [ALL95]. Because of this, the use of multicast must be optimized by the query. To hide the latency involved in connection setup, a productive strategy would be to set up as few sequential connections as possible for a particular query.

       

    5. Design Strategies

 

In high bandwidth wide area networks, the amount of data transmitted is no longer the dominant factor when compared to latency and local processing time. Technology advances may increase the processor capacity, disk access speed, and memory access time, which will reduce local processing time, however, due to the fixed, finite speed of light, technology will not be able to reduce latency delay. Hence, as network bandwidths become higher and higher, latency delay will become more and more dominant as a delay factor for response time. New connection-oriented protocols, such as ATM offer true bandwidth-on-demand through the use of SVCs but also introduce new challenges such as a lack of implicit multicast.

 

In other words, in future distributed query processing techniques, we must strive to reduce the number of sequential messages being sent in the network, therefore reducing total latency delay, instead of striving to only minimize the amount of data transmitted, as was done in the past. In addition, we must learn to exploit the new features such as BoD and deal with the problems caused by the new protocols. Of course, reducing the local processing times, such as disk I/O and CPU processing, will also speed up the execution of queries.

 

In summary, a set of productive strategies for implementing distributed query processing on high speed, connection oriented WANs is as follows:

 

(1) Reduce the total latency by minimizing

sequential message passing.

  1. If Bandwidth-on-Demand such as SVCs in ATM are used, set up as few sequential connections as possible to reduce the round-trip propagation delay incurred in connection setup. In addition, if monetary cost of connection time is critical, tear down SVC connections as soon as possible.
  2. If multicast is used, care must be taken to optimize the connections.

 

  1. DISTRIBUTED JOIN PROCESSING
  2.  

    Distributed query processing over a conventional wide area communication network is very expensive, due mainly to data transmission and I/O costs. The join operation is one of the most common and most expensive operations in distributed query processing. Three general techniques for distributed join processing are typically used. They are nested loop, sort merge and hash join. The nested loop join technique and the sort merge join technique [BLA77] were developed first. Both nested loop and sort merge incur high disk I/O costs when memory buffer space is limited [ZEL90]. Hash-based join techniques, such as the hybrid hash join algorithm, were proposed to complement nested loop and sort merge [DEW84, SHA86] for large memory systems.

     

    Alternatively, join acceleration information can be cached on disk. In the materialized view technique [ADI80, BLA90, and SHM84], the entire join result is cached on disk between executions of a join. This technique has proven to be particularly valuable in decision support systems and data warehouses. In the Join Index technique [VAL87], surrogate pairs representing the join result are stored on disk instead. In the Domain Vector technique [PER91, GUS92], only bit vectors representing participating join values are stored on disk. In [RAM93, PER94, PER95], a distributed version of the domain vector join method is developed for low speed local area networks.

     

    To show how the design criteria can be applied to an existing distributed query algorithm, we will extend a distributed version of the domain vector join method developed for low speed local area networks [RAM93, PER94, PER95]. Before this, we give a brief description of the Domain Vector Acceleration approach. For complete details, the reader is referred to [PER91,GUS92].

     

    1. Domain Vector Acceleration
    2.  

      Domain Vector Acceleration (DVA) is a space and time efficient method for accelerating relational queries. A domain vector (DV) is a bit vector in which each bit represents the presence or absence of a specific domain value. Each extant domain value is assigned a unique bit position in the DV and the mapping between bit positions and extant domain values is maintained by a data structure called the domain value identifier table, or DVI table. For a join between relations R and S on attribute A, the two domain vectors, DVR.A and DVS.A, are stored on disk. When the join of R and S is called for, the domain vectors are retrieved from disk and logically ANDed to produce a Join Vector (JV). Each 1-bit in JV corresponds to an extant A-domain value that occurs in both R and S. Computation of the JV requires very little CPU overhead and JV information can accelerate query processing appreciably.

       

      Although the JV represents the common domain values present in both attributes R.A and S.A, it does not specify which records in each relation contain those values. Two indices, DVIR.A and DVIS.A, are used to identify the location of join-participating tuples by their record identifiers (RID). A DVI index contains {bit-position, RID} pairs for each tuple in the base relation. DVI indexes implemented as B+ tree indexes are space efficient and provide fast access to the records in R and S for joining, selecting and certain aggregations and orderings (e.g., count, grouped-by).

       

      If relations R and S are clustered on the DVI values, then domain vector acceleration method becomes a specialized accelerated merge join over clustered indices using the JV. When the join selectivity is low, a single linear scan of only a fraction of the pages of R and S is sufficient to create the join.

       

      On the other hand, if relations R and S have non-clustered indices, additional vectors called select-omit-vectors (SOVs) are used to minimize page accesses. SOVs are similar to the Bitmapped Indexes used in System 204, FoxPro Rushmore Technology, Sybase IQA and other systems. With non-clustered indices, DVA requires a hash method rather than sort merge method. A cost performance study in [GUS92] shows that for large joins, DVA outperforms other methods in a wide range of cases. DVs are more disk space efficient than either join indices (JIs) or materialized views (MVs), and the update cost of DV due to inserts and deletes is low and can be partially shared with referential integrity checking. Index updating is very fast. Also, in a data warehouse, update costs become unimportant, as in-place updates are rare or non-existent.

       

      A distributed version of DVA [RAM93, PER95] requires transmission of domain vectors between sites, allowing a JV to be computed at each site. It is the distributed DVA method that is extended in this paper to achieve the general methodology change proposed for very high-speed network environments.

    3. DVA for Distributed Multi-way Equi-Join in High Speed Networks

 

Domain vector acceleration reduces distributed query response time by minimizing local processing and disk I/O [GUS92, RAM93, PER95]. Now we extend it to multi-way equi-join query. For simplicity we assume they join on same attribute.

 

In high speed networks, the strategies for distributed joins must concentrate on reducing the number of sequential messages transmitted in the network (i.e., reducing the number of latency periods). In the extended DDVA multi-way equi-join method proposed below(we call it HSN-DDVA), we reduce the number of sequential messages passed for a distributed multi-way join to a minimum of three. These three steps are absolutely necessary to achieve full reduction in joining large files over high speed, connection-oriented WANs. Our algorithm also attempts to maintain the maximum parallelism of local processing at different sites. Since we consider a connection-oriented BoD type of high speed network in which there is no 1-step mechanism to set up a fully connected network, we devise a 2-step efficient connection setup strategy. The HSN-DDVA method is illustrated for a distributed multi-way join in Figure 2.

 

Consider a query Q requiring a join among relation R1 at site S1, R2 at site S2, , and Rn at site Sn on a common attribute A, where site S1 initiates the join.

Q = R1 ÷ Xç R2 ÷ Xç ÷ Xç Rn

 

The HSN-DDVA [PZK97b] is as follows:

  1. At site S1 , retrieve DV (R1.A) from disk and simultaneously setup a point-to-multipoint unidirectional connection from site S1 to site Si (i = 2,..., n)
  2. Send Q together with DV (R1.A) to site Si (i = 2,..., n), then tear down this connection
  3. At each Si (i=2,...,n), retrieve DV(Ri.A), simultaneously setup a point-to-multipoint unidirectional connection from site Si to every other site Sj (j = 1,..,i-1, i+1,...,n)
  4. From each Si (i=2,...,n) ship its DV(Ri.A) to every other site Sj (j = 1,...,i-1, i+1,...,n)
  5. At each site Si (i = 1,..,n), logically AND DV(Ri.A) (i = 1,...,n) to create JV
  6. At each Si (i=1,...,n), use DVI(Ri.A) to read participating tuples, Ri.A, in JV order.
  7. From each site Si (i = 2,...,n) ship Ri.A to site R1 along the same connection set up used in step c, then tear down each connection
  8. At S1, merge join Ri .A (i=1,...,n) (already sorted in JV order) to get the final result.

 

Figure 2. The Extended Distributed DVA

 

The first message (i.e. query Q) has to be sent from the query initiating site to all other participating sites so that they know which join will be executed. We send Q and DV(R1.A) together based on the fact that a connection has to be set up before Q could be sent and connection setup will take as much or more time than retrieving a DV from disk. In our algorithm, we introduce only one extra message (second message in order to create JV) before retrieving and sending only participating tuples. This reduces the total latency delay to a minimum, which is important in high speed network. In terms of connection setup, we include only two (sequential) to do all the communication jobs. In the next section, we give a performance analysis of our algorithm and compare the response time to a provable theoretical low bound.

 

  1. PERFORMANCE ANALYSIS

 

In this section, the performance of the HSN-DDVA is analyzed using an analytic cost model. The response time cost of HSN-DDVA is shown to be very close to a provable theoretical lower bound. From this it can be concluded that the HSN-DDVA response time is close to optimal. The theoretical lower bound is calculated by adding together the response times associated with required sequential steps in the distributed join process, ignoring all other costs. That sum will be less than or equal to the response time of any method that accomplishes the join. It is therefore a lower bound. Due to space limitations we do not discuss the maintenance cost of domain vectors and the comparison of DVA algorithm with semi-join method ( [GUS92, RAM93, and PER95].)

 

    1. The Theoretical Lower Bound Cost

 

Any distributed, full reducing, multi-way equi-join among relations R1 , R2 ,..., Rn at sites S1, S2, , and Sn on a common attribute A in a connection-oriented network, would have to include at least the following steps: (Assume Q is issued at site S1.)

a) Set up connections from site S1 to site Si (i = 2,...,n)

  1. A small message Q must be sent from S1 to site Si (i=2,...,n), so it is known at site Si, which join is to be executed. We make the theoretical lower bound assumption that this information can be transmitted by sending only one byte.
  2. Set up connections from Si (i = 2,...,n) to all other participating sites.
  3. Each site needs to send a message containing necessary meta information to be used by the other sites to fully identify their participating records. We make the theoretical lower bound assumption that one byte is sufficient to provide the necessary information to achieve this full reduction.
  4. At site Si (i = 1,..., n), at least the set of participating tuples, Ri.A, must be read from disk using some index. To guarantee a theoretical lower bound, we assume the index read can be done at zero time cost. Since all Ri.As are read in parallel, the cost for this step is the time to read the largest Ri.A.
  5. Ri.A (i=2,..., n) from Si to S1, costing the send time for the largest Ri.A.

g) The join at S1 is a merge since all Ri.A arrive in the same order (JV-order). It It is well known that the most efficient join for ordered relations is the merge.

The costs of these steps would be the lower bound for the cost of the distributed join regardless of the method. Three messages, (1) sending the query from the query initiating site to all other participating sites, (2) sending reduction information from each site to all other sites and (3) sending participating records to the query initiating site are absolutely necessary to achieve full reduction. Since connections have to be set up before any data can be transferred, a connection from S1 to all other sites is needed for message one. Once the query Q arrives, each sites other than S1 can set up a connection to all other sites in parallel. We calculate a theoretical lower bound by adding together the response times associated with these required sequential steps, ignoring all other costs. We then show that the actual cost of our method is only slightly higher than this lower bound. We conclude that our method is near optimal in terms of response time.

 

Calculation of the Theoretical Lower Bound:

TotalLB = T Setup1 +TSEND_Q +TSetup2 + TSEND_Red + TREAD_Ri.A + TSEND_Ri.A +TACTJ , where T Setup1 is the cost of step a.; TSEND_Q is the cost of step b; TSetup2 is the cost of step c; TSEND_Red is the cost of step d; TREAD_Ri.A is the cost of step e; TSEND_Ri.A is the cost of step f, and TACTJ is to cost of the final join step g.

 

We note again that no index cost is assigned to step e. This assumption is made to guarantee that the theoretical cost calculation is in fact a lower bound.

 

    1. System Performance Prameters
    2.  

      TACTJ Time to process ACTual Join by accessing only participating pages.

      BandWidth The bandwidth of the network in Megabits per second (Mbps)

      TRET_DV(X.A) Time to retrieve DV(X.A) from the disk

      TSEND_Red Time to send reduction information from a site to all others

      TSEND_DV(X.A) Total elapsed time between sending and receiving of DV(X.A)

      TJV Time to calculate JV

      TDVI Time to access DVI

      TREAD_X.A Retrieving X.A from memory

      TSEND_X.A Total elapsed time between sending and receiving of X.A

      TSetup Time to set up a point-to-multipoint unidirectional connection

       

    3. Cost Analysis of Distributed Domain Vector Acceleration

 

The total response time for our HSN-DDVA method is

Total = TRET_DV(R1.A) or TSetup1 + TSEND_DV(R1.A)&Q + TRET_DV(Ri.A) or TSetup2 + T SEND_DV(Ri.A) + TJV + TDVI + TREAD_Ri.A + TSEND_Ri.A + TACTJ

 

Notice that in our algorithm, the setup of connections and retrieval of DVs, which occur in both step a) and step c), are done in parallel. If we take average 50Mbit/sec as the disk rate (current state-of-the-art), the time to read a 1Mbit DV is 20msec. However, to setup a connection across United States will take at least 40msec (a round trip propagation delay) plus the amount of time to go through each of the ATM switches in the path between the source and destination end systems. Notice the costs of TRET_DV(R1.A) and TRET_DV(Ri.A) can be ignored since they overlap with the setup costs of Setup1 and Setup2. The total response time for our algorithm becomes:

Total = TSetup1 + TSEND_DV(R1.A)&Q + TSetup2 + T SEND_DV(Ri.A) + TJV + TDVI + TREAD_Ri.A + TSEND_Ri.A + TACTJ

 

The costs for TREAD_Ri.A and TSEND_Ri.A are read-send-time of the largest Ri.A.

 

    1. Additional Cost
    2.  

      We will now show that the response time cost of HSN-DDVA, our new distributed domain vector acceleration method is only slightly higher than a known theoretical lower bound and some of the extra costs can not be further improved because of the speed of light. Thus, even though HSN-DDVA may not be the absolute lowest cost method, it leaves very little room for improvement. That is our assessment plan.

      The theoretical lower-bound cost is

      TotalLB = T Setup1 + TSEND_Q + TSetup2 + TSEND_Red +TREAD_Ri.A + TSEND_Ri.A + TACTJ ,

      The total response time for the HSN-DDVA method is Total =TSetup1+ TSEND_DV(R1.A)&Q +TSetup2 +T SEND_DV(Ri.A) +TJV +TDVI +TREAD_Ri.A +TSEND_Ri.A + TACTJ

       

      Thus, the additional response time for HSN-DDVA above the lower bound is:

      TDELTA = (TSEND_DV(R1.A)&Q - TSEND_Q) + (T SEND_DV(Ri.A) - TSEND_Red ) + TJV + TDVI

       

      Now we derive detailed formulas for each of these cost components. We assume the connection between any pair of sites has the same capacity (bandwidth). The cost of sending a piece of information F from a site to another is Latency(dist) + Data(F)/BandWidth, where the dist is the distance between sites, and Data(F) is the number of bits in F. Therefore Data(F)/BandWidth is the data transmission delay in getting the data from the network - the time between the arrival of the first and last bits or the transmission. The latency or propagation delay is the time taken for light to travel the distance between sites X and Y, Latency(dist) = dist / (2* 108) seconds. For TDELTA, (TSEND_DV(R1.A)&Q -TSEND_Q ) = Latency(dist) + Data(||DV|| + Q)/BandWidth - Latency(dist) - Data(Q)/BandWidth = Data(||DV||)/BandWidth This component will be very small in high speed network. For example, sending a 1Mbit DV across US over a Gigabit network takes 1msec that is small comparing with 20msec latency delay. The next component (TSEND_DV(Ri.A) -TSEND_ReD) is calculated as Latency(dist)+ Data(||DV||)/(BandWidth / (n-1)) - Latency(dist) - Data(ReD)/(BandWidth / (n - 1)) = Data(||DV|| - ReD)/(BandWidth / (n-1))

       

      The number of sites n appears in this formula because for each site there are n - 1 incoming connections, in worst case dividing the total bandwidth by (n - 1). This cost is calculated only once because the sending of DV(Ri.A) are done in parallel among sites Si (i = 2 ~ n). When network bandwidth is high, this is small. We give a brief discussion.

       

      Computation of the join vector, JV, involves a bitwise AND of DV(Ri.A) (i = 1~n), at a cost of 1.3 m sec per word ([RAM93, PER94, PER95]); that is TJV = ( || DV || * 1.3 ) / 32 m sec. In our HSN-DDVA, the participating records are read by accessing the small indexes DVIRi.A (i = 1,...,n). We assume these indices are implemented as two level B+ trees [Bay72] with root nodes pinned in memory. Since the selectivity for multi-way join is low, the number of page accesses in worst case will be equal to the number of participating records involved at each site.

       

      The rest of the components in the formula of TDELTA are the calculations of JV and the time to access DVI. For a detailed discussion, we refer readers to [RAM93, PER94, PER95]. Each of the components that make up TDELTA has been calculated to compute TDELTA for different sizes of JV and different bandwidths. Each of those terms were calculated using the equations shown in previous sections and using typical values for the atomic variables. These TDELTA values result in tables that show the relationship between TDELTA (extra response time), BandWidth and size of JV(in bits).

       

      Parameters Typical Values

      Number of Sites 4

      Attribute Selectivity 0.1

      Disk Rate 50Mbit/s

      Page Size 8kbytes

       

      Additional Response Times in Seconds

       

      BandWidth (bps)

       

      Sizeof JV(bits)

      108

      109

      1010

      1011

      10,000

      0.00210

      0.00174

      0.00171

      0.00170

      100,000

      0.0210

      0.0174

      0.0171

      0.0170

      1,000,000

      0.210

      0.174

      0.171

      0.170

       

      From the table, we can easily see for typical bandwidths and size of JVs, the difference in response time for our algorithm and the optimal theoretical algorithm is very small. Thus, we conclude that HSN-DDVA is nearly optimal.

       

    3. Bandwidth Reduction for Meta- Data Processing

 

In HSN-DDVA, a strategy is developed that introduces only one sequential message that is minimum for data reduction. The communication strategy used in HSN-DDVA for data reduction is based on group multicast [ZKH96]: each site multicasts its meta-data (DV) for data reduction to all other sites. Multicast yields a better performance in terms of response time. However, it generates a lot of traffics floating through the network. Assume n sites involved in a join, the traffic for exchanging DVs is n2. There are also redundant operations for end systems. Each site performs the same ANDing and produces the same results (JV). We propose the following scheme to leverage computation and storage (Figure 3 (a)).

 

An active node connecting all end-systems is used as the ANDing node within the network. Each site after receiving the query, retrieves its own DV from disk and then sends it to the active node. When the first DV arrives at the active node, it allocates a buffer space for storing it. When second DV arrives, it gets ANDed with previous one. The result is a partial JV. This step is repeated as new DV comes. A final JV is produced after receiving all DVs. The active node, in turn, multicasts the JV to all sites.

 

Figure 3. (a) ANDing within the network

 

 

 

 

Figure 3. (b) ANDing at the end systems

 

 

Figure 3 (a) shows the new scheme. Each link between the active node and the end system has only one message each direction. Compared with the old scheme (non-active networking, Figure 3 (b) which has n2 messages, the total network traffic is 2 * n for the new scheme. In new scheme, each end system needs only handle 2 messages while in old scheme this value is n. Doing this significantly reduces the overhead of software handling of messages at the sender and receiver(s).

 

Another potential advantage is that since the data we process in the switches or routers are simple bit vectors, it is possible that the ANDing operation can be done at very low level of the network stacks. Doing this also reduces the overhead associated with software layer handling at end systems.

 

Query meta-data processing we propose in this dissertation assembles the information merging application envisioned by active network researchers as a new application [T+97]. Merging data within the network reduces the bandwidth requirement at the end users, which are located at the (low bandwidth) periphery of the network.

 

  1. CONCLUSIONS AND FUTURE WORK
  2.  

    This paper demonstrates that active networking can improve the performance of distributed database systems in terms of latency and bandwidth. The set of strategies developed can be used as a guideline for the query algorithm designer. Issues such as transmission delay and latency, bandwidth-on-demand, and multicast must be addressed. It is demonstrated that by applying some or all of these strategies, a distributed query processing algorithm designed for a traditional network environment can be successfully implemented to take account of the new environment. It is also shown that active networking can be applied to amortize the communication and processing cost of query meta-data by merging them within the network.

     

  3. REFERENCES

 

[ADI80] Adiba, M., Lindsay, B., "Database snapshots," VLDB, 1980, pp. 86-91.

[ALL95] Alles, A., "ATM Networking," Cisco Systems, Inc. May 1995.

[BAY72] Bayer, R., and McCreight, E., "Organization and Maintenance of Large Ordered Indexes," Acta Inf., Vol. 1, No. 3. 1972.

[BLA77] Blasgen, M. W., and Eswaran, K. P., "Storage and Access in RDBSs," IBM Journal, V6:4, 1977.

[BLA90] Blakeley, J. A., and Martin, N.L., "Join Index, Materialized View, and Hybrid-Hash Join," IEEE Data Eng Conf, Los Angeles, 1990.

[DEW84] DeWitt, D .J., et al, "Implementation Techniques for Main Memory Databases," ACM SIGMOD, June 1991, Boston, pp.1-8.

[GUS92] Gustafson, et al, "DVH: A query Processing Method using Domain Vectors and Hashing," IEEE RIDE-TQP Workshop, Feb, 1992.

 

 

 

 

 

 

 

 

 

 

 

 

[PER91] Perrizo, W., et al, "DVA: A Query Accelerator for Relational Operators," IEEE Conf. on Data Engineering, April, 1991, Kobe, Japan.

[PER94] Perrizo,W., Ram, P., andWenberg, D., "Distributed Join Processing Performance Evaluation," Conf on System Science, Maui, HI, Jan 1994.

[PER95] W. Perrizo and P. Ram, "Multidatabase Global Query Optimization," IEEE-ACM System Science Conference, Maui, HI, January, 1995.

[PVZ+96] W. Perrizo, R. Vetter, Z. Zhang, A. Duggal, S. Krebsbach, "A Method for Answering Queries over Future High Speed Networks", Conference on Computer Applications in Industry and Eng, Orlando, Florida, Dec., 1996.

[PZK97b] W. Perrizo, Z. Zhang, S. Kresbach, "Strategies for Implementing Distributed Query Algorithms over High-Speed, Bandwidth-on-Demand, WANs", IEEE COMPSAC'97, Washington D.C., August 11-15, 1997.

[PZK97a] W. Perrizo, Z. Zhang, S.Krebsbach, "A Query Processing Method for Data Warehouses which Contain Multimedia Data", Proceedings of the ACM Symposium on Applied Computing, San Jose, CA, Feb 28, 1997.

[RAM93] Ram, P., "Residual Surrogates in Database Query Processing," Ph.D. Thesis, NDSU, Fargo,1993.

[SHA86] Shapiro, L., "Join Processing in Database Systems with Large Main Memories," ACM Transactions on Database Sys, Sep 1986, pp. 239-264.

[SHM84] Shmueli, O., Itai, A., "Maintenance of Views," SIGMOD84, pp. 240.

[T+97] D.Tennenhouse et al. A Survey of Active Network Research, IEEE Communication Magazine, 1997.

[VAL87] Valduriez, P., "Join Indices," ACM Trans Database Sys, 1987, pp. 218.

[ZEL90] Zeller, H.J., Gray, J., "Adaptive hash joins for a multiprogramming", VLDB-90, Australia,1990.

[ZKH96] Z. Zhang, S. Krebsbach, G. Hamer, "Multicast Issues in Distributed Database over ATM", Proceedings of the Mid-continent Information and Database Systems Conference, Fargo, ND, August 6-7, 1996.

 

 

 

 

Copyright 2000 ACM

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and or fee.
SAC 2000 March 19-21 Como, Italy
(c) 2000 ACM 1-58113-239-5/00/003>...>$5.00