Beyond relational data Flashcards
What is semi-structured data?
Semi-structured data lies in between fully structured data (like relational databases) and entirely unstructured database (arbitrary data files)
What is fully structured data?
Data that fits a strong schema, which allows you to make highly efficient queries possible but you do need highly specific shapes/structure
What is unstructured data?
- Can store basically anything, pictures, music, arbitrary text files
- No precise description of the structure of this data which means that programs that work with these kinds of files need to know exactly how to extract the data
What is semi-structured data?
In between the two extremes you have semistructured data
Tries to pick best features of both extremes, has lots of flexibility but no schema
Describe a semistructured data model
- End up with a tree like structure, these don’t need to be trees however they can just be paths.
- Like B+ trees, data is found in the leaves. However it’s not as good at searching and doesn’t have strong balancing properties
- Each edge has a label and the label defines the relationship between the two nodes
Describe each of the elements that make up a semi-structured data tree like model
- leaf nodes: have associated data
- Inner nodes: have edges going to other nodes
- Root: no incoming edges
What advantage do semi-structured data models have over structured data models?
- As it’s semi-structured we can include some data but not others,
- It’s not a requirement that each node has the same kind of property as every other node,
- We can very easily add in attributes, by just traversing to the correct place in the tree and adding a node
What is semi-structured data useful for storing?
- Often used for sharing things between companies over the internet
- useful for storing documents
What are some of the forms for storing semi-structured data?
XML, JSON, KEY-VALUE, Graphs
Order these types of databases from fastest to slowest for accessing data: XML, JSON, Key-value, relational database
- Key-value
- relational database
- XML, JSON
What is the structure of an XML document
- the first line says that it’s an XML file, so it’s XML version 1.0, encoding UTF-8 and standalone = yes, standalone meaning that we don’t have a schema for the file.
- inside we have a bunch of lecturers with tags around them
- opening tags have no slash inside them, closing tags have a slash inside them
- so in between tags we have an element
What is not a problem in XML but is in file systems?
- Can think of the tree as a file system, with each node as folders. - Children can however have the same name and this would be a problem in a normal file, however is fine in XML because when we query we search all paths that satisfy the condition
What can XML trees not have?
in XML, we can’t have nodes with multiple parents because XML files are always trees
- We can have references in trees though, that say this node points to this other node and it’s basically how shortcuts are done in a file system.
What is the form for an XML element?
- XML files are made up of a bunch of elements
- we have opening and closing tags and in between some arbitrary text (an element)
What do you do if you want to leave an element empty?
You just combine the opening and closing tags by writing <keyword></keyword>
- elements are case sensitive so the keywords defining them must be the same
How are attributes defined in elements in XML documents?
- Write opening tag then the attribute name = value, then another attribute name = value (if there’s more than one) then the closing tag
- each attribute can only have one attribute per name, you can have as many attributes as you like but they must all be uniquely named
When should something be an attribute and when should something just be another element
- staff ID can be either because there’s only one ID, whereas you shouldn’t use email addresses as attributes because there could be multiple email addresses and you’re not allowed to write more than one value for an attribute
When should something be an attribute and when should something just be another element
- staff ID can be either because there’s only one ID, whereas you shouldn’t use email addresses as attributes because there could be multiple email addresses and you’re not allowed to write more than one value for an attribute
What is document order?
- Document order defines how XML files are ordered - they’re just ordered how they appear in the file. Whichever element comes first in the physical file, is what’s first
What is a DTD?
Document type definition or XML schema are used to define a schema for your XML files, this must be done at the start of the document
What are Entity references
Entity references are basically the shortcuts, so if you wanted to say that two elements were both members of a group, you need to point to one of them instead of writing them on both of them.
Why do we use Entity references
We do this because if you just read it as a file, then this could insinuate that there are two different groups instead of two places pointing to the same group
What is CDATA used for?
For passing information onto the processor or the application being used by you XML file for
-for example if you want to use < or > inside your text then you need to define that the XML processor knows this isn’t an error - this can be done with CDATA sections.
What is a good way of defining format of an XML file
- A DTD such as a schema of an XML file
- DTD provides information about the structure of your XML documents such as what elements may occur, what sub elements may occur inside an element and what attributes we have.
What is the value of standalone in the first line when we have a DTD for the XML file?
We set it to “no” because we do have a schema
What are the meanings of the symbols +, *, ?
+ means 1 or more of an item
* means 0 or more of an item
? means 0 or 1 of an item
- How do we define that an element must have an attribute in a DTD?
- first you define the element without the attribute by writing <!ELEMENT module EMPTY>
- then we define the attributes, by writing <!ATTLIST module code CDATA #IMPLIED>
and <!ATTLIST module title CDATA #IMPLIED>
What does #IMPLIED mean in DTD
- # IMPLIED means that the data is optional
How do we say a specific an element can’t be left empty in the DTD
- # REQUIRED if this attribute can’t be left empty or Some value “COMPXXX” as a default value or #FIXED and some value if it’s a constant
What are IDREF/IDREFS?
- IDREF references one element
- IDREFS references a list of elements
What does ID allow you to define?
ID allows you to define a unique key to be associated with an element that you can use to point to this element later using IDREF
What are the two levels of document processing?
- Well formed and valid
What does a non-validating processor ensure?
That an XML document is well formed before passing information on to an application
What features does a well formed document have?
- all elements must be within one root element
- elements must be nested in a tree structure without any overlaps
What is XPath?
XPath is basically an (advanced) “file” path in XML
What does XPath do when we have multiple children with the same name?
- You can return all of them
- Or you can return, the first, last or ith item depending on what you want
What does XPath allow us to do?
- write queries that return a set of values or nodes from an XML document
- values are string, ints, reals, etc
- nodes are the entire document, an element node or an attribute
What is the format for the most basic path in XPath?
- most basic path looks like this /E1/E2/E3/…En
- this is a slash then the name of an attribute then a slash and so on until you reach a desired attribute
- Whatever you reach by traversing down the path is what is returned.
If there is more than one result when traversing a an XML document tree what is the order of the results returned?
- The result is returned in document order, so it will return them in the order they’re written in the x-file
What is a relative path expression in XPath?
- If you don’t start the expression with a / then it will evaluate it relative to the node, so it will return anything below the given node
- so if we put student/name it will start at student as opposed to the root node students
How do we return attributes in XPath queries?
- You write a command like before but in the last tag your write an @ and then the name of an attribute and it will output whatever attribute you wrote in there
What does * mean in an XPath query
Use this * wildcard symbol to return anything directly below the named attribute
So /students/student/* will return the program code, module code
What is the general form of an XPath expression
/axis::E1/axis::E2/axis::E3/ then a tag name, attribute name or *
What are common axes?
- @ for attribute:: (returns an attribute)
- child is the default so you don’t have to write it
- //E can replace descendant::
- .. is short for parent::
- . is short for self
What is a proper descendant?
A descendant is just everything you can reach by just going one step away from you
What is a descendant-or-self?
A descendant-or-self is everything you can reach by just going zero or more steps away from you
What is a preceding-sibling?
- They have the same parent and come before in document order
What is a following sibling
- To be a following sibling, it’s still important you have the same parent! But you just come after the self node in document order.
What is a following sibling
- To be a following sibling, it’s still important you have the same parent! But you just come after the self node in document order.
What is the general form of an XPath expression with conditions?
/axis::E1[C1]/axis::E2[C1]/axis::E3[C1]/ then a tag name, attribute name or *
What type of conditions can we include in XPath query?
We can do comparisons and do combinations of these using binary operators
What does where category[1] return
means that if a book belongs to multiple categories it will take the first category in the document order and return it
What does last() return?
last() returns the last child node which can be useful if we want the biggest item in a list as this is the way data is ordered
What does ancestor*[2] return?
finds your parent’s parent
What does E[XPath] return?
Returns true if the xpath returns a non-empty set
What does E[@price] return?
returns a book if it has a price attribute
What does E[string] return?
If you write a string inside one of the square brackets it returns true if the string is not empty so if you write/data() in the condition, it checks that the string is not empty
What is the role of XPath?
It’s not really used as a query language. It’s just used to define paths in your documents
What is XQuery?
- a language for finding and extracting elements and attributes from XML documents
What is the simplest kind of XQuery?
XPaths
What is the general format of an XQuery?
FLWR
What does each part of FLWR do?
L - let this doc be the contents of ..
F - for clause iterates over whatever element you’re looking at, if there’s multiples of them it assigns the first one to the first one and then to the second one, then to the third one and so on
W - Where clause. So here we’re saying, where the E = …
R - Return clause where we say what we want to return each time we look at some element in out for loops or just once if there’s no for loop. In this case we want to return our element name.
What parts of FLWR match with FROM, WHERE and SELECT in XQuery?
Let and for = FROM
where = WHERE
Return = SELECT
What does it mean that XQuery is case-sensitive?
you must write everything in lowercase letters
Which parts of FLWR are mandatory?
F - optional
L - optional
W - optional
R - mandatory
What does ‘let doc$:= XQuery expression’ do?
- It lets you assign your document to a variable
In XQuery what do all variable names start with?
In XQuery, all variable names start with a dollar sign $
Describe for clauses in XQuery?
It just executes whatever comes after the for clause. This could be more for clauses, or a let or where and then finally a return clause.
What does the XQuery For $s in $doc/students/student do?
It will iterate through every student in the database
Describe where clauses in XQuery?
So you just have some condition inside the where clause, that evaluates the condition and if it’s true then it executes the corresponding return clause
- just wrote the keyword where
What does it mean that XQuery has Existential semantics
Existential semantics in XQuery refers to the ability to query for the existence of elements or attributes in an XML document, rather than their specific values. What is returned is true rather than the data itself.
What happen if we compare two expressions
this still uses existential semantics, so for $s1/name = $s2/name, if both sides can find the same name, then it returns true, if one of the two or neither can then it doesn’t return it.
What does the some keyword return
- We can also use some to say return true if some $variables in the XQuery expression satisfies the condition
What does the every keyword return
- We can also use every to say return true if every $variable in the XQuery expression must satisfy the condition
How can we get an XQuery to output multiple items?
We can fix this by writing the keyword <pair> as now this is only returning one item (similar to returning a tuple in Java)
- and by putting curly brackets around each item that you want to return and a comma between them</pair>
What can we use nested loops with the <pair> keyword to do?</pair>
We want to return each title and the authors separate if there was more than one so we use nested loops.
So here we loop over the books, then loop over the authors for each book and then output the pair of the title and then the name.
How does the Order by clause fit into FLWR
Can also go Order by like in SQL, so we insert the order by clause in just above the return clause
- just put keyword ascending or descending
How does the group by and where again clause fit into FLWR
We have group by underneath the original where clause
- Though just like in SQL, we can also have the where clause after group by - known as HAVING in SQL (it does not affect GROUP BY an queries the results after group by was performed on them)
How do we get distinct values in XQuery?
In XQuery, it’s a function, called distinct-values. Before it outputs the distinct values, it also converts elements to strings
where do we put the distinct-values function if we want all the values returned to be distinct not just the values to be distinct for every path (such as every student)
- So we wrap the distinct values around everything and this will give us the desired output.
- so we write it before like distinct-values(let $doc:= “mydoc.xml”…)
What are the 3 general approaches to storing XML documents in a relational database
- Store XML documents as entries of a table
- Store XML documents in schema-independent form
- Store XML documents in shredded form across a number of attributes and relations
How do we store XML in an attribute
So we create a table XMLStaff, you have the 3 attributes, doc number, doc date and some staff data.
- Then we can input into this XMLStaff some values for the doc number and doc date, then when we want to insert the XML data, you write XML(‘’) then write whatever the XML data is inside the quotation marks, like a string.
How do we store XML in a Schema-Independent representation?
- Store the xml file as a tree inside our database.
- Since XML is a tree structure, each node may have only one parent.
- The rootID attribute allows a query on a particular node to be linked back to its document node.
- While this doesn’t depend on a schema, the recursive nature of structure can cause performance problems when searching for specific paths.
- To overcome this, we create a denormalised index (table) containing combinations of path expressions and a link to node and parent node.
How do we store XML in Shredded Form?
- extract all the data from your database and then put it into your database by spreading it over a number of attributes in one or more relations
- may make it easier to index values of some elements, provided these elements are placed into their own attributes.
- Also possible to add some additional data relating to hierarchical nature of the XML, making it possible to recompose original structure and ordering, and to allow the XML to be updated.
- however with this approach you also have to create an appropriate database structure.
What is a noSQl database?
It doesn’t mean there’s no SQL involved, it just means that it’s not entirely SQL or relational database
What are noSQL databases used for?
just collect all the data together for each user
- whereas secure data needs to be stored in reliable relational databases
What are some NoSQL Database Characteristics
Designed to guarantee:
- Every non-failing node should always be accepting new queries (shouldn’t lock)
- Not the same version of consistency as in ACID
- Add scalability by just adding new computers into the network
- We want to achieve high performance by just doing simple transactions such as look-ups based on keys, and only allowing insertion of keys with the corresponding values. simple process can be done even faster than in relational databases
What is Partition tolerance
- Partition tolerance means that if a connection between nodes fails or a bunch of nodes fail, the remaining subnetworks can still operate despite missing information from another/multiple nodes
What is the CAP Theorem?
- we cannot achieve all three of these properties simultaneously
- You can only select two of these properties at once
What do NoSQL databases guarantee (Not ACID)
BASE
What does BASE mean?
- Basically available states that you should be able to answer queries nearly all the time as long as computers are running.
- Soft state and eventually consistent mean that a database state might occasionally be inconsistent. So the result you get in one place may be different to the result you get from another place because they might not have all information available at all nodes but eventually the information and the system will be made consistent.
What are the common NoSQL Database
Key value stores only let you store key and value pairs. So you can find the keys very very fast. No other operations can be done. Apart from inserting/searching for keys.
A document store does the same as a key value store, except here the value will typically be some semi-structured data and can involve look-up of data that is stored next to a key
- column stores
- Graph databases
What are key-value stores?
- the simplest kind of database system
- a collection of tables and each table consists of key value pairs
- In essence it’s just one big index
Describe distributed storage with key-value pairs
- you store each key value pair at some nodes(databases in your distributed storage)
- you spread the pairs over the different computers
- you assign the values for a key to an integer between 0 and 2 to the n-1 where n is some sufficiently large number, so you can space out your nodes
- you use a hash function (function that for same input always gives the same output)
- after determining a hash function you distribute to each node(computer) these integers
- you can have multiple versions of the same node in many places
- so in the diagram above, we have 3 copies storing A, 3 copies storing B and only 2 copies storing C which could mean computer C may be less powerful than A and B
- then the key value pair is assigned to integer i of the node that comes next.
How can we add scalability to distributed storage of key value pairs
- Scalability is fairly simple, if you need more power just add in a new computer/ add in at any location in the cycle and move the key value pairs around appropriately to balance out number of pairs at each node
- Scalability is easy, just add in new nodes, move the key value pairs around
How do we ensure availability using replication on distributed storage of key value pairs?
- We just store replicas (backups) on consecutive(next to each other) nodes in clockwise order. If you replicate something twice, it will be stored in the following node and the node following the following node. So if the following node fails, we can get it from the one after.
what is versioning?
- allows multiple versions of a data item
- if a newer version of a data item is not yet available you haven’t stored it yet on all of these replicas, you get the most recent available version.
- This is typically fine for the majority of applications but if it’s not we assign a vector clock to each version of an item X which is a list of nodes and timestamps.
- The node corresponds to where it’s stored and then we have a timestamp which is a local time on a node right where this item was written.
- We use the vector clock to decide if a version originated from another version and this is done by checking that a number is smaller than or equal to another vector clock
Describe document stores
- Databases that store collections of “documents”
- the object ID is typically generated in some way. Could just be incremental.
- the document value part is typically written in JSON (think of it as XML though)
What is the main difference between XML and JSON?
JSON is shorter
When are document stores useful to use?
- When a user asks about a restaurant they want information about that restaurant but not about other restaurants
- Makes sense to use it in this case because the amount and what type of information you want varies from restaurant to restaurant
How do you update document stores?
If you want to update it you do it only on the master
Whenever you want to do a read, you by default ask the master
how do you do replication of document stores NoSql database?
The way you do this is by splitting your collection into horizontal fragments, then based on the shard key (an indexed field that exists in all documents) you distribute them over different nodes
For replications you copy entire fragmentations to other nodes using a master/slave approach where you have one primary copy on the master and a bunch of secondary copies (the replicas)
You only have to instruct the master to update and this node will instruct the replicas to update
What is the shard (or shared) key?
- used in vertical fragmentation to be able to natural join all of the fragments back together
- it’s the attribute that all the fragments have to include with their data
What are column store NoSQL databases?
- You have multiple levels of columns, from an abstract POV it looks similar to a table for SQL
- We have column qualifier which is the name of the column
- How it differs from typical tables is we have a column family, so you don’t need to specify all of the column qualifiers in a column family, some can be left empty
-Different rows can have different qualifiers - Cells just hold values
- To reference an item you specify the column family name then the column qualifier
What is the scan keyword used for?
Scan is used for going through the whole document (table)
What is the HBase techique/
- uses two levels of fragmentation: a top and a bottom level
- horizontal fragmentation, different regions can store different column families (subsets of the columns in different places)
- bottom level: regions store different column families in different nodes
Describe graph databases
- Store the data as a graph, it’s different to XML and JSON trees
- there are no requirements: such as a root node, they can all link to each other, this graph doesn’t have to be a nice tree
- Graphs are slower than other tools
