CROSS-REFERENCE TO RELATED APPLICATIONS AND PRIORITY

[001] The present PCT application claims priority to India Patent Application No. 201921036051, filed before Indian Patent Office on September 6, 2019. Entire contents of the aforementioned application are incorporated herein by reference.

TECHNICAL FIELD

[002] The disclosure herein generally relates to data processing, and, more particularly, to a method and a system for generating responses to unstructured Natural Language (NL) queries.

BACKGROUND

[003] In various applications, systems are required to collect user queries, interpret, and identify and perform action(s) in response to the collected user queries. For example, chatbots are being used in various websites so as to provide at least some basic information regarding services being offered, to the users. The chatbot allows a user to interact with the website/platform, mostly by presenting a pre-configured list of questions or data pointers to the user. In response to a question asked by a user, the system provides appropriate response.

[004] Such questions being asked by the user can be broadly classified as structured questions and unstructured questions. While structured questions are comparatively easy for the system to interpret and understand, interpreting the unstructured questions is a challenge. For example, when the question being asked by the user is an unstructured Natural Language (NL) query, processing terms/keyword(s) alone might not be sufficient as meaning of the terms/keyword(s) may change based on context in which the question is being asked.

[005] Certain mechanisms are being employed to process natural language queries. However based on the approaches taken, capability of such mechanisms in effectively interpreting the NL queries and preparing responses can vary. SUMMARY

[006] Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a method is provided. In this method, at least one query from a user as input is fetched using one or more hardware processors, wherein the at least one query is in unstructured natural language format. Further, a sketch corresponding to the fetched at least one query is generated using the one or more hardware processors (102), wherein the sketch is a structured representation of the at least one unstructured query. Further, the sketch is transformed to one or more database queries, using the one or more hardware processors. At least one database is queried using the one or more database queries, using the one or more hardware processors. Further a response to the at least one unstructured query is generated based on one or more results obtained by querying the at least one database, using the one or more hardware processors.

[007] In another aspect, a system (100) is provided. The system includes one or more hardware processors, one or more communication interfaces, and one or more memory modules storing a plurality of instructions. The plurality of instructions when executed cause the one or more hardware processors to fetch at least one query from a user, as input, wherein the at least one query is in unstructured natural language format. The system further generates a sketch corresponding to the fetched at least one query, wherein the sketch is a structured representation of the at least one unstructured query. The system then transforms the sketch to one or more database queries, and queries at least one database using the one or more database queries. The system further generates a response to the at least one unstructured query based on one or more results obtained by querying the at least one database.

[008] In yet another aspect, a non-transitory computer readable medium for generating response to an unstructured Natural Fanguage (NF) query is provided. The non-transitory computer readable medium generates the response to the unstructured NF query by executing the following method: In this method, at least one query from a user as input is fetched using one or more hardware processors, wherein the at least one query is in unstructured natural language format. Further, a sketch corresponding to the fetched at least one query is generated using the one or more hardware processors (102), wherein the sketch is a structured representation of the at least one unstructured query. Further, the sketch is transformed to one or more database queries, using the one or more hardware processors. At least one database is queried using the one or more database queries, using the one or more hardware processors. Further a response to the at least one unstructured query is generated based on one or more results obtained by querying the at least one database, using the one or more hardware processors.

[009] It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.

BRIEF DESCRIPTION OF THE DRAWINGS

[010] The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles:

[Oil] FIG. 1 illustrates an exemplary system for processing unstructured Natural Language (NL) query, according to some embodiments of the present disclosure.

[012] FIG. 2 is a flow diagram depicting steps involved in the process of generating response to the unstructured Natural Language (NL) query, using the system of FIG. 1, according to some embodiments of the present disclosure.

[013] FIGS. 3 A and 3B (collectively referred to as FIG. 3) are flow diagrams depicting steps involved in the process of generating a sketch corresponding to the unstructured Natural Language (NL) query, using the system of FIG. 1, in accordance with some embodiments of the present disclosure.

[014] FIG. 4 is a flow diagram depicting steps involved in the process of transforming the sketch to at least one database query, using the system of FIG. 1, according to some embodiments of the present disclosure. DETAILED DESCRIPTION OF EMBODIMENTS

[015] Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the spirit and scope of the disclosed embodiments. It is intended that the following detailed description be considered as exemplary only, with the true scope and spirit being indicated by the following claims.

[016] Referring now to the drawings, and more particularly to FIG. 1 through FIG. 4, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.

[017] FIG. 1 illustrates an exemplary system for processing unstructured Natural Language (NL) query, according to some embodiments of the present disclosure. The system 100 includes one or more memory modules 101, one or more hardware processors 102, and one or more communication interfaces 103.

[018] The memory module(s) 101 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, one or more modules (not shown) of the system 100 can be stored in the memory module(s) 101. The memory module (s) 101 are further configured to store a plurality of instructions, which when executed, cause the one or more hardware processor(s) 102 to perform different actions associated with the unstructured Natural Language (NL) query (the unstructured NL query is referred to as ‘query’ henceforth) processing being handled by the system 100. The memory module(s) 101 can be further configured to store any data, associated with processing of the query and response generation being handled by the system 100. For example the data such as but not limited to the one or more queries being received/collected from a user, corresponding sketch generated, corresponding database queries generated, results fetched, responses generated, and so on can be stored in the one or more memory modules 101. The memory module 101 is further configured to store a plurality of data models generated using one or more appropriate machine learning techniques, at least for the purpose of 1. generating a sketch corresponding to a query received, 2. transforming the sketch to one or more database queries, and 3. identifying data in one or more reference databases matching the one or more database queries. In an embodiment, the plurality of data models are sequence to sequence Bidirectional Long Short Term Memory (LSTM) models along with a time-distributed dense layer.

[019] The one or more hardware processors 102 can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, graphics controllers, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) are configured to fetch and execute computer-readable instructions stored in the memory. In an embodiment, the system 100 can be implemented in a variety of computing systems, such as laptop computers, notebooks, hand-held devices, workstations, mainframe computers, servers, a network cloud and the like. The one or more hardware processors 102 are configured to perform data and control signal processing, at different stages of the query processing, as required.

[020] The communication interface(s) 103 can include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like and can facilitate multiple communications within a wide variety of networks N/W and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the communication interface(s) 103 can include one or more ports for connecting a number of devices to one another or to another server. The communication interface(s) can be configured to provide one or more channels with appropriate protocols, for the system 100 to communicate with one or more external systems. For example, the communication interface(s) 103 interacts and collects inputs required for collecting and processing the query and for further generating the response(s) to the query. The communication interface(s) 103 may further provide appropriate user interface(s) for an authorized user to interact with the system 100 and provide/ask one or more queries (which is in the unstructured natural language format). The communication interface(s) 103 can be further configured to provide one or more channels for different components of the system 100 to interact with each other and perform data and/or control transfer.

[021] The system 100 processes a query received in three steps:

1. Generating sketch from query:

[022] Processing of the query to generate the sketch is explained by considering an example. Consider the query “How many employees work in project Curie?”. Steps involved in generating the sketch for the aforementioned query are explained below:

[023] In a first step, Predicates (otherwise called ‘target concepts’) are identified and extracted from the query using an appropriate data model (a predicate finder model) from the plurality of data models. In case of database query language, the predicates refer to ‘SELECT’ part of the query. In an embodiment, in order to identify the predicates, the query is initially transformed to a vector format and is fed as input to the predicate finder model. For example, the query “How many employees work in project Curie?” is annotated as { 00 A 00 B 0 } . In this example, ‘employee’ and ‘project’ are identified as the predicates.

[024] In the next step, the system 100 finds values/entities in the query, using an entity discovery model of the plurality of models. At this stage, the system 100 takes output from previous step and replaces the identified predicates with a <predicate> token. The query is then represented as: {How many <predicate> work in <predicate> Curie}. From this sentence, all Parts of Speech (PoS) tags are extracted by the system 100 and then all the PoS tags that are stop words are ignored (during further processing of the query) by the system 100. Further, using any suitable technique (for example, a sliding window technique), n-grams are prepared from remaining part of the query, where the n-gram refers to continuous sequence of n items from the query. If more than one n-grams are present, then the n-gram which corresponds to an entity in the data and having a highest score is picked by the system 100. In the example query considered, ‘Curie’ is picked as an entity by the system 100.

[025] In the next step the system 100 finds type of the predicates and values at a node or table level. For example, in the aforementioned query, ‘employee’ is a PERSON, and hence the type of ‘employee’ is PERSON. Information pertaining to the ‘type’ allows the system 100 to accurately interpret the queries in some circumstances. For example, Consider the following sentences:

• What is employee ID of Washington?

• List all stores in Washington

[026] Here in the first sentence ‘Washington’ refers to name of a person whereas in the second sentence ‘Washington’ refers to a place. Here the type information allows the system 100 to interpret that in the first sentence ‘Washington’ refers to a name and that in the second sentence ‘Washington’ refers to a place. After identifying the entities, the system 100 may mark the entities with a token <value>.

[027] In the next step, the system 100 identifies one or more attribute types in the query. This may be done using an attribute type finder model from the plurality of models. This model identifies one or more attribute types of the predicates and values. For example, consider the following sentences:

• What is employee ID of May?

• List all employees hired in May

[028] In these examples, even though ‘May’ in first sentence and in second sentence may be present in a same table ‘Employee’, they have different attributes. In this scenario, the attribute information can be used by the system 100 to distinguish between May (a name) and May (a month). The attribute type information helps the system 100 to improve accuracy in interpreting context/intent of the query. [029] In the next step, the system 100 finds attribute values in the query, if any. This may be done using a predicate value finder model from the plurality of models. In some queries the attribute values may be already present. For example, consider the following sentences:

• How many employees work in curie?

• How many employees work in project curie?

[030] From the second sentence, it is clear that ‘Curie’ is a project. The predicate value finder model binds the predicate to the corresponding value or entity i.e. in this example ‘project’ to ‘curie’. This model may replace predicates with tag <predicate> and entities with tag <value>. Then the second sentence may be read as {How many <predicate> work in <predicate> <value>], and is annotated as [00 000 A A]

[031] In the next step, the system 100 uses an aggregators & operators model from the plurality of models to determine aggregators and operators for the predicates and entities respectively. A few examples of aggregate functions that are supported by the system 100 are count, groupby, min, max, sum, sort, and so on. Similarly, a few examples of operators supported by the system 100 are =, <, >, < >, <=, >=, and so on. The second sentence that is represented as {How many <predicate> work in <predicate> <value>] is annotated as {00 count 000 equal}. It is also inferred by the system 100 that the predicate ‘project’ and entity ‘Curie’ are related as [project] = [Curie].

[032] Further, by using data from all the data models, the system 100 generates the sketch corresponding to the query, as:

Sketch = {Select, Conditions],

Where

Select = {predjiint := employees Type := person Attr_type:= name Aggregations count]

Conditions = {predjiint ;= project value := Curie type := PROJECT Attr_type : = name }

[033] As can be seen, the sketch has a predicate part (P) and a condition part (C).

2.Transforming sketch to database queries:

[034] The sketch S is represented as S = {P, C], where P is a set {pi, p2, P ₃ , . . .p _n ] and each pi is {m, ¾, hi, gi], where m = node/table level type of predicate pi ai = attribute/predicate level type of predicate pi hi = Natural Language (NL) hint for pi gi = aggregation information for the predicate pi

[035] Similarly, C is a set {ci, C2, C3,...c _n ], where each Ci is a set {m, ai, hi, gi, Oi], where ni = node/table level type of predicate pi involved in condition Ci ai = attribute/predicate level type of predicate pi involved in condition Ci hi = Natural Language (NL) hint for pi involved in condition Ci gi = aggregation information for the predicate pi involved in condition Ci

Oi = operator involved in the condition Ci

[036] The sketch S contains information about all predicates identified, which indicates list of attributes that needs to be extracted from tables of a table T that stores information. Similarly the sketch S contains information about all conditions which gives similar information about data in rows of T. To transform the sketch to the one or more database queries, the predicate part (P) and condition part (C) of the sketch are separately analyzed.

Analyzing predicate part (P) of the sketch S:

[037] While analyzing the predicate part of the sketch, the system 100 checks for semantic similarity of the predicates pi in the sketch, with that of the predicates in each table of type ni and attribute type ai. After identifying all matching predicates, the system 100 identifies corresponding tables as matching tables. Analyzing condition part (C) of the sketch S: [038] For each condition Ci of C, the system 100 identifies predicates matching value Vi of the condition Ci, wherein matching predicates are identified based on values of hi, ai, and m of the predicates. After identifying the matching predicates, the system 100 identifies the corresponding tables as matching tables.

[039] In the next step, the system 100, out of all the identified matching tables, the system 100 identifies a set of unique tables (U) for the corresponding sketch. In some scenarios, the number of matching tables may be one. In some other scenarios, the number of matching tables may be more than one (i.e. len(U) > 1). When len(U) > 1, then the system 100 computes a final relation (R) between the tables. This is done by finding a shortest path between the unique tables identified as matching the query. For example, consider that for the query “How many employees work in project Curie” the unique tables identified are ‘Employee’ and ‘Project’. Then the system 100 identifies the shortest path between these two tables in terms of a joint ‘works in’ (i.e. as Employee -> ‘works in’ -> Project). Further, using the relationship R along with the operator information, the aggregator information and any other data from the sketch S, the system 100 computes one or more database queries.

[040] For example, consider the query “How many employees in each project”. By analyzing this query the system 100 identifies that the count is on emp id and predicate is ‘project’. From this the system 100 further identifies the corresponding unique tables (T) involved and computes the relation R between the identified unique tables. Then the corresponding database query maybe:

SELECT COUNT(emp_id), proj_name FROM Employee INNER JOIN Project ON (pid_fk = pid) GROUP BY proj_name

[041 ] The one or more database queries are then used to query one or more databases, and matching data is identified. The matching data is then used to generate a response to the query from the user.

[042] FIG. 2 is a flow diagram depicting steps involved in the process of generating response to the unstructured Natural Language (NL) query, using the system of FIG. 1, according to some embodiments of the present disclosure. The system 100 fetches/collects (202) the query as an input, from the user. As the query is in an unstructured format, the system 100 processes the query to generate (204) a sketch, wherein the sketch is a structured representation of the query. Then the sketch is transformed (206) to one or more database queries. Using the one or more database queries, the system 100 queries (208) one or more reference databases and fetches matching results. The matching results are then used by the system 100 to generate (210) a response to the query received, which in turn can be provided to the user.

[043] FIGS. 3A and 3B (collectively referred to as FIG. 3) are flow diagrams depicting steps involved in the process of generating a sketch corresponding to the unstructured Natural Language (NL) query, using the system of FIG. 1, in accordance with some embodiments of the present disclosure. In order to generate the sketch for a query received, the system 100 initially detects (302) one or more predicates from the query. Then the system 100 replaces (304) all identified predicates with a predicate token (<predicate>). Then the system 100 detects and removes (306) one or more Parts of Speech (PoS) tags from the query. From the parts of the query that remains after removing the PoS tags, the system 100 detects (308) n-grams, which are then processed to identify (310) one or more concepts that exist in the query. Further the system 100 identifies (312) one or more attribute types from the query. In the next step the system 100 identifies (314) one or more predicate values, if present, from the query, and then identifies (316) one or more aggregators and operators from the query. At all the aforementioned steps, the system 100 uses appropriate data model from a plurality of data models to identify and extract relevant data. Finally the data from all the models are collected (i.e. the one or more concepts, the one or more attribute values, the one or more predicate values, and the aggregators and operators) and processed by the system 100 to generate (318) the sketch.

[044] FIG. 4 is a flow diagram depicting steps involved in the process of transforming the sketch to at least one database query, using the system of FIG. 1, according to some embodiments of the present disclosure. The sketch comprises of two parts: a predicate part and a conditions part. In order to transform the sketch to corresponding database queries, the system analyzes the predicate part and the conditions part separately.

[045] While analyzing the predicate part of the sketch, for each predicate pi, the system 100 identifies (402) a plurality of matching predicates from a plurality of reference tables (T). The system 100 then checks (404) semantic similarity of each predicate pi with the plurality of matching predicates from the plurality of reference tables. Based on the semantic similarity, some predicates from the reference tables are identified and shortlisted as matching predicates, and the system 100 then identifies (406) table (T) each of the matching predicates belong to, as matching tables.

[046] Similarly while analyzing the condition part of the sketch S, for each condition ci, the system 100 identifies (408) a plurality of matching predicates from a plurality of reference tables (T). After identifying the matching predicates, the system 100 identifies the corresponding tables (T) as the matching tables.

[047] In the next step, the system 100 considers the matching tables (from step 406 and step 410), and establishes (412) a relationship (R) between the tables identified as the matching tables. Further, based on the relationship (R), the system 100 computes (414) at least one database query.

[048] The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.

[049] The embodiments of present disclosure herein addresses unresolved problem of response generation for an unstructured Natural Language query. The embodiment, thus provides a mechanism to generate a structured representation (sketch) of the unstructured query. Moreover, the embodiments herein further provides a mechanism to transform the sketch to one or more database queries which can be used to query one or more databases. [050] It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g. using a plurality of CPUs.

[051] The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules described herein may be implemented in other modules or combinations of other modules. For the purposes of this description, a computer- usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

[052] The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope and spirit of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.

[053] Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer- readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer- readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, nonvolatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.

[054] It is intended that the disclosure and examples be considered as exemplary only, with a true scope and spirit of disclosed embodiments being indicated by the following claims.