Dialogue systems
Dialogue systems
Database, Attributes and Search Trees
Luděk Bártek
Laboratory of searching and dialogue, Fakulty of Informatics, Masaryk
University, Brno
spring 2023
Question Answering Systems for Relational Databases
Dialogue systems
Luděk Bártek
Question Answering Systems for Relational Databases
Database, Attributes and Search Trees
■ Database structure is defined by relational schema (system of attributes)
■ System tries to find requested data using the attribute values entered by user, not necessarily all.
Pawlak's Information System
Dialogue systems
Luděk Bártek
Database, Attributes and Search Trees
Author — Zdzislaw I. Pawlak (1926 — 2006), polish mathematics, member of the Polish Academy of Science.
Pawlak's IS - quaternion S = ((7, 7, \/, f)\
■ U - set of objects
■ T - set of attributes
■ V - set of attributes values
■ f : UxT->V
Pawlak's IS formally describes relations between objects, their attributes and values.
Dialogue system relation - searching the minimal set of attributes identifying each object.
Pawlak's IS
Example
Dialogue systems
Luděk Bártek
Question Answering Systems for Relational Databases
Database, Attributes and Search Trees
	Elementi	Element2	Elements	Element^
Attribute^	1	1	0	0
Attribute^	0	1	1	1
Attributes	1	1	1	0
Pawlak's IS
Search Tree
Dialogue systems
Luděk Bártek
Database, Attributes and Search Trees
Pawlak's IS Search Tree construction:
□ We gradually take individual attributes contained in the IS
and ask on their presence/value. El Leaves are the particular elements stored in IS.
Relation to system initiative dialogue interface:
■ We ask the value/presence of an attribute on the level corresponding the attribute.
■ User's answer determines the way the dialogue continues.
The mixed initiative dialogue can be used as well:
User fills the values of any number of elements at once. System will process the answer and asks for missing values.
Pawlak's IS
Search Trees Examples
Dialogue systems
Luděk Bártek
atribut.
atribut
atribut
prvek2       prvekl  prvek3 prvek4
Database, Attributes and Search Trees
Obrázek: Pawlak's IS search tree 4
Obrázek: Another Pawlak's IS search tree 4
Pawlak's IS
Interesting Problems
Dialogue systems
Luděk Bártek
Select a minimal set of the IS attributes identifying every element.
Database, Attributes and Search Trees
	Element^	Element^	Element^	Element^
attribute^	1	1	1	0
attribute	1	1	0	1
attributes	1	0	1	1
attribute^	1	1	0	0
attributes	1	0	1	0
■ Has been proved the problem is NP-Complete.
Select optimal search tree according the set of elements.
■ Criterion - the tree height for example - the problem is NP-complete again.
There are approximative algorithms.
Question Answering Systems
Examples
Dialogue systems
Luděk Bártek
Database, Attributes and Search Trees
General question answering system Start
General practitioners question answering system Hermes
Unmaintained and inaccessible NLP Fl question answering system UIO
Bot Libre Chatbots, you may create your own chatbot.