Patent Publication Number: US-9851958-B2

Title: Method, apparatus, and computer program for specializing serializer

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims the benefit of priority under 35 U.S.C. 119 from Application No. 2013-269077, filed on Dec. 26, 2013 in Japan, the contents of which are incorporated by reference herein. 
     BACKGROUND OF THE INVENTION 
     The present invention relates to a method, apparatus, and computer program for performing type inference of serialization for each generation site and specializing a serializer for each generation site. 
     With the recent proliferation of Internet environments, improvements in processing speed of various computers has led to an increase in attention to big data, which is a massive volume of digital data. Big data is not merely massive in volume, but also unstructured and requires high real-time performance. In conventional database management systems, data is structured and stored, and later processed and analyzed. It is therefore regarded as difficult to handle big data whose properties are incompatible with conventional databases. 
     In the case of analyzing data using a NoSQL (Structured Query Language) language, (e.g., JAQL), for handling semi-structured data, such as JavaScript Object Notation (JSON), a proper response may not be obtained due to a bottleneck caused by the input and output costs of a large amount of data communication. Accordingly, various measures can be taken, such as unifying data processing using a type (schema) and also compressing data to reduce the data size before analysis. 
     For example, patent literatures including Japanese Patent Application Publication Numbers 2003-122730, 2003-122773, 2003-249961, 2005-056085, 2005-157718, and 2005-209048, Japanese Translation of PCT International Application Publication No. 2007-522558, and WO 2011/111532 disclose techniques of executing serialization and/or deserialization in the case of processing a massive volume of digital data. Mostly, serialization and/or deserialization disclosed in the patent literatures 1 to 8 are dynamically executed while checking types and values. 
     Japanese Translation of PCT International Application Publication No. 2007-519078 and Japanese Patent Application Publication No. 2010-237867 disclose systems that use type inference for inferring a type (schema). For example, by inferring a type of a record having values and names (identifiers), big data can be deserialized to data that can be actually handled. 
     SUMMARY 
     However, in the case where serialization and/or deserialization are dynamically executed while checking types and values, there is a problem of possible excessive processing loads. For example, in the case of compiling a query, a type generalized by merging of control flows in the query is inferred. The use of an existing serializer here involves an immense amount of time and cost to check types and values. 
     The present invention has been made in view of such circumstances, and has an object of providing a method, apparatus, and computer program for performing type inference of serialization for each generation site and specializing a serializer for each generation site. 
     To achieve the object stated above, a method according to a first aspect of the invention is a method executable in an apparatus for generating at least one of a serializer and a deserializer in the case of compiling a query, the method including: inferring a type of serialization for each generation site of compiling the query; specializing the serializer for each generation site, based on the inferred type and a type that is actually used; and serializing a data value using the specialized serializer for each generation site. 
     A method according to a second aspect of the invention is the method according to the first aspect, wherein inferring a type of serialization for each generation includes: executing the inference, while transcribing identification information assigned to each generation site to a type as an annotation; and recursively comparing the inferred type and the type used in serialization. 
     A method according to a third aspect of the invention is the method according to inferring a type of serialization for each generation or specializing the serializer for each generation site, wherein in the case of generating a serializer of a record type having an optional area, specializing the serializer for each generation site includes: generating code for outputting a bit “1,” in the case of determining that an optional area in a first type T0 is already requested in a second type Tc; generating code for outputting a bit “0,” in the case of determining that the optional area in the first type T0 is not present in the second type Tc; and generating, in the case where the optional area in the first type T0 is also an optional area in the second type Tc, code for outputting a bit “1” if a data value is present and code for outputting a bit “0” if no data value is present. 
     A method according to a fourth aspect of the invention is the method according to inferring a type of serialization for each generation or specializing the serializer for each generation site, wherein in the case of generating a serializer of a selection type in which a first type is selected from a plurality of types from T0 to Tn where n is a natural number, specializing the serializer for each generation site includes: generating code for outputting a numeric value “i,” in the case of determining that a second type Tc is a subtype of only the selected first type Ti where i is any of 1 to n; and generating code for serializing a data value, based on the second type Tc and the selected first type Ti. 
     To achieve the object stated above, an apparatus according to a fifth aspect of the invention is an apparatus for generating at least one of a serializer and a deserializer in the case of compiling a query, the apparatus including: type inference means for inferring a type of serialization for each generation site of compiling the query; specialization means for specializing the serializer for each generation site, based on the inferred type and a type that is actually used; and means for serializing a data value using the specialized serializer for each generation site. 
     An apparatus according to a sixth aspect of the invention is the apparatus according to the fifth aspect, wherein the type inference means includes: means for executing the inference, while transcribing identification information assigned to each generation site to a type as an annotation; and means for recursively comparing the inferred type and the type used in serialization. 
     An apparatus according to a seventh aspect of the invention is the apparatus according to the fifth or sixth aspect, wherein in the case of generating a serializer of a record type having an optional area, the specialization means includes: means for generating code for outputting a bit “1,” in the case of determining that an optional area in a first type T0 is already requested in a second type Tc; means for generating code for outputting a bit “0,” in the case of determining that the optional area in the first type T0 is not present in the second type Tc; and means for generating, in the case where the optional area in the first type T0 is also an optional area in the second type Tc, code for outputting a bit “1” if a data value is present and code for outputting a bit “0” if no data value is present. 
     An apparatus according to an eighth aspect of the invention is the apparatus according to the fifth or sixth aspect, wherein in the case of generating a serializer of a selection type in which a first type is selected from a plurality of types from T0 to Tn where n is a natural number, the specialization means includes: means for generating code for outputting a numeric value “i,” in the case of determining that a second type Tc is a subtype of only the selected first type Ti where i is any of 1 to n; and means for generating code for serializing a data value, based on the second type Tc and the selected first type Ti. 
     To achieve the object stated above, a computer program according to a ninth aspect of the invention is a computer program executable in an apparatus for generating at least one of a serializer and a deserializer in the case of compiling a query, the computer program causing the apparatus to function as: type inference means for inferring a type of serialization for each generation site of compiling the query; specialization means for specializing the serializer for each generation site, based on the inferred type and a type that is actually used; and means for serializing a data value using the specialized serializer for each generation site. 
     A computer program according to a tenth aspect of the invention is the computer program according to the ninth aspect, causing the type inference means to function as: means for executing the inference, while transcribing identification information assigned to each generation site to a type as an annotation; and means for recursively comparing the inferred type and the type used in serialization. 
     A computer program according to an eleventh aspect of the invention is the computer program according to the ninth or tenth aspect, causing, in the case of generating a serializer of a record type having an optional area, the specialization means to function as: means for generating code for outputting a bit “1,” in the case of determining that an optional area in a first type T0 is already requested in a second type Tc; means for generating code for outputting a bit “0,” in the case of determining that the optional area in the first type T0 is not present in the second type Tc; and means for generating, in the case where the optional area in the first type T0 is also an optional area in the second type Tc, code for outputting a bit “1” if a data value is present and code for outputting a bit “0” if no data value is present. 
     A computer program according to a twelfth aspect of the invention is the computer program according to the ninth or tenth aspect, causing, in the case of generating a serializer of a selection type in which a first type is selected from a plurality of types from T0 to Tn where n is a natural number, the specialization means to function as: means for generating code for outputting a numeric value “i,” in the case of determining that a second type Tc is a subtype of only the selected first type Ti where i is any of 1 to n; and means for generating code for serializing a data value, based on the second type Tc and the selected first type Ti. 
     According to the present invention, a dedicated serializer and/or deserializer can be generated for each generation site. Thus, a type used in serialization for each generation site can be reliably inferred, instead of dynamically inferring a type of a serializer which is an object, which can reduce the overall processing time. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram schematically showing a structure of a generation apparatus according to an embodiment of the present invention. 
         FIG. 2  is a functional block diagram of the generation apparatus according to the embodiment of the present invention. 
         FIG. 3  is a diagram showing an example of a predicate for computing a type where only a data value part is extracted in the generation apparatus according to the embodiment of the present invention. 
         FIG. 4  is a diagram showing an example of a rule in the case of a record type in the generation apparatus according to the embodiment of the present invention. 
         FIG. 5  is a diagram showing an example of a rule in the case of an array type in the generation apparatus according to the embodiment of the present invention. 
         FIG. 6  is a diagram showing an example of a rule in the case of a union type in the generation apparatus according to the embodiment of the present invention. 
         FIG. 7  is a diagram showing an example of a rule in the case of a primitive type in the generation apparatus according to the embodiment of the present invention. 
         FIG. 8  is a diagram showing an example of a rule in the case where a union type appears on the right side in the generation apparatus according to the embodiment of the present invention. 
         FIG. 9  is a flowchart showing a procedure of a CPU in the generation apparatus according to the embodiment of the present invention. 
         FIG. 10  is a flowchart showing a serializer specialization procedure of the CPU in the generation apparatus according to the embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     An apparatus (generation apparatus) for generating at least one of a serializer and a deserializer in the case of compiling a query according to an embodiment of the present invention is described in detail below, with reference to drawings. Note that the invention defined in the Claims is not limited by the following embodiment, and not all combinations of the characteristic matters described in the embodiment are essential to solve the problems. 
     Moreover, the present invention can be implemented in many different modes, and should not be construed as being limited to the description of the embodiment. The same elements are given the same reference signs throughout the embodiment. The present invention may be a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention. 
     Though the following embodiment describes an apparatus realized by introducing a computer program into a computer system, it is obvious to those skilled in the art that part of the present invention can be implemented as a computer program executable in a computer. That is, the present invention can be embodied as hardware which is an apparatus (generation apparatus) for generating at least one of a serializer and a deserializer in the case of compiling a query, as software, or as a combination of hardware and software. The computer program can be stored in any computer-readable recording medium such as a hard disk, a DVD, a CD, an optical storage device, or a magnetic storage device. 
     According to the embodiment of the present invention, a dedicated serializer and/or deserializer can be generated for each generation site. Thus, a type used in serialization for each generation site can be reliably inferred statically during query compilation, instead of dynamically checking a value of an object and determining a type used in serialization during data processing, which can reduce the overall processing time. 
       FIG. 1  is a block diagram schematically showing a structure of a generation apparatus according to an embodiment of the present invention. A generation apparatus  1  according to the embodiment of the present invention includes at least a CPU (Central Processing Unit)  11 , a memory  12 , a storage device  13 , an I/O interface  14 , a video interface  15 , a portable disc drive  16 , a communication interface  17 , and an internal bus  18  for connecting the foregoing hardware. 
     The CPU  11  is connected to the above-mentioned hardware elements of the generation apparatus  1  via the internal bus  18 . The CPU  11  controls the operations of the above-mentioned hardware elements, and also executes various software functions according to a computer program  100  stored in the storage device  13 . The memory  12  is composed of a volatile memory such as a static random-access memory (SRAM) or a synchronous dynamic random access memory SDRAM. A load module is expanded in the memory  12  when the computer program  100  is executed, to store temporary data generated during the execution of the computer program  100  and the like. 
     The storage device  13  is composed of a built-in fixed storage device (hard disk), a ROM, or the like. The computer program  100  stored in the storage device  13  is downloaded from a portable recording medium  90  such as a DVD or a CD-ROM in which information such as programs and data is stored, using the portable disc drive  16 . Upon execution, the computer program  100  is deployed from the storage device  13  to the memory  12  and executed. The computer program may be downloaded from an external computer connected via the communication interface  17 . 
     The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire. 
     Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device. 
     The storage device  13  includes a type comparison rule storage unit  131  storing a rule for type comparison. A rule for recursively comparing an inferred type and a type used in serialization for each generation site is stored in the type comparison rule storage unit  131 . 
     For example, a rule for computing a predicate is stored according to type such as a record type, a union type, and a primitive type. The CPU  11  computes the predicate according to the stored rule, and compares the inferred type and the type actually used in serialization. 
     The communication interface  17  is connected to the internal bus  18 , and is capable of data transmission and reception to and from the external computer and the like when connected to an external network such as the Internet, a LAN, or a WAN. 
     The I/O interface  14  is connected to input devices such as a keyboard  21  and a mouse  22 , and receives data input. The video interface  15  is connected to a display device  23  such as a CRT display or a liquid crystal display, and displays a given image. 
       FIG. 2  is a functional block diagram of the generation apparatus  1  according to the embodiment of the present invention. In  FIG. 2 , an annotation addition unit  201  in the generation apparatus  1  adds an annotation for identifying a generation site, to a sub-expression of a query. 
     For example, suppose queries to two tables, $t0 and $t1, are respectively represented by map functions shown in Expression 1.
 
map Fn 0($ t 0)=$ t 0→transform $ x [$ x.id,{“x ”:$ x}] 
 
map Fn 1($ t 1)=$ t 1→transform $ y [$ y.id,{“y ”:$ y}].   (Expression 1)
 
     An annotation is assigned to each generation site to identify that the generation site is added to the right side (sub-expression) of Expression 1. As an example, adding an annotation for the table $t0 yields Expression 2.
 
$ t 0 2 →transform1$ x[   3 $ x   5 , 4   id   6 ,{ 7   “x”   8 :$ x   9 }].  (Expression 2)
 
     A type inference unit  202  (e.g., a type inference means) infers a type of serialization for each generation site of compiling a query. 
     In practice, the type inference unit  202  includes: an execution unit  203  for executing inference, while transcribing identification information assigned to each generation site, to a type as an annotation; and a comparison unit  204  for recursively comparing an inferred type and a type used in serialization. 
     The execution unit  203  (e.g., means for executing the inference) transcribes identification information assigned to each generation site to a type as an annotation to thereby obtain Expression 3, in the case of executing type inference. Expression 3 is a type-inferred annotated type Tc.
 
 Tc=[   1 [ 3 long 0 ,{ 7   “x”:{   0   “id ”:long 0 ,“name”:string 0 }]*].  (Expression 3)
 
     In more detail, the rule of type inference varies according to a sub-expression. For example, in the case where a sub-expression of a NoSQL expression is a “transform” expression as in Expression 2, the type of the left side is recursively inferred. When the inference result is a variable length array type [t*], an assumption that the type of the variable $x is t is added to an environment Γ, and the type of [ 3 $x 5 ,  4 id 6 ,{ 7 “x” 8 :$x 9 }], which is a sub-expression, is inferred. 
     When the type inference result of the sub-expression is a type u, an array type [l u*] is inferred. This is written as Expression 4. In Expression 4, e denotes the left side of Expression 2, e2 denotes the expression in square brackets “[ ]” in Expression 2, l (the lowercase of letter L) denotes the numeric value of the annotation, and u denotes the result of type-inferring the sub-expression e2. 
     
       
         
           
             
               
                 
                   
                     
                       Γ 
                       - 
                       
                         e 
                         : 
                         
                           
                             [ 
                             
                               t 
                               * 
                             
                             ] 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           Γ 
                         
                       
                     
                     , 
                     
                       $ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         x 
                         : 
                         
                           
                             t 
                             ⊢ 
                             
                               e 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               2 
                             
                           
                           : 
                           u 
                         
                       
                     
                   
                   
                     
                       Γ 
                       ⊢ 
                       e 
                     
                     -&gt; 
                     
                       transform 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       l 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       $ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         x 
                         ⁡ 
                         
                           [ 
                           
                             l 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             u 
                             * 
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Expression 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     4 
                   
                   ) 
                 
               
             
           
         
       
     
     In the case where the sub-expression of the NoSQL expression is an if-expression, such as “if e then e1 else e2,” the types of the sub-expressions e, e1, and e2 are recursively inferred. When the type inference results are respectively Bool, s, and t, a union type slt is inferred, yielding Expression 5. 
     
       
         
           
             
               
                 
                   
                     Γ 
                     ⊢ 
                     
                       e 
                       : 
                       
                         
                           
                             Bool 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             Γ 
                           
                           ⊢ 
                           
                             e 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                         
                         : 
                         
                           
                             
                               s 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               Γ 
                             
                             ⊢ 
                             
                               e 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               2 
                             
                           
                           : 
                           t 
                         
                       
                     
                   
                   
                     
                       
                         Γ 
                         ⊢ 
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           e 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           then 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           e 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           else 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           e 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                       
                       : 
                       
                           
                       
                       ⁢ 
                       s 
                     
                     ❘ 
                     t 
                   
                 
               
               
                 
                   ( 
                   
                     Expression 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     5 
                   
                   ) 
                 
               
             
           
         
       
     
     In the case where the sub-expression of the NoSQL expression is a generation expression of a constant length array [le1, e2, . . . ], the types of the sub-expressions e1, e2, . . . are recursively inferred. When the type inference results are respectively t1, t2, . . . , a constant length array type [lt1, t2, . . . ] is inferred for [le1, e2, . . . ], yielding Expression 6. 
     
       
         
           
             
               
                 
                   
                     
                       Γ 
                       ⊢ 
                       
                         e 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                     : 
                     
                       
                         
                           t 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           Γ 
                         
                         - 
                         
                           e 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                       
                       : 
                       
                         t 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         … 
                       
                     
                   
                   
                     
                       Γ 
                       - 
                       
                         [ 
                         
                           
                             l 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             e 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                           , 
                           
                             e 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             2 
                           
                           , 
                           … 
                         
                         ⁢ 
                         
                             
                         
                         ] 
                       
                     
                     : 
                     
                       [ 
                       
                         
                           l 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           t 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                         , 
                         
                           t 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                         , 
                         … 
                       
                       ⁢ 
                       
                           
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Expression 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     6 
                   
                   ) 
                 
               
             
           
         
       
     
     In the case where the sub-expression of the NoSQL expression is a generation expression of a record type { 1 c1:e1, c2:e2, . . . }, the types of the sub-expressions e1, e2, . . . are recursively inferred. When the inference results are respectively t1, t2, . . . , a record type { 1 c1:t1, c2:t2, . . . } is inferred for { 1 c1:e1, c2:e2, . . . }, yielding Expression 7. 
     
       
         
           
             
               
                 
                   Γ 
                   - 
                   
                     e 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     1 
                   
                 
                 : 
                 
                   
                     
                       t 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       1 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       Γ 
                     
                     ⊢ 
                     
                       e 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       2 
                     
                   
                   : 
                   
                     t 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     2 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     … 
                   
                 
               
               
                 
                   Γ 
                   - 
                   
                     { 
                     
                       
                         
                           l 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           c 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                         : 
                         
                           e 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                       
                       , 
                       
                         
                           c 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                         : 
                         
                           e 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                       
                       , 
                       … 
                     
                     ⁢ 
                     
                         
                     
                     } 
                   
                 
                 : 
                 
                   { 
                   
                     
                       
                         l 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         c 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                       : 
                       
                         t 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                     , 
                     
                       
                         c 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                       : 
                       
                         t 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                     
                     , 
                     … 
                   
                   ⁢ 
                   
                       
                   
                   } 
                 
               
             
             ⁢ 
             
                 
             
             ⁢ 
             
               
                 
                   
                     ( 
                     
                       Expression 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       7 
                     
                     ) 
                   
                 
               
               
                 
                   
                       
                   
                 
               
             
           
         
       
     
     In the case where the sub-expression of the NoSQL expression is the variable $x, a type t is inferred for the variable $x when $x:t is present in the environment, yielding Expression 8.
 
Γ,$ x:t ├$ x:t   (Expression 8)
 
     The annotated type Tc can be inferred by combining the above-mentioned type inferences. 
     The comparison unit  204  (e.g., means for recursively comparing) recursively compares the inferred type Tc (second type) and a type T0 (first type) used in serialization. The type T0 used in serialization is, for example, a type of a value of a map output as shown in Expression 9. The comparison unit  204  recursively compares the type T0 used in serialization and the annotated type Tc inferred in Expression 3.
 
 To={“x”?:{“id ”:long,“name”:string},“ y”?:{“id ”:long,“score”:double}}   (Expression 9)
 
     In detail, a predicate is computed according to the rule, which is stored in the type comparison rule storage unit  131  in the storage device  13 , for recursively comparing the type used in serialization for each generation site. The type for serialization is then specified for each generation site. 
     In this embodiment, the inferred type Tc includes both a data value and key information using an array. Accordingly, a predicate for computing a type Tc′ where only the data value part is extracted is defined first.  FIG. 3  is a diagram showing an example of the predicate for computing the type Tc′ where only the data value part is extracted in the generation apparatus  1 , according to the embodiment of the present invention. The generation apparatus  1  defines the predicate according to the rule, as shown in  FIG. 3 . 
     In the case where the predicate shown in  FIG. 3  is applied to the type Tc shown in Expression 3, as an example, the type Tc′ can be obtained in curly brackets in Expression 10.
 
 Tc −value{ 7   “x”:{   0   “id ”:long 0 ,”name:string 0 }}  (Expression 10)
 
     Next, the obtained type Tc′ and the type T0 are recursively compared. Here, a predicate is equally computed based on the rule stored in the type comparison rule storage unit  131 .  FIG. 4  is a diagram showing an example of a rule in the case of a record type in the generation apparatus  1 , according to the embodiment of the present invention. In the case where the type is a record type, the generation apparatus  1  computes the predicate according to Rule  1  shown in  FIG. 4 . 
     In the case where the type is other than a record type, too, the predicate can be computed according to the rule stored in the type comparison rule storage unit  131  in the storage device  13 .  FIG. 5  is a diagram showing an example of a rule in the case of an array type in the generation apparatus  1 , according to the embodiment of the present invention. In the case where the type is an array type, the generation apparatus  1  computes the predicate according to Rule  2  shown in  FIG. 5 . 
     Likewise, the rule differs according to type.  FIG. 6  is a diagram showing an example of a rule (Rule  3 ) in the case of a union type in the generation apparatus  1 , according to the embodiment of the present invention.  FIG. 7  is a diagram showing an example of a rule (Rule  4 ) in the case of a primitive type in the generation apparatus  1 , according to the embodiment of the present invention.  FIG. 8  is a diagram showing an example of a rule (Rule  5 ) in the case where a union type appears on the right side in the generation apparatus  1 , according to the embodiment of the present invention. The generation apparatus  1  selects one of Rule  1  through Rule  5  according to type, and computes the predicate. 
     Applying such rule to Expression 3 enables the predicate to be computed as shown in Expression 11.
 
{7“ x”:{ 0“ id ”:long0,”name::string0}}
 
&lt;:{“ x”?:{“id ”:long,“name”:string},“ y”?:“id ”:long,“score”:double}}
 
{ 0   “id ”:long 0 ,“name”:string 0   }&lt;:{“id ”:long,“name”:string}
 
long 0 &lt;:long
 
string0&lt;:string
 
├ Tc′&lt;:To    (Expression 11)
 
     As can be seen from the computation result of Expression 11, a record (e.g., a data value) generated in the record generation expression { 7 “x” 8 :$x 9 } is serialized by a type {“x”?:{“id”:long,“name”: string}, “y”?:{“id”:long,“score”:double}}, and a record included in the input $t0 in Expression 1 is serialized by a type {“id”:long,“name”:string}. 
     Referring back to  FIG. 2 , a specialization unit  205  (e.g., a specialization means) specializes a serializer based on the type computed for each generation site. A serialization unit  206  (e.g., a means for serializing data) generates code for serializing a record (e.g., data value) using the specialized serializer, for each generation site. 
     The specialization unit  205  includes a first code generation unit  207  and a second code generation unit  208  (e.g., means for generating code), according to type. The first code generation unit  207  is selected and executed in the case of generating a serializer of a record type having an optional area. The second code generation unit  208  is selected and executed in the case of generating a serializer of a selection type selected from a plurality of types from T0 to Tn (where n is a natural number). 
     In the case of generating a serializer of a record type having an optional area, the generation of code for serialization of a bit vector is started. The first code generation unit  207  generates code for outputting a bit “1,” in the case of determining that an optional area in the first type T0 is already requested in the second type Tc. 
     The first code generation unit  207  generates code for outputting a bit “0,” in the case of determining that the optional area in the first type T0 is not present in the second type Tc. In the case where the optional area in the first type T0 is also an optional area in the second type Tc, the first code generation unit  207  outputs a bit “1” if a data value is present, and outputs a bit “0” if no data value is present. The first code generation unit  207  then generates code for serialization to serialize the whole area following the bit code. 
     The second code generation unit  208  generates code for outputting a numeric value “i,” in the case of determining that the second type Tc is a subtype of only the selected first type Ti (i is any of 1 to n). The second code generation unit  208  generates code for serializing a data value, based on the second type Tc and the selected first type Ti. The second code generation unit  208  equally generates code for serialization to serialize the whole area following the bit code. 
     In the case where the first type T0 is any other type, code for serialization is generated in an existing method. Code for serialization is equally generated to serialize the whole area following the bit code. 
       FIG. 9  is a flowchart showing a procedure of the CPU  11  in the generation apparatus  1  according to the embodiment of the present invention. In  FIG. 9 , the CPU  11  in the generation apparatus  1  adds an annotation for identifying a generation site, to a sub-expression of a query (step S 901 ). 
     The CPU  11  transcribes identification information assigned to each generation site of query compilation to a type as an annotation (step S 902 ), and executes type inference (step S 903 ). The CPU  11  recursively compares the inferred annotated type (second type) Tc and the type (first type) T0 used in serialization (step S 904 ). 
     The CPU  11  specializes a serializer based on the compared type for each generation site (step S 905 ), and generates code for serializing a record (e.g., a data value) using the specialized serializer for each generation site (step S 906 ). The CPU  11  then equally generates code for serialization to serialize the whole area following the bit code (step S 907 ). 
       FIG. 10  is a flowchart showing a serializer specialization procedure of the CPU  11  in the generation apparatus  1  according to the embodiment of the present invention. In  FIG. 10 , the CPU  11  in the generation apparatus  1  determines a type for generating a serializer (step S 1001 ). 
     In the case where the CPU  11  determines that the type is a record type having an optional area (step S 1001 : record type), the CPU  11  determines whether or not an optional area in the first type T0 is already requested in the second type Tc (step S 1002 ). In the case where the CPU  11  determines that the optional area is already requested (step S 1002 : YES), the CPU  11  generates code for outputting a bit “1” (step S 1003 ). 
     In the case where the CPU  11  determines that the optional area is not already requested (step S 1002 : NO), the CPU  11  determines whether or not the optional area in the first type T0 is present in the second type Tc (step S 1004 ). In the case where the CPU  11  determines that the optional area is not present (step S 1004 : NO), the CPU  11  generates code for outputting a bit “0” (step S 1005 ). 
     In the case where the CPU  11  determines that the optional area is present (step S 1004 : YES), the CPU  11  determines whether or not the optional area in the first type T0 is also an optional area in the second type Tc (step S 1006 ). In the case where the CPU  11  determines that the optional area in the first type T0 is not the optional area in the second type Tc (step S 1006 : NO), the CPU  11  skips steps S 1007  to S 1009 . In the case where the CPU  11  determines that the optional area in the first type T0 is also the optional area in the second type Tc (step S 1006 : YES), the CPU  11  determines whether or not a data value is present in the optional area (step S 1007 ). 
     In the case where the CPU  11  determines that the data value is present (step S 1007 : YES), the CPU  11  generates code for outputting a bit “1” (step S 1008 ). In the case where the CPU  11  determines that no data value is present (step S 1007 : NO), the CPU  11  generates code for outputting a bit “0” (step S 1009 ). The CPU  11  equally generates code for serialization to serialize the whole area following the bit code (step S 1010 ). 
     In the case where the CPU  11  determines that the type for generating the serializer is a selection type selected from a plurality of types from the first type T0 to Tn (where n is a natural number) (step S 1001 : selection type), the CPU  11  determines whether or not the type Tc is a subtype of only the type Ti (step S 1011 ). In the case where the CPU  11  determines that the type Tc is not the subtype (step S 1011 : NO), the CPU  11  skips step S 1012 . In the case where the CPU  11  determines that the type Tc is the subtype (step S 1011 : YES), the CPU  11  generates code for outputting the numeric value “i” (where i is any of 1 to n) (step S 1012 ). The CPU  11  generates code for serializing a data value, based on the second type Tc and the selected first type Ti (step S 1010 ). 
     In the case where the CPU  11  determines that the type for generating the serializer is any other type (step S 1001 : other type), the CPU  11  generates code for serialization in an existing method (step S 1013 ). 
     As described above, according to this embodiment, a dedicated serializer and/or deserializer can be generated for each generation site. Thus, a type used in serialization for each generation site can be reliably inferred statically during query compilation, instead of dynamically checking a value of an object and determining a type used in serialization during data processing, which reduces the overall processing time. 
     Note that the present invention is not limited to the embodiment described above, as various changes and modifications are possible within the scope of the present invention. Though the above embodiment describes serialization as an example, the processing load can also be reduced by deserialization using a type specified for each generation site.